Contents
1.游戏图文说明
这个游戏是这样玩的:
开始有两堆石子,第一堆有2个,第二堆有1个,开始是玩家1开始取石子,然后是玩家2取石子,规则是只能取某一堆的至少一颗石子,两人轮流取石子,直到有人取完石子,谁就输了。
上图列出了游戏的所有可能:
假设玩家1取了第一堆中的一颗石子,那么在接下来的回合,玩家2无论取第一堆或者第二堆石子中的一颗,那么玩家1都将会输掉这个比赛。玩家1正确的做法就是取走第一堆的两颗石子,这样就赢了。当然如果玩家1取走第二堆中的石子,除非玩家2脑残地取走了第一堆中的2颗石子,玩家1将会输掉这个比赛。
先好好理解下上面所说的,看起来很简单,我们这次的目的是要创建一个电脑对手,它必须知道所有的游戏可能,它必须足够聪明,让玩家头痛。
2.用程序模拟比赛所有可能
2.1创建一个树的数据结构来存储所有结果
把上面实体的所有比赛过程可以转换成一个树的数据结构。我们需要存储所有的可能。当我们像上面的情况2,1时,有11种情况,然而如果是有4堆石子,它们数量分别是4,2,2,2的情况,总共有228291种情况,计算时间要12秒!真令人吃惊。可能是我写的算法太垃圾。
首先我们创建一个Rocks的类表示每一堆。有两个属性,一个是堆的索引,表示第几堆,另一个表示堆里石子的数量。
class Rocks{ public: friend bool operator == (const Rocks& p1,const Rocks& p2); Rocks(const int& Index,const int& Count){ m_index = Index; m_count = Count; } int GetIndex() const{ return m_index; } void SetIndex(const int& Index){ m_index = Index; } int GetCount()const{ return m_count; } void SetCount(const int& Count){ m_count = Count; } private: int m_index,m_count; }; bool operator == (const Rocks& p1,const Rocks& p2){ return (p1.GetCount() == p2.GetCount() && p1.GetIndex() == p2.GetIndex()); }
然后建立一个Node的类,它就是图中树的每个节点。它有多个孩子,有父节点。 有每一堆石子的状态。
//一个node就是一种游戏状态,一个树的节点 class Node{ friend Tree; public: Node(const vector<Rocks>& Rocks){ m_rocks = Rocks; parent = 0; m_win = -1; } vector<Rocks> GetRocks()const{ return m_rocks; } int GetHeight(){ int height = 0; Node *currentNode = this; while(currentNode->parent != NULL){ ++height; currentNode = currentNode->parent; } return height; } int GetWin()const{ return m_win; } void SetWin(const int& Win){ m_win = Win; } vector<Node*> GetChildren(){ return children; } private: vector<Rocks> m_rocks; //每一堆石子的数量 Node* parent; //它有父节点 vector<Node*> children; //它有多个孩子节点 int m_win; //对玩家来说是否是一个赢的状态 };
接下来建立Tree类。
class Tree{ public: Tree(){root = 0;} ~Tree(); Tree(const vector<Rocks>& p); //构造函数,参数是初始石子堆 void BuildMinimaxTree(Node* node); //递归方式创建树 void BuildMinimaxTree(); //非递归方式创建树 Node* GetCurrentNode(); //得到当前所在节点,即游戏玩到哪一步了 void SetCurrentNode(Node* node); //设置当前节点 bool ChangeCurrentNode(const Rocks& p); //更改节点因为玩家或者电脑做出选择了 void ComputerChooseNode(); //电脑做出选择 void Minimax(Node* node); //对树进行统计,看下每个节点对玩家是否有利 int GetCountChoice(){ //得到所有Node的数量 return countChoice; } Node* GetRoot()const{ //得到根节点 return root; } private: Node* root; //根节点 Node* current; //当前节点 int countChoice; //总的Node的数量,只是用来看下树总共有几个孩子 };
2.2 第一个难点,如何创建树?
类写的差不多,到了第一个难点,如何创建一个树?一般创建用递归方式,根节点每堆石子少一个石子就是一个新的结果,它们就是根节点的孩子节点,在对孩子节点也同样处理,直到没有节点可处理,树就出来了。
//use recursion void Tree::BuildMinimaxTree(Node* node){ if(node){ vector<Rocks> p = node->m_rocks; //对所有堆进行遍历,每堆减少一个石子即为一个新的结果 for(vector<Rocks>::iterator itr = p.begin();itr != p.end(); ++itr){ int saveCount, count; saveCount = count = itr->GetCount(); while(count > 0){//至少还有一个石子 itr->SetCount(--count);//每次少一个石子 Node* newNode = new Node(p);//got new child ++countChoice;//只是用来计数 newNode->parent = node; node->children.push_back(newNode); BuildMinimaxTree(newNode);//build it's child as a tree } itr->SetCount(saveCount); } } } tree.BuildMinimaxTree(tree.GetRoot());
还有一种方式是用双端队列deque来处理,弄过寻路算法的童鞋就知道了。先把根节点加入队列,把它孩子都加入到队列尾部,然后剔除头部,再对刚刚加入的第一个孩子进行这样处理,处理完,剔除。这样一直做下去直到队列为空,树就出来了。
理论上这种没有使用递归的方式会快点的,但在这程序里好像并不明显。
//use deque void Tree::BuildMinimaxTree(){ deque<Node*> allNode; allNode.push_back(root);//先加入根节点 while(allNode.size() > 0){ Node* currentNode = allNode.front();//对头部的节点进行处理,把他的孩子都加入到队列的尾部,再剔除头部 vector<Rocks> p = currentNode->GetRocks(); for(vector<Rocks>::iterator itr = p.begin(); itr != p.end(); ++itr){ int saveCount, count; saveCount = count = itr->GetCount(); while(count > 0){ itr->SetCount(--count); Node *newNode = new Node(p); ++countChoice;//只是用来计数 newNode->parent = currentNode; currentNode->children.push_back(newNode); allNode.push_back(newNode);//把他的孩子都加入到队列的尾部 } itr->SetCount(saveCount); } allNode.pop_front();//再剔除头部 } }
2.3 第二个难点,当前节点是否对玩家有利?
每一个节点我们还有一个属性来标识是否对玩家有利,有利表示1,失利表示0,这个是我们根据石子堆2,1,1统计出的树。主要有3点。
- 先看最末端节点,如果是电脑结束游戏,那么玩家就输了,是玩家拿完最后一颗石子。
- 再看最右边,是如何得出1的呢?因为是玩家回合,只要有一个孩子是1,它就是1,因为有一个结果对玩家有利,理论上玩家就会选择这个
- 再看最左边的,因为是电脑回合,所以只有他的所有孩子都是1,它才是1,如果有一个是0,电脑就会选择它了,玩家就输了,看下这个节点的兄弟节点都是0。
代码是这样的,再次用了递归,速度非常慢。
void Tree::Minimax(Node* node){ vector<Node*> n = node->children; int childrenSize = n.size(); if(childrenSize == 0){ node->SetWin(node->GetHeight() % 2 == 0 ? 1 : 0); }else{ int totalChildrenWin = 0; for(int i = 0; i != childrenSize; ++i){//add all child's win totalChildrenWin += n[i]->GetWin(); } //if the node's win is -1 and all it's child's win is -1,after calculate //it's child's win and calculate it's win if(node->GetWin() == -1 && totalChildrenWin == -(childrenSize)){ for(int j = 0; j < childrenSize; ++j){ Minimax(n[j]); } Minimax(node); }else{ bool isMyTurn = node->GetHeight() % 2 == 0 ? true : false; if(isMyTurn){//if is my turn, one child's win is 1, I will choose the child,so I will win. totalChildrenWin > 0 ? node->SetWin(1):node->SetWin(0); }else{//if is not my turn, all child's win is 1,I will win totalChildrenWin == childrenSize ?node->SetWin(1):node->SetWin(0); } } } }
其他还有一些代码就没列出来了,比如电脑的选择,电脑肯定会选择0的节点让玩家输,但是如果没有0的节点可以选,它会随机选择一个节点。还有代码也没有对用户输入的值进行合法验证。
3.游戏截图
4.整个项目代码下载:
http://www.waitingfy.com/?attachment_id=719
http://www.waitingfy.com/?p=725
5.游戏规则参考:
《Data Structures For Game Programmers》
Tags: 小游戏
725