（五）程序：
void AstarPathfinder::FindPath(int sx, int sy, int dx, int dy)
{
NODE *Node, *BestNode;
int TileNumDest;
TileNumDest = TileNum(sx, sy);
//生成Open和Closed表
/*EN=( NODE*/;calloc(1,sizeof( NODE ));
CLOSED=( NODE* )calloc(1,sizeof( NODE ));
Node=( NODE* )calloc(1,sizeof( NODE ));
Node->g = 0;
Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); // should really use sqrt(
).
Node->f = Node->g+Node->h;
Node->NodeNum = TileNum(dx, dy);
Node->x = dx;
Node->y = dy;
OPEN->NextNode=Node; // make Open List point to first node
for (;;)
{
BestNode=ReturnBestNode();
if (BestNode->NodeNum == TileNumDest) // if we've found the end, break
and finish
break;
GenerateSuccessors(BestNode,sx,sy);
}
PATH = BestNode;
}
GenerateSuccessors：
void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int dy)
{
int x, y;
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper
if ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower
if ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
}
GenerateSucc：
void AstarPathfinder::GenerateSucc(NODE *BestNode,int x, int y, int dx, int
dy)
{
int g, TileNumS, c = 0;
NODE *Old, *Successor;
g = BestNode->g+1; // g(Successor)=g(BestNode)+cost of getting from
BestNode to Successor
TileNumS = TileNum(x,y); // identification purposes/
if ( (Old=CheckOPEN(TileNumS)) != NULL ) // if equal to NULL then not in
OPEN list, else it returns the Node in Old
{
for( c = 0; c < 8; c++)
if( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's C
hildren (or Successors).
break;
BestNode->Child[c] = Old
if ( g < Old->g ) // if our new g value is < Old's then reset Old's paren
t to point to BestNode
{
Old->Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
}
}else
if ( (Old=CheckCLOSED(TileNumS)) != NULL ) // if equal to NULL then not
in OPEN list, else it returns the Node in Old
{
for( c = 0; c< 8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Chi
ldren (or Successors).
break;BestNode->Child[c] = Old;
if ( g < Old->g ) // if our new g value is < Old's then reset Old's paren
t to point to BestNode
{ Old->Parent = BestNode;
Old->g = g;Old->f = g + Old->h;
PropagateDown(Old); // Since we changed the g value of Old, we nee
d}}else
{ Successor = ( NODE* )calloc(1,sizeof( NODE ));
Successor->Parent = BestNode;
Successor->g = g;
Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy); // should do sqrt(), but si
nce we don't really
Successor->f = g+Successor->h; // care about the distance but just whi
ch branch looks
Successor->x = x; // better this should suffice. Anyayz it
's faster.
Successor->y = y;
Successor->NodeNum = TileNumS;
Insert(Successor); // Insert Successor on OPEN list wrt f
for( c =0; c < 8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Ch
ildren (or Successors).
break;
BestNode->Child[c] = Successor;
}
}
基于人工智能理论的围棋人机对弈
08计算机
1班11号
张超
20081118610015
（3）UCT Tree 搜索流程总结如下：UCT算法使用极大极小游戏树（minimax game tree）,
搭配节点选择公式（UCB公式），选择树节点，展开要测试的节点，然后使用
Monte Carlo方法执行模拟棋局，最后将模拟棋局的结果回馈更新。流程图如下：
（4）研究来源：计算机围棋相关问题研究。中国新技术新产品。２００９，（１６）：２７