算法博弈

A. 棋类游戏的算法有哪些

棋类游戏的算法有哪些

棋类游戏通常包含三大要素：棋盘、棋子和游戏规则，其中游戏规则又包括胜负判定规则、落子的规则以及游戏的基本策略。下面我来给大家讲讲各类棋类游戏的算法。

除了棋盘和棋子的建模，棋类游戏最重要的部分就是AI算法的设计。目前棋类游戏的AI基本上就是带启发的搜索算法，那么常用的搜索算法有哪些呢?

1. 博弈与博弈树

博弈可以理解为有限参与者进行有限策略选择的竞争性活动，比如下棋、打牌、竞技、战争等。根据参与者种类和策略选择的方式可以将博弈分成很多种，比如“二人零和、全信息、非偶然”博弈，也就是我们常说的零和博弈(Zero-sum Game)。所谓“零和”，就是有赢必有输，不存在双赢的结果。所谓“全信息”，是指参与博弈的双方进行决策时能够了解的信息是公开和透明的，不存在信息不对称的情况。比如棋类游戏的棋盘和棋子状态是公开的，下棋的双方都可以看到当前所有棋子的位置，但是很多牌类游戏则不满足全信息的条件，因为牌类游戏都不会公开自己手中的牌，也看不到对手手中的牌。所谓的“非偶然”，是指参与博弈的双方的决策都是“理智”的行为，不存在失误和碰运气的情况。

在博弈过程中，任何一方都希望自己取得胜利，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利同时对对方最为不利的那个行动方案。当然，博弈的另一方也会从多个行动方案中选择一个对自己最有利的方案进行对抗。参与博弈的双方在对抗或博弈的过程中会遇到各种状态和移动(也可能是棋子落子)的选择，博弈双方交替选择，每一次选择都会产生一个新的棋局状态。

假设两个棋手(可能是两个人，也可能是两台计算机)MAX和MIN正在一个棋盘上进行博弈。当MAX做选择时，主动权在MAX手中，MAX可以从多个可选决策方案中任选一个行动，一旦MAX选定某个行动方案后，主动权就转移到了MIN手中。MIN也会有若干个可选决策方案，MIN可能会选择任何一个方案行动，因此MAX必须对做好应对MIN的每一种选择。如果把棋盘抽象为状态，则MAX每选择一个决策方案就会触发产生一个新状态，MIN也同样，最终这些状态就会形成一个状态树，这个附加了MAX和MIN的决策过程信息的状态树就是博弈树(Game Tree)。

2. 极大极小值搜索算法

极大极小值(Min-Max)搜索算法是各种博弈树搜索算法中最基础的搜索算法。假如MAX和MIN两个人在下棋，MAX会对所有自己可能的落子后产生的局面进行评估，选择评估值最大的局面作为自己落子的选择。这时候就该MIN落子，MIN当然也会选择对自己最有利的局面，这就是双方的博弈，即总是选择最小化对手的'最大利益(令对手的最大利益最小化)的落子方法。作为一种博弈搜索算法，极大极小值搜索算法的名字就由此而来。

3. 负极大值搜索算法

博弈树的搜索是一个递归的过程，极大极小值算法在递归搜索的过程中需要在每一步区分当前评估的是极大值节点还是极小值节点。1975年Knuth和Moore提出了一种消除MAX节点和MIN节点区别的简化的极大极小值算法，称为负极大值算法Negamax。该算法的理论基础是：

max(a,b) = -min(-a, -b)

简单地将递归函数MiniMax()返回值取负再返回，就可以将所有的MIN 节点都转化为MAX节点，对每个节点的搜索都尝试让节点值最大，这样就将每一步递归搜索过程都统一起来。

4. “α-β”剪枝算法

有很多资料将“α-β”剪枝算法称为“α-β”搜索算法，实际上，它不是一种独立的搜索算法，而是一种嫁接在极大极小值算法和负极大值算法上的一种优化算法。“α-β”剪枝算法维护了一个搜索的极大极小值窗口：[α,β]。其中α表示在搜索进行到当前状态时，博弈的MAX一方所追寻的最大值中最小的那个值(也就是MAX的最坏的情况)。在每一步的搜索中，如果MAX所获得的极大值中最小的那个值比α大，则更新α值(用这个最小值代替α)，也就是提高α这个下限。

而β表示在搜索进行到当前状态时，博弈的MIN一方的最小值中最大的那个值(也就是MIN的最坏的情况)。在每一步的搜索中，如果MIN所获得的极小值中最大的那个值比β小，则更新β值(用这个最大值代替β)，也就是降低β这个上限。当某个节点的α≥β时，说明该节点的所有子节点的评估值既不会对MAX更有利，也不会对MIN更有利，也就是对MAX和MIN的选择不会产生任何影响，因此就没有必要再搜索这个节点及其所有子节点了。

5. 估值函数

对于很多启发式搜索算法，其“智力”的高低基本上是由估值函数(评估函数)所决定，棋类游戏的博弈树搜索算法也不例外。

估值函数的作用是把一个棋局量化成一个可直接比较的数字，这个数字在一定程度上能反映取胜的概率。棋局的量化需要考虑很多因素，量化结果是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战力(棋力)、双方棋子占领的空间、落子的机动性、威胁性(能吃掉对方的棋子)、形和势等。

6. 置换表与哈希函数

置换表(transposition table)也是各种启发式搜索算法中常用的辅助算法，它是一种以空间换时间的策略，使用置换表的目的就是提高搜索效率。一般情况下，置换表中的每一项代表者一个棋局中最好的落子方法，直接查找置换表获得这个落子方法能避免耗时的重复搜索，这就是使用置换表能大幅提高搜索效率的原理。

使用置换表最大的问题是置换表的组织和查找的效率。一般来说，置换表越大，查找的命中率就越高。但这个关系不是绝对的，当置换表大小达到一定规模后，不仅不会再提高命中率，反而会因为耗时的查找操作影响算法的效率。所以置换表不是越大越好，需要根据计算机的性能以及搜索的深度选择一个合适的大小。此外，为了查找操作更高效，通常都会用可直接访问的哈希表方式组织置换表，哈希函数的性能就成为影响置换表性能的重要因素。棋类游戏普遍采用Zobrist哈希算法。

B. c语言的五子棋代码（博弈算法）

#include<stdio.h>
#include<bios.h>
#include<ctype.h>
#include<conio.h>
#include<dos.h>
#defineCROSSRU0xbf/*右上角点*/
#defineCROSSLU0xda/*左上角点*/
#defineCROSSLD0xc0/*左下角点*/
#defineCROSSRD0xd9/*右下角点*/
#defineCROSSL0xc3/*左边*/
#defineCROSSR0xb4/*右边*/
#defineCROSSU0xc2/*上边*/
#defineCROSSD0xc1/*下边*/
#defineCROSS0xc5/*十字交叉点*/

/*定义棋盘左上角点在屏幕上的位置*/
#defineMAPXOFT5
#defineMAPYOFT2

/*定义1号玩家的操作键键码*/
#definePLAY1UP0x1157/*上移--'W'*/
#definePLAY1DOWN0x1f53/*下移--'S'*/
#definePLAY1LEFT0x1e41/*左移--'A'*/
#definePLAY1RIGHT0x2044/*右移--'D'*/
#definePLAY1DO0x3920/*落子--空格键*/

/*定义2号玩家的操作键键码*/
#definePLAY2UP0x4800/*上移--方向键up*/
#definePLAY2DOWN0x5000/*下移--方向键down*/
#definePLAY2LEFT0x4b00/*左移--方向键left*/
#definePLAY2RIGHT0x4d00/*右移--方向键right*/
#definePLAY2DO0x1c0d/*落子--回车键Enter*/

/*若想在游戏中途退出,可按Esc键*/
#defineESCAPE0x011b

/*定义棋盘上交叉点的状态,即该点有无棋子*/
/*若有棋子,还应能指出是哪个玩家的棋子*/
#defineCHESSNULL0/*没有棋子*/
#defineCHESS1'O'/*一号玩家的棋子*/
#defineCHESS2'X'/*二号玩家的棋子*/

/*定义按键类别*/
#defineKEYEX99v0/*退出键*/
#defineKEYFALLCHESS1/*落子键*/
#defineKEYMOVECURSOR2/*光标移动键*/
#defineKEYINVALID3/*无效键*/

/*定义符号常量:真,假---真为1,假为0*/
#defineTRUE1
#defineFALSE0

/**********************************************************/
/*定义数据结构*/

/*棋盘交叉点坐标的数据结构*/
structpoint
{
intx,y;
};


或者下面这个：
#include<graphics.h>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#defineN15
#defineB7
#defineSTOP-10000
#defineOK1
#defineNO0
#defineUP328
#defineDOWN336
#defineLEFT331
#defineRIGHT333

inta[N+1][N+1];
intzx,zy;
intwrite=1,biaoji=0;
structzn{
longsum;

inty;

intx;

}w[N+1][N+1],max,max1;


voidcbar(inti,intx,inty,intr);
voidmap(inta[][]);
intgetkey();
intkey();
voidzuobiao(intx,inty,inti);
inttu(inta[][],intwrite);
intwtu(inta[][],intwrite);
intneng(inta[][]);
intzh5(inty,intx,inta[][]);
longzzh5(intb[][],inti);
main()
{
inti,j;
intgdriver=DETECT;
intgmode;
initgraph(&gdriver,&gmode,"");
zx=(N+1)/2;
zy=(N+1)/2;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
a[i][j]=0;
map(a);
i=1;
while(i)
{
intk,n;
k=wtu(a,write);
if(k==STOP)gotoend;
map(a);
n=neng(a);
if(n==STOP)gotoend;
map(a);
}
end:
;
}


intneng(inta[N+1][N+1])

{
inti,j;
intk;
max.sum=-1;

for(i=0;i<=N;i++)
for(j=0;j<+N;j++)

{
w[i][j].sum=0;
w[i][j].x=i;
w[i][j].y=j;
}
for(i=1;i<=N-4;i++)
for(j=1;j<=N-4;j++)
{
k=zh5(i,j,a);
if(k==STOP)return(STOP);
}

for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{

if(max.sum<w[i][j].sum)
{

max.sum=w[i][j].sum;
max.y=i;
max.x=j;
}

elseif(max.sum==w[i][j].sum)
{

if(((max.y-zy)*(max.y-zy)+(max.x-zx)*(max.x-zx))>((i-zy)*(i-zy)+(j-zx)*(j-zx)))
max.sum=w[i][j].sum;
max.y=i;
max.x=j;
}
}
if(a[max.y][max.x]==0)

{
a[max.y][max.x]=-1;
zy=max.y;
zx=max.x;
}

}


intzh5(inty,intx,inta[N+1][N+1])
{

inti,j;
intb[6][6];
longc[13];

longd[6][6];
longtemp;
for(i=y;i<=y+4;i++)
for(j=x;j<=x+4;j++)
b[i+1-y][j+1-x]=a[i][j];
c[1]=b[1][1]+b[1][2]+b[1][3]+b[1][4]+b[1][5];
c[2]=b[2][1]+b[2][2]+b[2][3]+b[2][4]+b[2][5];
c[3]=b[3][1]+b[3][2]+b[3][3]+b[3][4]+b[3][5];
c[4]=b[4][1]+b[4][2]+b[4][3]+b[4][4]+b[4][5];
c[5]=b[5][1]+b[5][2]+b[5][3]+b[5][4]+b[5][5];
c[6]=b[1][1]+b[2][1]+b[3][1]+b[4][1]+b[5][1];
c[7]=b[1][2]+b[2][2]+b[3][2]+b[4][2]+b[5][2];
c[8]=b[1][3]+b[2][3]+b[3][3]+b[4][3]+b[5][3];
c[9]=b[1][4]+b[2][4]+b[3][4]+b[4][4]+b[5][4];
c[10]=b[1][5]+b[2][5]+b[3][5]+b[4][5]+b[5][5];
c[11]=b[1][1]+b[2][2]+b[3][3]+b[4][4]+b[5][5];
c[12]=b[1][5]+b[2][4]+b[3][3]+b[4][2]+b[5][1];


for(i=1;i<=12;i++)
{
switch(c[i])

{

case5:biaoji=1;return(STOP);

case-5:biaoji=-1;return(STOP);

case-4:c[i]=100000;break;

case4:c[i]=100000;break;

case-3:c[i]=150;break;

case3:c[i]=150;break;

case-2:c[i]=120;break;

case2:c[i]=100;break;

case-1:c[i]=1;break;

case1:c[i]=1;break;

default:c[i]=0;

}

}

for(i=1;i<=12;i++)

{

if(c[i]==150)

c[i]+=zzh5(b,i);

}

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

d[i][j]=0;

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

{

if(i==j)d[i][j]+=c[11];

if((i+j)==6)d[i][j]+=c[12];

d[i][j]+=c[i]+c[j+5];

}

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

{

if(b[i][j]!=0)

d[i][j]=-2;

}

max1.sum=-1;

max1.y=0;

max1.x=0;

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

{

if(max1.sum<d[i][j])

{

max1.sum=d[i][j];

max1.y=i;

max1.x=j;

w[i+y-1][j+x-1].sum+=max1.sum;

}

elseif(max1.sum==d[i][j])

{

if(((i+y-1-zy)*(i+y-1-zy)+(j+x-1-zx)*(j+x-1-zx))>((max1.y+y-1-zy)*(max1.y+y-1-zy)+(max1.x+x-1-zx)*(max1.x+x-1-zx)))

{

max1.sum=d[i][j];

max1.y=i;

max1.x=j;

}

}

}

}

longzzh5(intb[6][6],intn)

{

inti,j,k,l,m;

switch(n)

{

case1:i=b[1][1];j=b[1][2];k=b[1][3];l=b[1][4];m=b[1][5];break;

case2:i=b[2][1];j=b[2][2];k=b[2][3];l=b[2][4];m=b[2][5];break;

case3:i=b[3][1];j=b[3][2];k=b[3][3];l=b[3][4];m=b[3][5];break;

case4:i=b[4][1];j=b[4][2];k=b[4][3];l=b[4][4];m=b[4][5];break;

case5:i=b[5][1];j=b[5][2];k=b[5][3];l=b[5][4];m=b[5][5];break;

case6:i=b[1][1];j=b[2][1];k=b[3][1];l=b[4][1];m=b[5][1];break;

case7:i=b[1][2];j=b[2][2];k=b[3][2];l=b[4][2];m=b[5][2];break;

case8:i=b[1][3];j=b[2][3];k=b[3][3];l=b[4][3];m=b[5][3];break;

case9:i=b[1][4];j=b[2][4];k=b[3][4];l=b[4][4];m=b[5][4];break;

case10:i=b[1][5];j=b[2][5];k=b[3][5];l=b[4][5];m=b[5][5];break;

case11:i=b[1][1];j=b[2][2];k=b[3][3];l=b[4][4];m=b[5][5];break;

case12:i=b[1][5];j=b[2][4];k=b[3][3];l=b[4][2];m=b[5][1];break;

}

if((i==0&&j==1&&k==1&&l==1&&m==0))

return(900);

if((i==0&&j==-1&&k==-1&&l==-1&&m==0))

return(1000);

if((i==0&&j==0&&k==1&&l==1&&m==1)||(i==1&&j==1&&k==1&&l==0&&m==0))

return(20);

if((i==0&&j==0&&k==-1&&l==-1&&m==-1)||(i==-1&&j==-1&&k==-1&&l==0&&m==0))

return(20);

if((i==-1&&j==1&&k==1&&l==1&&m==1)||(i==1&&j==-1&&k==1&&l==1&&m==1)||(i==1&&j==1&&k==-1&&l==1&&m==1)||(i==1&&j==1&&k==1&&l==-1&&m==1)||(i==1&&j==1&&k==1&&l==1&&m==-1))

return(-60);

if((i==1&&j==-1&&k==-1&&l==-1&&m==-1)||(i==-1&&j==1&&k==-1&&l==-1&&m==-1)||(i==-1&&j==1&&k==-1&&l==-1&&m==-1)||(i==-1&&j==-1&&k==-1&&l==1&&m==-1)||(i==-1&&j==-1&&k==-1&&l==-1&&m==1))

return(-60);

}


intwtu(inta[N+1][N+1],intwrite)

{

inti=1;

map(a);

zuobiao(zx,zy,1);

while(i)

{

intk;

k=tu(a,write);

if(k==OK)i=0;

if(k==STOP)return(STOP);

}

}


intgetkey()

{

intkey,lo,hi;

key=bioskey(0);

lo=key&0x00ff;

hi=(key&0xff00)>>8;

return((lo==0)?hi+256:lo);

}


intkey()

{

intk;

k=getkey();

switch(k)

{

case27:return(STOP);

case13:

case'':return(OK);

case328:return(UP);

case336:return(DOWN);

case331:return(LEFT);

case333:return(RIGHT);

default:return(NO);

}

}


voidzuobiao(intx,inty,inti)

{

intr;

if(i!=0)

{

setcolor(GREEN);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);


}

else

{

if(a[zy][zx]==1)

{

setcolor(8);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);

}

elseif(a[zy][zx]==-1)

{

setcolor(WHITE);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);

}

else

{

setcolor(B);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);

setcolor(RED);line(75+25*zx-5,25+25*zy,75+25*x+5,25+25*zy);

line(75+25*zx,25+25*zy-5,75+25*zx,25+25*zy+5);

}

}

}


inttu(inta[N+1][N+1],intwrite)

{

intk;

re:

k=key();

if(k==OK)

{

if(a[zy][zx]==0)

{

a[zy][zx]=write;

}

else

gotore;

}

if(k==STOP)return(STOP);

if(k==NO)gotore;

if(k==UP)

{

inti,j;

if(zy==1)j=zy;

elsej=zy-1;

zuobiao(zx,zy,0);

zuobiao(zx,j,1);

zy=j;

gotore;

}

if(k==DOWN)

{

inti,j;

if(zy==N)j=zy;

elsej=zy+1;

zuobiao(zx,zy,0);

zuobiao(zx,j,1);

zy=j;

gotore;

}

if(k==LEFT)

{

inti,j;

if(zx==1)i=zx;

elsei=zx-1;

zuobiao(zx,zy,0);

zuobiao(i,zy,1);

zx=i;

gotore;

}

if(k==RIGHT)

{

inti,j;

if(zx==N)i=zx;

elsei=zx+1;

zuobiao(zx,zy,0);

zuobiao(i,zy,1);

zx=i;

gotore;

}

}


voidcbar(inti,intx,inty,intr)

{

if(i!=0)

{

if(i==1)

setcolor(8);

elseif(i==-1)

setcolor(WHITE);

for(i=1;i<=r;i++)

{

circle(x,y,i);

}

}

}


voidmap(inta[N+1][N+1])

{

inti,j;

cleardevice();

setbkcolor(B);

setcolor(RED);

for(i=0;i<N;i++)

{

line(100,50+25*i,75+N*25,50+25*i);

line(100+25*i,50,100+25*i,25+N*25);

}

for(i=1;i<=N;i++)

for(j=1;j<=N;j++)

cbar(a[i][j],75+25*j,25+25*i,10);

}

C. 博弈树算法是啥

就是用树的节点来表示博弈过程中的每一步，比如在象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是将死对方，或者避免被将死。
由此，我们可以用一棵“博弈树”（一棵n叉树）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断直到再无可选择的走法，即到达叶子结点（棋局结束）。

D. 多智能体博弈如何体现在算法中

多智能体博弈体现在算法中：
1.蚁群优化算法（AntColonyOptimization,ACO）
ACO算法思想来源于蚂蚁寻食中的通信机制，蚂蚁在寻找食物过程中通过分泌信息素，通过信息素的浓度来选取最佳路径。
对于ACO算法的改进有Max-MinAntSystem（MMAS）和AntColonySystem（ACS）算法，MMAS算法的主要特征是在每一次迭代结束后，仅最优蚂蚁对其所经过的最优路径进行信息素
更新，其他蚂蚁不参与更新，ACS加入伪随机比例规则和离线信息素更新规则，并且只对全局最优路径的信息素进行更新。
2.粒子群算法（ParticleSwarmOptimization,PSO）为代表。
PSO算法是科学家们在观察鸟群觅食时利用计算机模拟鸟群的聚集行为总结出一种群智能算法，可以在全局随机搜索,算法运行前会在自身建立的搜寻空间中设置一群随机的粒子，粒子通过迭代的
过程不断地更新自己的速度、位置逐渐朝着最优位置逼近，最终会找到最优解。

E. 博弈算法里的剪枝怎么用（具体的）

极大极小过程，以及阿尔法-贝塔剪纸。极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的α-β剪枝搜索方法，就是从这一方法发展而来的。
首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的读者都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。
想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应......这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。
极小极大搜索方法，模拟的就是人的这样一种思维过程。当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。
在图3.5所示的例子中，假定搜索深度为2，D～J是7个叶节点，在它们下边括号中的数字是这些节点的评价函数值（假定可以计算得到）。A、B、C是三个极小节点，它们分别取各自子节点最小值为自己的值，得到三个节点的值分别为-6、-2和-4。s是极大节点，从A、B、C三个节点的值中取最大值，得到-2。由于-2来自于节点B，所以搜索的结果是应选择B作为我方的走步。对于我方来说，-2并不是一个好的结果，但却是在对方不犯错误的情况下，对我方最有利的结果。因为从图中可以看出，如果选择A为我方的走步，如果对方回应D的话，我方可以得到评价值9，固然对我方有利。但是如果对方是一个高手的话，他一定回选择E，而不是D。在这种情况下，我方只能得到-6，结果岂不是更差。因此，极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。
值得注意的是，不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。为此要定义一个静态估计函数f，以便对棋局的势态（节点）作出优劣估值，这个函数可根据势态优劣特征来定义（主要用于对端节点的"价值"进行度量）。一般规定有利于MAX的势态，f（p）取正值，有利于MIN的势态，f（p）取负值，势均力敌的势态，f（p）取0值。若f（p）＝＋∞，则表示MAX赢，若f（p）＝－∞，则表示MIN赢。下面的讨论规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方，MAX先走。
图3.5是一个表示考虑两步棋的例子，图中端节点给出的数字是用静态函数f（p）计算得到，其他节点不用f（p）估计，因为不够精确，而应用倒推的办法取值。例如A、B、C是MIN走步的节点，MAX应考虑最坏的情况，故其估值应分别取其子节点f（p）估值中最小者，而s是MAX走步的节点，可考虑最好的情况，故估值应取A、B、C值中的最大者。这样求得f（s）＝－2，依此确定了相对较优的走步应是走向B，因为从B出发，对手不可能产生比f（s）＝－2更差的效果。实际上可根据资源条件，考虑更多层次的搜索过程，从而可得到更准确的倒推值，供MAX选取更正确的走步。当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。

F. 美国计算机科学都有什么课程

美国计算机科学（简称CS）是一门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分析、形式化语法等等，
到更具体的主题如编程语言、程序设计、软件和硬件等，计算机科学分为理论计算机科学和实验计算机科学两个部分。

计算机科学课程辅导

斯坦福大学计算机科学课程设置

计算生物学Computational Biology、计算机视觉Computer Vision、机器学习Machine Learning、自然语言处理Natural Language Processing、机器人Robotics、人机交互Human-computer Interaction、编程系统与验证Programming Systems and Verification 、操作与分布式系统Operating/Distributed System、网络Networking、计算机安全Computer Security、架构Architecture、算法博弈论Algorithmic Game Theory、程序与编程语言的设计与分析Design and Analysis of Programs and Programming Languages等。