黑白棋规则

游戏开发（三）——WIN32⿊⽩棋（⼆）——AI

整个游戏分3部分介绍。

今天是第⼆部分：玩家和AI

玩家主要是实现悔棋的功能

AI主要是搜索、最⼤最⼩算法，枝剪算法

1、每⼀步落⼦的步骤，为了可以悔棋

typedefstructReversiStep

{

ReversiBitBoardm_LastMap;

ReversiStep&operator=(constReversiStep&temp)

{

m_LastMap=temp.m_LastMap;

return*this;

}

}ReversiStep;

这⾥直接记录落⼦之前的棋盘状态（这⼀步轮到谁落⼦已经记录在ReversiBitBoard⾥⾯），悔棋的时候就是恢复棋盘状态到这个⼈落⼦之

前的状态，然后仍然由该玩家重新落⼦。

落⼦的时候，填⼀下ReversiStep，存⼊，悔棋的时候，从链表尾退出⼀个节点，并将棋盘状态恢复为这个尾节点的状态，即实现了悔棋。

⼀盘棋总共60步下满，这⾥⽤了⼀个，⼀次性申请好60步所需内存，这样避免在频繁的落⼦悔棋的过程中，频繁的申请内存。

悔棋其实很简单，很好实现，下⾯是关键：AI怎么做。

2、AI

关于⿊⽩棋的AI，据本⼈了解，⼤致是分两⼤种：

第⼀种：是模板实现的（不是C++的模板啊），是棋局的模板。

简单来说，就是对⼤量的棋局，棋谱，进⾏分析。找出，下哪⼀个位置，形成⼀个什么样的局⾯，是优势，还是劣势。然后给不同的局⾯打

个分数。

AI下棋的时候，分别看下每个位置，能形成模板库⾥⾯的哪⼀种局⾯，得到什么样的分数，来判断这⼀步是好棋，还是坏棋，要不要落在这

个位置上。

（当然，笔者⼿上就没有这⼤量的可供分析的棋谱去研究了，这⾥最终也没有采⽤这种⽅法）

第⼆种：就是实时分析的。

也就是每⼀步落⼦之前，现场搜索⼀下，看本⽅可以有哪些位置可以落⼦的。然后，不同的位置是优势还是劣势，可以得多少分；

分别落在这些位置之后，对⽅接着可以落⼦在哪些位置上，对⽅分别可以得多少分，

然后循环反复，搜索到后⾯的若⼲步。

然后综合评估⼀下看当前落⼦什么位置最好，可以让本⽅获得的优势尽可能的⼤，对⽅获得的优势尽可能的⼩。

这⾥就涉及到⼀个估值函数的问题：怎么样算优势，怎么样算劣势？

估值表：

对棋盘的64个位置按经验做⼀下估值，初步判断⼀下哪些位置要抢占的，哪些位置是要诱使（或者逼迫）对⽅占领，即对⽅除了下这个

点，别⽆选择

⽐如上图：

像1A这个位置，如果你占了之后，对⽅是⽆论如何也不能把这个位置翻转掉的（下⾯会提到这样的位置叫确定⼦），所以如果你能占这个

位置，这个位置就肯定就是你的了，不会被吃掉，所以要尽可能的占像1A这样的4个⾓的位置。

像1B，2A，2B，这样的位置，如果你占了之后，对⽅就能很容易的占⾓，所以要尽量避免占这样的位置（这样的位置有12个）。除⾮迫

不得已⽆⼦可下，没有其他更好的位置了。

按照这样的经验，我们给如上的棋盘设定⼀个估值表，不同的位置有不同的值，4个⾓深绿⾊表⽰的位置，得分是最⾼的（这⾥给的是

0x01000000），像1B，2A，2B这样的红⾊表⽰的位置，得分就是最低的（这⾥给的是0x00000001）。如下表：

constintg_Weight[REVERSI_MAX_ROW][REVERSI_MAX_COLUMN]={

{0x1<<24,0x1,0x1<<20,0x1<<16,0x1<<16,0x1<<20,0x1,0x1<<24},

{0x1,0x1,0x1<<16,0x1<<4,0x1<<4,0x1<<16,0x1,0x1},

{0x1<<20,0x1<<16,0x1<<12,0x1<<8,0x1<<8,0x1<<12,0x1<<16,0x1<<20},

{0x1<<16,0x1<<4,0x1<<8,0,0,0x1<<8,0x1<<4,0x1<<16},

{0x1<<16,0x1<<4,0x1<<8,0,0,0x1<<8,0x1<<4,0x1<<16},

{0x1<<20,0x1<<16,0x1<<12,0x1<<8,0x1<<8,0x1<<12,0x1<<16,0x1<<20},

{0x1,0x1,0x1<<16,0x1<<4,0x1<<4,0x1<<16,0x1,0x1},

{0x1<<24,0x1,0x1<<20,0x1<<16,0x1<<16,0x1<<20,0x1,0x1<<24}

};

⾏动⼒：

也就是说你当前有多少个可以落⼦的位置。

上⾯在估值表中说到，要⾃⼰抢占有利的位置，并逼迫对⽅落⼦到不利的位置上。所以有⼀个⾏动⼒的概念。

（有⼀句话叫⾛⾃⼰的路，让别⼈⽆路可⾛，就是这个道理。）

为了使⾃⼰抢占有利的位置，那么⾃⼰的可以落⼦的位置就要尽可能的多，这样⾃⼰才可以选择最有利的那个位置。

（棋盘总共只有60个位置可以落⼦，你能下得位置尽可能的多了，对⽅能下的位置就尽可能的少了，这就叫⾛别⼈的路。）

要让对⽅可以落⼦的位置尽可能的少，这样才能逼迫对⽅⾛到不想下这个位置，但是不得不下的位置上去。

（这就叫让别⼈⽆路可⾛。）

当然这⾥有存在特殊的情况，⽐如⾃⼰这⽅有3个位置可以落⼦，但是都是⼀些不痛不痒的地⽅，对⽅只有1个位置可以落⼦，但是却是占

⾓。

所以⾏动⼒要和估值表配合起来使⽤，简单的⽅法就是：要让对⽅的⾛棋位置，每⼀步对应的估值表的权值，的总和，尽可能的⼩，⼰⽅的

总和尽可能的⼤。

⽐如⾃⼰这⽅有3步可以⾛，分别得分是5，10，15分，对⽅只有1步可以⾛，得分是100分。那么肯定优先不考虑这种⽅案。

确定⼦：

也有翻译成稳定⼦的。

⿊⽩棋的规则就是本⽅俩⼦之间夹住的对⽅棋⼦，可以被翻转。⽽确定⼦，就是对⽅⽆论如何，不管怎么⾛棋，都不可能翻转掉的棋⼦。

显然，4个⾓就是确定⼦

再⽐如下图：

上图中所有⽩⼦全部为确定⼦。

当⼀⽅确定⼦个数达到33个，则必定胜利。

还有各种概念，墙，平衡⼦，内⼦，外⼦，等等，这⾥就不⼀⼀介绍了。有兴趣的可以baidu⼀下《⿊⽩棋指南》

本⽂实现的AI就是按照估值表来搜。

但是由于搜素的步数是按指数增长的。本⼈机器上不会感觉到卡顿的最⼤步数⼤约是9步，10步⼤概就要卡个1，2秒钟了。

所以也不可能每⼀种情况都搜，要做⼀些枝剪

对于每⼀步的搜索：

⾸先看能不能占⾓，能占⾓，当前分⽀就不继续往下搜了（即使没有搜到最⼤深度，也不继续了），开始搜上⼀步的其他可能的落⼦位置。

（这其实就是⼀个提前按经验做的枝剪）。

其次就是最⼤最⼩搜索算法：

这⾥假设AI的对⼿都是最聪明的，会选择最优解，即会选择对AI最不利的选择。

那么：

搜出来的结果集是AI⽅的结果，那么要选择最终得分最⾼的那个位置

搜出来的结果集是玩家⽅的结果，那么要选择最终得分最低的那个位置。

如下图

假设圆形代表的是AI节点，⽅形代表玩家节点。

对于A2和A3这两种选择，AI显然是选择A2得10分。对于A4和A4这两种选择，AI显然是选择A4得20分。

但是对于B1，B2来说，玩家如果下B2，使得AI可以得20分，下B1，使得AI只能得10分，那么玩家显然是下B1。

所以最终A1这⼀步，AI只能得10分。这就是最⼤最⼩算法。

然后就是α-β枝剪：

现在A2，A3已经选出最⼤值10，B1的得分是10分。

⽽对于B1，B2来说是要选最⼩值，既然B1的得分是10分，则B1，B2之间的最终结果是<=10的。

⽽A4的得分是20分，对于A4，A5来说是选择最⼤值得，即A4，A5之间的最终结果是>=20的，说明B2的最终结果是>=20的。

那么这种情况下肯定是选B1了，对于还没有搜索的A5节点来说，已经影响不到最终的选择结果了，所以就可以不⽤考虑了。

这就是枝剪。

然后得分的计算：

这⾥每⼀步的得分，都是相对于AI来说的得分。

AI⾃⼰落⼦某⼀个位置，得⼀个正分，之后对⼿落⼦某⼀个位置，所得的分数对于AI来说就是⼀个负分（即玩家取得的优势，对于AI来说就

是劣势）。

对于已经搜到最⼤深度的节点来说，它的得分就是这个位置的本⾝得分（因为后⾯已经不搜了）。

⽽对于中途节点来说，它的得分应该是这个位置的本⾝得分，加上下⼀步对⽅的选择结果的得分。这⾥不能只以最后⼀步的结果逆推的。

举个例⼦：

如上图的左右两种情况。

假设圆形代表的是AI节点，⽅形代表玩家节点。

其中分值表⽰的是节点⾃⾝落⼦该位置所获得的在估值表中的得分。玩家节点取负分。

如果只是⽤最深层的节点的得分，来计算最上层的节点的得分，那么按照上⾯最⼤最⼩算法，AI最后的得分：左边是10分，右边是5分。那

么AI选择左边的10分这种情况。

但是却造成了中间过程中，玩家可以得到50分的这样⼀个相对来说是⽐较好的分值。

⽽AI应该不让玩家取得这样⼀个⽐较好的优势。

所以要综合前后对⽅的落⼦位置以及得分来考虑最终得分：

AI最后的得分：左边是-30分，右边是-15分。最终选择为右边，⽽不是左边。

好了，基本的AI就这些。虽然只是⼀个很简单的AI，下赢笔者是⽐较轻松的了。

下⾯给出具体的代码

ReversiPlayer.h

#ifndef_ReversiPlayer_h_

#define_ReversiPlayer_h_

#include"TBDLinkList.h"

#include"TObjectPool.h"

#include"ReversiCommon.h"

#include"ReversiBitBoard.h"

typedefstructReversiStep

{

ReversiBitBoardm_LastMap;

ReversiStep&operator=(constReversiStep&temp)

{

m_LastMap=temp.m_LastMap;

return*this;

}

}ReversiStep;

classReversiPlayer

{

public:

voidInit(EnumReversiPiecesTypetype);

voidPlay(ReversiBitBoard&reversi,charrow_y,charcolumn_x);

voidCancel(ReversiBitBoard&reversi);

EnumReversiPiecesTypeGetPlayerType();

private:

voidAddReversiStep(ReversiBitBoard&reversi);

EnumReversiPiecesTypem_PlayerType;

TBDLinkListm_ReversiStepList;

TObjectPool>m_ReversiStepPool;

};

#endif

#include"ReversiPlayer.h"

voidReversiPlayer::Init(EnumReversiPiecesTypetype)

{

m_PlayerType=type;

m_(enum_DisableLock);

m_(REVERSI_MAX_ROW*REVERSI_MAX_COLUMN,

0,

enum_DisableLock_ObjPool,

enum_DisableAssign_ObjPool);

}

voidReversiPlayer::Play(ReversiBitBoard&reversi,charrow_y,charcolumn_x)

{

AddReversiStep(reversi);

ces(m_PlayerType,row_y,column_x);

rsi(m_PlayerType,row_y,column_x);

ayer();

}

EnumReversiPiecesTypeReversiPlayer::GetPlayerType()

{

returnm_PlayerType;

}

voidReversiPlayer::AddReversiStep(ReversiBitBoard&reversi)

{

TBDLinker*pLinker=m_();

if(NULL!=pLinker)

{

pLinker->m_Value.m_LastMap=reversi;

pLinker->m_pLinkList=NULL;

m_il(pLinker);

}

}

voidReversiPlayer::Cancel(ReversiBitBoard&reversi)

{

TBDLinker*pLinker=m_l();

if(NULL!=pLinker)

{

reversi=pLinker->m_Value.m_LastMap;

m_(pLinker);

}

}

ReversiAI.h

#ifndef_ReversiAI_h_

#define_ReversiAI_h_

#include"TObjectPool.h"

#include"tool.h"

#include"ReversiCommon.h"

#include"ReversiPoint.h"

#include"ReversiBitBoard.h"

constintMAX_DEPTH=9;

constintMAX_WEIGHT=MY_MAX_INT;

constintMIN_WEIGHT=MY_MIN_INT;

typedefstructReversiAIRecord

{

EnumReversiPiecesTypem_type;//当前落⼦⽅

ReversiPointm_point;//当前落⼦⽅的落⼦位置

ReversiBitBoardm_resultboard;//当前落⼦⽅的落⼦结果（棋盘状态）

intm_weight;//当前落⼦⽅的落⼦权值

//若为玩家，权值为负，若为AI，权值为正

voidSetRecord(EnumReversiPiecesTypetype,

charrow_y,charcolumn_x,

ReversiBitBoard&lastboard);

}ReversiAIRecord;

classReversiAI

{

public:

voidInit(EnumReversiPiecesTypetype);

voidPlay(ReversiBitBoard&reversi);

EnumReversiPiecesTypeGetPlayerType();

private:

intFind(ReversiBitBoard&lastReversi,

intlastWeight,

intlastDepth,

EnumReversiPiecesTypelastType);

EnumReversiPiecesTypem_AIType;

TObjectPoolm_ReversiAIRecordPool;

};

#endif

#include"ReversiAI.h"

voidReversiAIRecord::SetRecord(EnumReversiPiecesTypetype,

charrow_y,charcolumn_x,

ReversiBitBoard&lastboard)

{

m_type=type;

m_type=type;

m_point.m_row_y=row_y;

m_point.m_column_x=column_x;

m_resultboard=lastboard;

m_ces(m_type,m_point.m_row_y,m_point.m_column_x);

m_rsi(m_type,m_point.m_row_y,m_point.m_column_x);

m_weight=0;

}

voidReversiAI::Init(EnumReversiPiecesTypetype)

{

m_AIType=type;

m_(100,100,

enum_DisableLock_ObjPool,

enum_DisableAssign_ObjPool);

}

voidReversiAI::Play(ReversiBitBoard&reversi)

{

intcurrWeight=MIN_WEIGHT;

ReversiPointcurrPoint={-1,-1};

inti=0;

for(;i<4;i++)

{

if(y(m_AIType,g_WeightOrder[i][0],g_WeightOrder[i][1]))

{

currPoint.m_row_y=g_WeightOrder[i][0];

currPoint.m_column_x=g_WeightOrder[i][1];

break;

}

}

if(!d())

{

for(;i

{

if(y(m_AIType,g_WeightOrder[i][0],g_WeightOrder[i][1]))

{

ReversiAIRecord*currRecord=m_();

if(NULL!=currRecord)

{

currRecord->SetRecord(m_AIType,

g_WeightOrder[i][0],g_WeightOrder[i][1],

reversi);

intweight1=g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]];

intweight2=Find(currRecord->m_resultboard,currWeight,1,m_AIType);

currRecord->m_weight=weight1+weight2;

if(currRecord->m_weight>currWeight)

{

currWeight=currRecord->m_weight;

currPoint=currRecord->m_point;

}

elif(currRecord->m_weight==currWeight)

{

if(!d())

{

currWeight=currRecord->m_weight;

currPoint=currRecord->m_point;

}

}

m_(currRecord);

}

}

}

}

if(d())

{

ces(m_AIType,currPoint.m_row_y,currPoint.m_column_x);

rsi(m_AIType,currPoint.m_row_y,currPoint.m_column_x);

}

ayer();

}

intReversiAI::Find(ReversiBitBoard&lastReversi,

intlastWeight,intlastDepth,EnumReversiPiecesTypelastType)

{

EnumReversiPiecesTypecurrType=SwapType(lastType);

intcurrDepth=lastDepth+1;

intcurrWeight=0;

if(currType==m_AIType)

{

currWeight=MIN_WEIGHT;

}

el

{

currWeight=MAX_WEIGHT;

}

inti=0;

for(;i<4;i++)

{

if(y(currType,g_WeightOrder[i][0],g_WeightOrder[i][1]))

{

if(currType==m_AIType)

{

returng_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]];

}

el

{

return-g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]];

}

}

}

for(;i

{

if(y(currType,g_WeightOrder[i][0],g_WeightOrder[i][1]))

{

ReversiAIRecord*currRecord=m_();

if(NULL!=currRecord)

{

currRecord->SetRecord(currType,

g_WeightOrder[i][0],g_WeightOrder[i][1],

lastReversi);

intweight1=0;

intweight2=0;

if(currType==m_AIType)

{

weight1=g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]];

}

el

{

weight1=-g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]];

}

if(currDepth==MAX_DEPTH)

{

weight2=0;

}

el

{

weight2=Find(currRecord->m_resultboard,currWeight,currDepth,currType);

}

currRecord->m_weight=weight1+weight2;

if(currType==m_AIType)

{

if(currRecord->m_weight>currWeight)

{

currWeight=currRecord->m_weight;

if(currRecord->m_weight>lastWeight)

{

m_(currRecord);

break;

}

}

}

el

{

if(currRecord->m_weight

{

currWeight=currRecord->m_weight;

if(currRecord->m_weight

{

m_(currRecord);

break;

}

}

}

m_(currRecord);

}

}

}

returncurrWeight;

}

EnumReversiPiecesTypeReversiAI::GetPlayerType()

{

returnm_AIType;

}