游戏开发（三）——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 
行动力：
也就是说你当前有多少个可以落子的位置。

上面在估值表中说到，要自己抢占有利的位置，并逼迫对方落子到不利的位置上。所以有一个行动力的概念。
（有一句话叫走自己的路，让别人无路可走，就是这个道理。）

为了使自己抢占有利的位置，那么自己的可以落子的位置就要尽可能的多，这样自己才可以选择最有利的那个位置。
（棋盘总共只有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之间的最终结果是
而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 m_ReversiStepList;
	TObjectPool> 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 *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 *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 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 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 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 m_weight;

						if (currRecord->m_weight 

游戏开发（三）——WIN32 黑白棋（二）——AI,搜素材,soscw.com
游戏开发（三）——WIN32 黑白棋（二）——AI
标签：游戏设计   win32   黑白棋   游戏开发   ai   
原文地址：http://blog.csdn.net/zilaishuichina/article/details/38397705