首页 > 代码库 > 游戏开发(三)——WIN32 黑白棋(二)——AI

游戏开发(三)——WIN32 黑白棋(二)——AI

今天是第二部分:玩家和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;
}