C++ 取石子游戏

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. 先看最末端节点,如果是电脑结束游戏,那么玩家就输了,是玩家拿完最后一颗石子。
  2. 再看最右边,是如何得出1的呢?因为是玩家回合,只要有一个孩子是1,它就是1,因为有一个结果对玩家有利,理论上玩家就会选择这个
  3. 再看最左边的,因为是电脑回合,所以只有他的所有孩子都是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

Leave a Reply

Name and Email Address are required fields.
Your email will not be published or shared with third parties.