今天是第二部分:玩家和AI
玩家主要是实现悔棋的功能
AI主要是搜索、最大最小算法,枝剪算法
1、每一步落子的步骤,为了可以悔棋
typedef struct ReversiStep { ReversiBitBoard m_LastMap; ReversiStep& operator= (const ReversiStep& 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)。如下表:
const int g_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" typedef struct ReversiStep { ReversiBitBoard m_LastMap; ReversiStep& operator= (const ReversiStep& temp) { m_LastMap = temp.m_LastMap; return *this; } }ReversiStep; class ReversiPlayer { public: void Init(EnumReversiPiecesType type); void Play(ReversiBitBoard& reversi, char row_y, char column_x); void Cancel(ReversiBitBoard& reversi); EnumReversiPiecesType GetPlayerType(); private: void AddReversiStep(ReversiBitBoard& reversi); EnumReversiPiecesType m_PlayerType; TBDLinkList<ReversiStep> m_ReversiStepList; TObjectPool<TBDLinker<ReversiStep>> m_ReversiStepPool; }; #endif
ReversiPlayer.cpp
#include "ReversiPlayer.h" void ReversiPlayer::Init(EnumReversiPiecesType type) { m_PlayerType = type; m_ReversiStepList.Init(enum_DisableLock); m_ReversiStepPool.Init(REVERSI_MAX_ROW * REVERSI_MAX_COLUMN, 0, enum_DisableLock_ObjPool, enum_DisableAssign_ObjPool); } void ReversiPlayer::Play(ReversiBitBoard& reversi, char row_y, char column_x) { AddReversiStep(reversi); reversi.SetPieces(m_PlayerType, row_y, column_x); reversi.DoReversi(m_PlayerType, row_y, column_x); reversi.SwapPlayer(); } EnumReversiPiecesType ReversiPlayer::GetPlayerType() { return m_PlayerType; } void ReversiPlayer::AddReversiStep(ReversiBitBoard& reversi) { TBDLinker<ReversiStep> *pLinker = m_ReversiStepPool.Malloc(); if (NULL != pLinker) { pLinker->m_Value.m_LastMap = reversi; pLinker->m_pLinkList = NULL; m_ReversiStepList.PushTail(pLinker); } } void ReversiPlayer::Cancel(ReversiBitBoard& reversi) { TBDLinker<ReversiStep> *pLinker = m_ReversiStepList.PopTail(); if (NULL != pLinker) { reversi = pLinker->m_Value.m_LastMap; m_ReversiStepPool.Free(pLinker); } }
ReversiAI.h
#ifndef _ReversiAI_h_ #define _ReversiAI_h_ #include "TObjectPool.h" #include "tool.h" #include "ReversiCommon.h" #include "ReversiPoint.h" #include "ReversiBitBoard.h" const int MAX_DEPTH = 9; const int MAX_WEIGHT = MY_MAX_INT; const int MIN_WEIGHT = MY_MIN_INT; typedef struct ReversiAIRecord { EnumReversiPiecesType m_type; // 当前落子方 ReversiPoint m_point; // 当前落子方的落子位置 ReversiBitBoard m_resultboard; // 当前落子方的落子结果(棋盘状态) int m_weight; // 当前落子方的落子权值 // 若为玩家,权值为负,若为AI,权值为正 void SetRecord(EnumReversiPiecesType type, char row_y, char column_x, ReversiBitBoard& lastboard); }ReversiAIRecord; class ReversiAI { public: void Init(EnumReversiPiecesType type); void Play(ReversiBitBoard& reversi); EnumReversiPiecesType GetPlayerType(); private: int Find(ReversiBitBoard& lastReversi, int lastWeight, int lastDepth, EnumReversiPiecesType lastType); EnumReversiPiecesType m_AIType; TObjectPool<ReversiAIRecord> m_ReversiAIRecordPool; }; #endif
ReversiAI.cpp
#include "ReversiAI.h" void ReversiAIRecord::SetRecord(EnumReversiPiecesType type, char row_y, char column_x, ReversiBitBoard& lastboard) { m_type = type; m_point.m_row_y = row_y; m_point.m_column_x = column_x; m_resultboard = lastboard; m_resultboard.SetPieces(m_type, m_point.m_row_y, m_point.m_column_x); m_resultboard.DoReversi(m_type, m_point.m_row_y, m_point.m_column_x); m_weight = 0; } void ReversiAI::Init(EnumReversiPiecesType type) { m_AIType = type; m_ReversiAIRecordPool.Init(100, 100, enum_DisableLock_ObjPool, enum_DisableAssign_ObjPool); } void ReversiAI::Play(ReversiBitBoard& reversi) { int currWeight = MIN_WEIGHT; ReversiPoint currPoint = {-1, -1}; int i = 0; for (; i < 4; i++) { if (reversi.CanPlay(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 (!currPoint.IsValid()) { for (; i < REVERSI_MAX_ROW * REVERSI_MAX_COLUMN - 4; i++) { if (reversi.CanPlay(m_AIType, g_WeightOrder[i][0], g_WeightOrder[i][1])) { ReversiAIRecord *currRecord = m_ReversiAIRecordPool.Malloc(); if (NULL != currRecord) { currRecord->SetRecord(m_AIType, g_WeightOrder[i][0], g_WeightOrder[i][1], reversi); int weight1 = g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]]; int weight2 = 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; } else if (currRecord->m_weight == currWeight) { if (!currPoint.IsValid()) { currWeight = currRecord->m_weight; currPoint = currRecord->m_point; } } m_ReversiAIRecordPool.Free(currRecord); } } } } if (currPoint.IsValid()) { reversi.SetPieces(m_AIType, currPoint.m_row_y, currPoint.m_column_x); reversi.DoReversi(m_AIType, currPoint.m_row_y, currPoint.m_column_x); } reversi.SwapPlayer(); } int ReversiAI::Find(ReversiBitBoard& lastReversi, int lastWeight, int lastDepth, EnumReversiPiecesType lastType) { EnumReversiPiecesType currType = SwapType(lastType); int currDepth = lastDepth + 1; int currWeight = 0; if (currType == m_AIType) { currWeight = MIN_WEIGHT; } else { currWeight = MAX_WEIGHT; } int i = 0; for (; i < 4; i++) { if (lastReversi.CanPlay(currType, g_WeightOrder[i][0], g_WeightOrder[i][1])) { if (currType == m_AIType) { return g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]]; } else { return -g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]]; } } } for (; i < REVERSI_MAX_ROW * REVERSI_MAX_COLUMN - 4; i++) { if (lastReversi.CanPlay(currType, g_WeightOrder[i][0], g_WeightOrder[i][1])) { ReversiAIRecord *currRecord = m_ReversiAIRecordPool.Malloc(); if (NULL != currRecord) { currRecord->SetRecord(currType, g_WeightOrder[i][0], g_WeightOrder[i][1], lastReversi); int weight1 = 0; int weight2 = 0; if (currType == m_AIType) { weight1 = g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]]; } else { weight1 = -g_Weight[g_WeightOrder[i][0]][g_WeightOrder[i][1]]; } if (currDepth == MAX_DEPTH) { weight2 = 0; } else { 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_ReversiAIRecordPool.Free(currRecord); break; } } } else { if (currRecord->m_weight < currWeight) { currWeight = currRecord->m_weight; if (currRecord->m_weight < lastWeight) { m_ReversiAIRecordPool.Free(currRecord); break; } } } m_ReversiAIRecordPool.Free(currRecord); } } } return currWeight; } EnumReversiPiecesType ReversiAI::GetPlayerType() { return m_AIType; }