/*从棋盘的一个状态出发，扩展此结点，并返回此结点的部分回溯值*/
void extend_node_one(tree_node_type *node_ptr, tree_node_type *parent_ptr,UINT8 obcolor)
{
tree_node_type childnode;
INT16 affected_list[MAX_AFFECTED_PIECES];
INT16 start_pos = 11, num;
num = find_move(&node_ptr->board, start_pos, obcolor, affected_list);
/*如果是终局状态，则返回状态估值函数的值*/
if(++cur_depth == max_depth || num==0 )
{
/*如果已方PASS但没到棋局结束,要扣分*/
node_ptr->value = calc_board_status(&node_ptr->board, computer_side);
if(!num)
{
/*如果双方都没棋下*/
if(!find_move(&node_ptr->board, 11, ~obcolor&0x03, affected_list))
return;
if(obcolor == computer_side)
{
node_ptr->value -= 15;
return ;
}
node_ptr->value += 15;
}
return;
}
/*初始化回溯值*/
node_ptr->value = (obcolor == computer_side)? -INITIAL_VALUE : INITIAL_VALUE;
memcpy(&childnode.board, &node_ptr->board, sizeof(board_type));
while(num)
{
while(num--)
childnode.board.board[0][affected_list[num]] = obcolor;
/*递归计算部分回溯值*/
UINT8 depth = cur_depth;
extend_node_one(&childnode, node_ptr, (~obcolor)&0x03);
cur_depth = depth;
/*如果此结点是棋手一方，则部分回溯值是子结点中最大的一个*/
if(obcolor == computer_side)
{
if(childnode.value > node_ptr->value)
{
node_ptr->value = childnode.value;
node_ptr->movepos = affected_list[0];
}
}
/*如果是对手一方，部分回溯值是子结点中最小的一个*/
else
{
if(childnode.value < node_ptr->value)
{
node_ptr->value = childnode.value;
node_ptr->movepos = affected_list[0];
}
}
/* α-β裁减的判断 在考虑轮到棋手下棋的一个亲节点及轮到对手下棋的一个子节点时，
如果该子节点的数值已经小于或等于其亲节点的回溯值，
那么就不需要对该节点或者其后续节点做更多的处理了。
计算的过程可以直接返回到亲节点上。
*/
/*在考虑轮到对手下棋的一个亲节点及轮到棋手下棋的一个子节点时，
如果该子节点的部分回溯值已经大于或等于其亲节点的部分回溯值，
那么就不需要对该子节点或者其后裔节点做更多的处理了。
计算过程可以直接返回到亲节点上。*/
if(parent_ptr)
{
if(obcolor != computer_side)
{
/*α裁减*/
if(node_ptr->value <= parent_ptr->value)
return;
}
else
{
/*β裁减*/
if(node_ptr->value >= parent_ptr->value)
return;
}
}
/*找到下一个可落子的点*/
start_pos = affected_list[0]+1;
memcpy(&childnode.board, &node_ptr->board, sizeof(board_type));
num = find_move(&childnode.board, start_pos, obcolor, affected_list);
}
return;
}
void extend_node_two(tree_node_type *node_ptr, tree_node_type *parent_ptr,UINT8 obcolor)
{
tree_node_type childnode;
INT16 affected_list[MAX_AFFECTED_PIECES];
INT16 start_pos = 11, num;
num = find_move(&node_ptr->board, start_pos, obcolor, affected_list);
/*如果是终局状态，则返回状态估值函数的值*/
if(!num)
{
/*如果已方PASS但没到棋局结束,要扣分*/
node_ptr->value = sample_calc_board_status(&node_ptr->board, computer_side);
/*如果双方都没棋下*/
if(!find_move(&node_ptr->board, 11, ~obcolor&0x03, affected_list))
return;
if(obcolor == computer_side)
{
node_ptr->value -= 10;
return;
}
node_ptr->value += 10;
return;
}
/*初始化回溯值*/
node_ptr->value = (obcolor == computer_side)? -INITIAL_VALUE : INITIAL_VALUE;
memcpy(&childnode.board, &node_ptr->board, sizeof(board_type));
while(num)
{
while(num--)
childnode.board.board[0][affected_list[num]] = obcolor;
/*递归计算部分回溯值*/
UINT8 depth = cur_depth;
extend_node_two(&childnode, node_ptr, (~obcolor)&0x03);
cur_depth = depth;
/*如果此结点是棋手一方，则部分回溯值是子结点中最大的一个*/
if(obcolor == computer_side)
{
if(childnode.value > node_ptr->value)
{
node_ptr->value = childnode.value;
node_ptr->movepos = affected_list[0];
}
}
/*如果是对手一方，部分回溯值是子结点中最小的一个*/
else
{
if(childnode.value < node_ptr->value)
{
node_ptr->value = childnode.value;
node_ptr->movepos = affected_list[0];
}
}
/* α-β裁减的判断 在考虑轮到棋手下棋的一个亲节点及轮到对手下棋的一个子节点时，
如果该子节点的数值已经小于或等于其亲节点的回溯值，
那么就不需要对该节点或者其后续节点做更多的处理了。
计算的过程可以直接返回到亲节点上。
*/
/*在考虑轮到对手下棋的一个亲节点及轮到棋手下棋的一个子节点时，
如果该子节点的部分回溯值已经大于或等于其亲节点的部分回溯值，
那么就不需要对该子节点或者其后裔节点做更多的处理了。
计算过程可以直接返回到亲节点上。*/
if(parent_ptr)
{
if(obcolor != computer_side)
{
/*α裁减*/
if(node_ptr->value <= parent_ptr->value)
return;
}
else
{
/*β裁减*/
if(node_ptr->value >= parent_ptr->value)
return ;
}
}
/*找到下一个可落子的点*/
start_pos = affected_list[0]+1;
memcpy(&childnode.board, &node_ptr->board, sizeof(board_type));
num = find_move(&childnode.board, start_pos, obcolor, affected_list);
}
return;
}
void get_chess_score(board_type *board_ptr, UINT16 &iWscore, UINT16 &iBscore)
{
iWscore =0; iBscore =0;
for(INT16 i=1; i<=BOARD_ROWS; i++)
for(INT16 j=1; j<=BOARD_COLS; j++)
{
if(board_ptr->board[i][j] == CHESS_BLACK)
iBscore++;
else if(board_ptr->board[i][j] == CHESS_WHITE)
iWscore++;
}
}
void game_over(board_type *board_ptr, HWND hwnd)
{
UINT16 wscore, bscore;
char strcomwin[]="虽然你很历害,但我还是赢了你!";
char struserwin[]="让你一次,下次你可没这么走运了!";
char strdogfall[]="我没好好下,你才有机会平局!";
char *text;
get_chess_score(board_ptr, wscore, bscore);
g_bStart = 0;
if(computer_side == CHESS_WHITE)
{
if(wscore > bscore)
{
text = strcomwin;
}
else if(wscore <bscore)
{
text = struserwin;
}
else
{
text = strdogfall;
}
}
else
{
if(wscore > bscore)
text = struserwin;
else if(wscore <bscore)
text = strcomwin;
else text = strdogfall;
}
MessageBox(hwnd, text, "黑白棋", MB_OK|MB_ICONINFORMATION);
}
void computer_play(board_type *board_ptr, HWND hwnd)
{
cur_depth =0;
tree_node_type node;
INT16 affected_list[MAX_AFFECTED_PIECES];
start:
memcpy(&node.board, board_ptr, sizeof(board_type));
node.movepos =0;
if(cur_step>= STEP_MONMENT2)
{
extend_node_two(&node, NULL, computer_side);
}
else if(cur_step > STEP_MONMENT1)
{
max_depth = depth2[g_iGameLevel];
extend_node_one(&node, NULL, computer_side);
}
else
{
max_depth = depth1[g_iGameLevel];
extend_node_one(&node, NULL, computer_side);
}
if(!do_move_chess(board_ptr, node.movepos, computer_side, hwnd))
{
if(!find_move(board_ptr, 11, (~computer_side)&0x03, affected_list))
{
game_over(board_ptr, hwnd);
return;
}
else
{
MessageBox(hwnd,"我没棋下了,你再走一步!", "黑白棋", MB_OK|MB_ICONINFORMATION);
return;
}
}
else
{
if(!find_move(board_ptr, 11, (~computer_side)&0x03, affected_list))
{
if(!find_move(board_ptr, 11, computer_side, affected_list))
{
game_over(board_ptr, hwnd);
return;
}
else
{
MessageBox(hwnd ,"你没棋下了,我再走一步!", "黑白棋", MB_OK|MB_ICONINFORMATION);
goto start;
}
}
}
}
UINT8 do_move_chess(board_type *board_ptr, UINT16 movepos, UINT8 obcolor, HWND hwnd)
{
INT16 affected_list[MAX_AFFECTED_PIECES];
INT16 num = find_move(board_ptr, movepos, obcolor, affected_list);
if(!num || affected_list[0] != movepos)
return 0;
for(int i=0; i<num; i++)
{
board_ptr->board[0][affected_list[i]] = obcolor;
if(hwnd)
::SendMessage(hwnd, WM_TRANCHESS, WPARAM(affected_list[i]),LPARAM(i<<16|obcolor));
}
step_array[cur_step++] = movepos;
return 1; |
