用Python写一个中国象棋AI？

我本人是大二学生，对编程比较感兴趣，现在正在学习python语言，如今正在做中国象棋的项目，我已经做出了能下棋的一步，现在在对人机对战方面很感兴趣，不知道从哪里入手，有没有大神对中国象棋AI有简单的认识吗？介绍点资料或者是代码给我参考一下。多谢！回复内容：我只讲一下棋类AI一般的实现方法（或者叫传统的实现方法）：写一个象棋类AI主要包含以下四步：第一步：局面表示 -- 构成可下棋的基本元素第二步：走法生成 -- 实现下棋的规则第三步：局面评估 -- 量化一个局面的双方优劣势第四步：局面搜索 -- 让电脑具备思考的能力===========================严重分割线==============================================================严重分割线===================================除了刚才上面那个小象棋。我再举个例子：六子冲棋六子冲棋规则参考维基百科：六子沖棋====================重要补充插入START==================刚才看了一下维基百科描写的规则和我们这边民间流传的规则略有不同，以下程序是根据我们当地民间规则实现的，请参考：六子冲_百度百科====================重要补充插入 E N D ==================这个例子具体说明如何通过上述四步实现一个棋类AI。不废话，直接上原创的完整代码，注释已经很详细。（C语言）/************************************************************** = 民间六子棋(六子冲)人机博弈引擎实现与教程 =* * www.leilei.name * * by LeiLei 2010.3.2 - 2010.3.5* * * 本教程主要讲解六子冲棋的博弈引擎实现，不讲解界面实现部分。* 本教程共分四节讲解：* * 第一节：局面表示 -- 构成可下棋的基本元素 * 第二节：走法生成 -- 实现下棋的规则 * 第三节：局面评估 -- 量化一个局面的双方优劣势 * 第四节：局面搜索 -- 让电脑具备思考的能力 * * 本教程主要以便于理解为目标，不追求代码技巧，希望对写代码实践* 较少的你，会有所帮助。*//************************************************************** = 附：六子冲介绍 =* * 六子冲是流传于中国民间的一类棋类游戏。由于这个游戏对环境的* 要求不高,孩子们大都是在光滑的地面或石板上画上方格，以石子或木* 棍、草节等为棋子，并有简单的比赛规则:* * 纵横各四条直线组成一个正方形棋盘，直线相交的地方为落子点。* 开局时放子处为上下左右边线上的落子点，且不同方的子不可交叉放置。* 游戏双方着二色棋子各6个在一 个“九宫”型棋盘上进行对抗因为游戏双* 方各着6个棋子，故名“六子冲”。　棋子只能停留在棋盘上的落子点，棋* 子只能在线上移动，棋子只能移动一步(即相邻落子点)，每回合只能移* 动1个棋子。消灭对方棋子的方法只有一条，也很简单。那就是：二子打* 一子。即在棋盘上攻击方的2个棋子(2子必须相连并主动移动其中的1个)* 与被攻方的1个棋子皆处在一条直线上并相邻时，被攻方的这个棋子就被* 消灭。重复上面的步骤，保护自己的棋子并消灭对方的棋子，直到最后* 胜利。* * 开始：双方棋子数均为六颗，分列棋盘四周，见图片“六子冲开始时”。* * 吃子：行棋一方若将两颗棋子移至一排，且一头挨着对方的一颗棋时，* 则可吃子，见图片“吃子”。* * 注意：* 　　1.行棋一方若将三颗棋子移至一排，不可吃子，见图1。* 　　2.行棋一方若将两颗棋子移至一排，但一头挨着对方的两颗棋，不可* 子吃，见图2。* 　　3.行棋一方若将两颗棋子移至一排，但两头分别挨着对方的一颗棋，* 不可吃子，见图3。* 　　4.行棋一方若将两颗棋子移至一排，且一头挨着对方的一颗棋时，但* 对方的该颗棋后有我方棋，不可吃子见图4。* * 流传:* 　　 有好多民间代代相承的传统儿戏，在六七十年代仍十分盛行，80年* 代后逐渐衰落。80年代以后，由于社会生活和居住环境的变化，孩子们* 聚在一起玩耍的机会较少，又有新兴的各类现代化的高档玩具流行，这* 样的游戏则逐渐鲜为人知了。* 　　 六子冲就是其中最有代表性的一项游戏.也是当年的小孩子因陋就* 简玩的一种棋类游戏。据传，六子冲游戏源自中国古代战争的士兵阵* 型训练，后逐渐演变为一种棋类游戏。六子冲规则简单，上手容易，但* 变化无穷，是一种让人玩起来就欲罢不能的智力对抗游戏。六子冲游戏* 在上世纪主要流行于中国四川一带。* 　　 在中国山区农村流传甚广，，由于规则简单，工具可信手拈来，是* 我国乡间常见的棋类游戏。在商洛镇安，涪城等地农村流行。* 顾问：姜年檑* (以上文字摘自百度百科，参见原文请访问：* http://baike.baidu.com/view/2472074.htm)* */#include /************************************************************** = 第一节 局面表示 =** 1.1 棋子表示* * 棋子可以随便用个数字表示，可以把它定义为常量，* 但是有时候为了方便运算和转换，也应该精心挑选用哪些数字表示棋子。* 这里演示就随便选两个数字。* * (1)需要定义用来表示棋子的常量* * 如下所示： */#define STONE 3 //定义常量 石头(白色棋子)#define LEAF 7 // 树叶(黑色棋子)#define WHITE 0 // 白方用0表示#define BLACK 1 // 黑方用1表示#define NOPIECE 0 // 无棋子用0/** 1.2 棋盘表示** 我们可以用数组来表示棋盘 * 用4*4的二维数组就可以表示这个游戏的棋盘结构和棋子在棋盘上的分布了。如下(简单吧)： * int board[4][4] = { // 对应坐标：* 3, 3, 3, 3, // (0,0), (1,0), (2,0), (3,0),* 3, 0, 0, 3, // (0,1), (1,1), (2,1), (3,1),* 7, 0, 0, 7, // (0,2), (1,2), (2,2), (3,2), * 7, 7, 7, 7 // (0,3), (1,3), (2,3), (3,3),* };* * 数组下标构成的坐标表示棋子在棋盘上的位置。* 可以用0表示棋盘上无棋子。 * 我们可以用4*4的数组表示棋盘，但是为了运算方便，这里我们采用8*8的一维数组来装棋盘，效果更好。* 我们可以把棋盘放在数组的中央。* 然后我们用一个8*8的inBoard数组来标识棋盘在数组中的位置。* 棋子在棋盘上的位置，我们直接用数组下标表示。* * 所以，* (1)我们需要一个用来表示棋盘的数组 * (2)我们用一个数组来标识棋盘在数组中的位置(用来判断棋子是否在棋盘上) * (3)写几个函数来转换坐标。* * 如下所示：*///棋盘数组(带开局棋子位置)int board[64] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 7, 7, 7, 0, 0, 0, 0, 7, 0, 0, 7, 0, 0, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//用来标记棋子是否在棋盘上的数组static const int inBoard[64] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//根据棋盘的特征，我们写三个可以转换和取得棋盘坐标的函数////////////////////////////由棋盘数组下标获得棋子X坐标int getXFromLocation(int location){ return (location & 7) - 2;} //由棋盘数组下标获得棋子Y坐标int getYFromLocation(int location){ return (location >> 3) - 2;} //由棋子X坐标，Y坐标获得棋盘数组下标int getLocationFromXY(int x, int y){ return (x + 2) + (y + 2 3);}/** 1.3 当前走棋方表示* * (1)我们需要一个变量来表示当前该哪方走棋* (2)还需要一个用来改变走其方的函数changePlayer()* * 如下所示： */int currentPlayer = WHITE; //初始化为白方走棋，BLACK表示黑方走棋 void changePlayer(){ currentPlayer = 1 - currentPlayer; //改变走棋方，不是0 就是1 }/** 1.4 在棋盘上放棋子和拿走棋子 * * 有了棋盘，我们就可以在棋盘上放棋子了* * (1)所以我们还需要几个函数用来在棋盘上放棋子和拿走棋子。 * * 如下所示： *///在棋盘上放一枚棋子的函数void addPiece(int location){ //根据位置和当前走棋方添加棋子 int piece; piece = currentPlayer * 4 + 3; //由当前走棋方计算当前走棋方棋子 if(inBoard[location]){ board[location] = piece; }}//在棋盘上拿走一枚棋子的函数void delPiece(int location){ //根据位置删除棋子 if(inBoard[location]){ board[location] = NOPIECE; //NOPIECE == 0表示无棋子 }}/************************************************************** = 第二节 走法生成 =** 2.1 走法表示** 走法表示就是用一个变量来表示棋子从棋盘上哪里走到哪里。* 我们可以定义一个结构体来表示一个走法，也可以用一串数字表示。* 在本程序里，我们用一个int类型来表示一个走法，低位表示起点位* 置(的棋盘数组下标)，高位表示目的位置(的棋盘数组下标)。* * 由此，* (1)我们需要写几个函数来处理走法的起点和终点。* * 如下： *///根据走法生成走法起点位置(起点位置的棋盘数组下标)int generateMoveFrom(int move){ return move & 255;}//根据走法生成走法目的位置(目的位置的棋盘数组下标)int generateMoveTo(int move){ return move >> 8;}//由起点位置和目的位置合成走法int composeMove(int locationFrom, int locationTo){ return locationFrom + locationTo * 256;}/** 2.2 走法生成 ** 走法生成就是生成一个局面可以有哪些走法，一般是用一个函数来生成所有可能的走法。 * 生成的这些走法，我们可以保存在一个走法列表里，方面使用。* 我们可以用这个走法列表来判断一步棋是否合法，最重要的是，我们需要用这个走法列表来搜索所有可能的局面。 * 六子冲的每颗棋子都是按上下左右四个方向走，通过对棋盘数组下标的观察，我们可以用原位置的数组下标分别* 加上-8、8、-1、1四个数就分别得到往上、下、左、右四个方向走一步的位置的数组下标。所以我们用一个数组* 存储这四个数。* * (1)定义一个常量MAX_GEN_MOVES来表示最大生成的走法数* (2)我们需要声明一个数组用来保存生成的走法列表* (3)用一个数组来表示棋子可走的方向* (4)还需要写一个一次性生成所有走法的函数。*/#define MAX_GEN_MOVES 32 //这里顺便定义一个常量来表示走法的最大生成数 static int theMoves[MAX_GEN_MOVES]; //定义一个走法数组用来保存生成的所有走法，一个局面最多走法数不会超过MAX_GEN_MOVES种 static const char movesTable[4] = {-8, 8, -1, 1}; //这个数组用来表示棋子的走子方向//走法生成函数，产生一个局面的所有走法 int generateAllMoves(int *moves){ //传递一个走法列表数组指针，返回生成的所有走法 int i, from, to, genCount; int myPiece, pieceFrom, pieceTo; //走法计数器清零 genCount = 0; //获取当前走棋方标记 myPiece = currentPlayer * 4 + 3; //根据当前走棋方，确定当前走棋方棋子 //遍历棋盘找到当前走棋方棋子 for(from = 0; from 64; from++){ //取得当前位置的棋子 pieceFrom = board[from]; //1.如果找到的不是本方棋子，继续找 if(pieceFrom != myPiece){ continue; } //2.如果找到本方棋子，探测四个方向是否可走 for(i = 0; i 4; i++){ to = from + movesTable[i]; //目标位置 if(inBoard[to]){ //如果还在棋盘内 pieceTo = board[to]; //获取此位置棋子 if(pieceTo == NOPIECE){ //如果此位置无棋子，此走法可行 moves[genCount] = composeMove(from, to); //保存走法 genCount++; //计数 } } }//end for(i) }//end for(from) return genCount; //返回生成的走法数}/** 2.3 走一步棋 * * 要走一步棋很简单，我们只需要先把要走的棋子从棋盘的原位置上拿* 走，然后再把这颗棋子放在棋盘上的目标位置上。我们可以利用前面* 的addPiece()和delPiece()函数来写一个走棋函数。* * 在走一步棋之前，我们最好先判断这步棋是否符合走棋规则，以免引* 起以后的混乱，我们可以利用走法生成函数来判断一步棋是否合法。 * 有的时候为了提高效率也可以单独写一个函数判断走法是否合法。 * 在这里为了简单就用直接利用走法生成函数，生成所有走法，如果走* 法在走法列表里说明走法合法。 * * 走一步棋后往往会引发吃子，六子冲的吃子需要我们进行检查，六子* 冲的吃子不光与所走棋子有关，还与其他棋子的合作有关。* * 在下一节的局面搜索中，我们还会用到走棋函数，并且在搜索的过程* 中，我们会在棋盘上走棋，以探测未来棋局的变化和走势，为了不破* 坏当前局面，每走一步棋我们就要记录当前的走法和所吃的子，以便* 还原，所以在吃子过程中，我们需要记录吃子的位置。* * (1)写一个能在棋盘上走一步棋的函数。*//**吃子参考方案 - 检查序列法**//吃子检查序列数组static int eatSequence[2][2][4] = { {{7, 3, 3, 0},{0, 7, 3, 3}}, {{3, 7, 7, 0},{0, 3, 7, 7}}};//检查吃子的函数，无返回吃子位置部分int checkEat(int to){ int i, j, k, step, eat, check; //检查吃子专用 int pieceSequence[4]; //pieceSequence用来保存棋子序列(检查吃子时用) // 检查吃子，从上往下、从下往上、从左往右、从右往左，沿四个方向检查吃子情况 // 比如：从左往右检查，只需检查是否呈“●○○_”或“_●○○”序列(假如白方为当前方) for(i = 0; i //1. 取得焦点位置(焦点就是当前检查点) check = to; //check变量这时作为焦点位置 //2. 取得步长 step = movesTable[i]; //3. 把焦点位置往反方向移动到棋盘边上 while(inBoard[check]){ check -= step; //往反方向移动焦点 } //4. 往正方向取得棋子序列，保存在数组pieceSequence中 for(j = 0; j form += step; //往正方向移动焦点 if(inBoard[check]){ pieceSequence[j] = board[check]; } } //5. 把焦点位置再次往反方向移动到棋盘边上，以便由焦点位置根据吃子序列数组取得吃子位置 while(inBoard[check]){ check -= step; //往反方向移动焦点 } //6. 检查棋子序列是否与两个吃子序列匹配，若匹配则吃子 for(k = 0; k //6.1 初始化为有子可吃 eat = 1; //6.2 检查序列是否完全匹配 for(j = 0; j if(pieceSequence[j] != eatSequence[currentPlayer][k][j]){ eat = 0; } } //6.3 检查到序列完全匹配则，按位置吃子 if(eat == 1){ delPiece(check + step * (k + 1)); //由焦点取得吃子位置 } } }}*///能根据走法走一步棋的函数 int makeOneMove(int move, int *eatTable){ //传递一个用来保存吃子位置的数组 int i, genCount, isLegalMove, from, to; int step, focus, myPiece, oppPiece, eatCount; //吃子专用 isLegalMove = 1; //初始化走法为不合法 genCount = generateAllMoves(theMoves); //生成所有走法 //在所有走法中查找当前走法是否存在 for(i = 0; i genCount; i++){ //如果找到一个走法等于当前走法 if(theMoves[i] == move){ isLegalMove = 0; //所有走法中有此走法，说明走法合法 break; } } //1.首先判断走法是否合法 if(isLegalMove == 1){ return 0; //返回走棋失败 } //2.分解走法，取得起点位置和目的位置 from = generateMoveFrom(move); to = generateMoveTo(move); //3.走一步棋 delPiece(from); addPiece(to); //4.检查吃子 eatCount = 0; //一步有可能同时吃掉两子 myPiece = currentPlayer * 4 + 3; //由当前走棋方计算当前走棋方棋子 oppPiece = (1 - currentPlayer) * 4 + 3; //由当前走棋方计算对方棋子 //检查吃子，从上往下、从下往上、从左往右、从右往左，沿四个方向检查吃子情况 for(i = 0; i 4; i++){ step = movesTable[i]; //取得步长 //检查是否为第一种吃子情况“○○●_” 所走棋子为序列中的第一个白子 focus = to + step; //把焦点移到棋子前方第一个位置 if(inBoard[focus] && board[focus] == myPiece){ focus += step; //把焦点移到棋子前方第二个位置 if(inBoard[focus] && board[focus] == oppPiece){ focus += step; //把焦点移到棋子前方第三个位置 if(inBoard[focus] && board[focus] == NOPIECE){ focus -= step; //把焦点移到吃子位置 delPiece(focus); //吃子 eatTable[eatCount] = focus; //记录吃子的位置 eatCount++; //计数 } } } //检查是否为第二种吃子情况“○○●_” 所走棋子为序列中的第二个白子 focus = to - step; //把焦点移到棋子后方位置 if(inBoard[focus] && board[focus] == myPiece){ focus = to + step; //把焦点移到棋子前方第一个位置 if(inBoard[focus] && board[focus] == oppPiece){ focus += step; //把焦点移到棋子前方第二个位置 if(inBoard[focus] && board[focus] == NOPIECE){ focus -= step; //把焦点移到吃子位置 delPiece(focus); //吃子 eatTable[eatCount] = focus; //记录吃子的位置 eatCount++; //计数 } } } //检查是否为第三种吃子情况“●○○_” 所走棋子为序列中的第二个白子 focus = to - step; //把焦点移到棋子后方位置 if(inBoard[focus] && board[focus] == oppPiece){ focus = to + step; //把焦点移到棋子前方第一个位置 if(inBoard[focus] && board[focus] == myPiece){ focus += step; //把焦点移到棋子前方第二个位置 if(inBoard[focus] && board[focus] == NOPIECE){ focus = to - step; //把焦点移到吃子位置 delPiece(focus); //吃子 eatTable[eatCount] = focus; //记录吃子的位置 eatCount++; //计数 } } } //检查是否为第四种吃子情况“_○○●” 所走棋子为序列中的第二个白子 focus = to - step; //把焦点移到棋子后方位置 if(inBoard[focus] && board[focus] == NOPIECE){ focus = to + step; //把焦点移到棋子前方第一个位置 if(inBoard[focus] && board[focus] == myPiece){ focus += step; //把焦点移到棋子前方第二个位置 if(inBoard[focus] && board[focus] == oppPiece){ focus = focus; //焦点已经在吃子位置 delPiece(focus); //吃子 eatTable[eatCount] = focus; //记录吃子的位置 eatCount++; //计数 } } } } //5.交换走棋方 changePlayer(); return 1 + eatCount; //返回吃子的个数加1，我们调用此函数时，只需要用返回值减1就得到吃子个数}/************************************************************** = 第三节 局面评估 =** 3.1 判断胜负** 有了能生成局面上所有能走的棋的函数，程序就能知道哪些棋可以走，哪些棋不能走。 * 现在为了完善规则，我们还差一个判断胜负的函数了。已知一个局面，是否已经分出* 胜负呢？看下面函数。* * (1)需要写一个判断胜负的函数。*///判断是否分出胜负的函数 int isCurrentPlayerDie(){ //如果生成零个走法，则已被困死，将返回1 if(generateAllMoves(theMoves)){ return 0; } return 1;}/** 3.2 局面评估** 局面评估就是量化一个局面的对双方的优劣势，比如一个局面对白方有* 利，那么到底有利多少呢？我们需要给这个局面打一个分。* * 一个局面的优劣，与很多因素有关：双方的棋子，棋子的数目，棋子的* 位置，棋子的灵活型，棋子之前的牵制等。* * 为了简单，本程序只对局面进行最简单的评估，我们设一颗棋子的价值* 为3，那么白方棋子的总价值就是3*白方棋子的剩余数。同样黑方的总* 价值就是3*黑方棋子的剩余数。* * 我们可以用 白方棋子的总价值 减去 黑方棋子的总价值 表示一个局面* 的价值(评分)，那么对白方来说分数越高越好，对黑方来说，分数越低* 越好。对白方来说最好的分数是36，对黑方来说最好的分数是-36，分* 数越大，对白方越有利，分数越小对黑方越有利，所以，白方走棋的原* 则是使局面的分数变大，而黑方走棋的原则是使局面的分数变小。* * (1)我们需要一个评估函数来计算一个局面的评分，如下：*///局面评估函数 int evaluatePosition(){ int i, whiteValue, blackValue, value; //初始化双方的总价值 whiteValue = blackValue = 0; //遍历棋盘，找到棋子 for(i = 0; i 64; i++){ if(board[i] == STONE){ whiteValue += 3; } if(board[i] == LEAF){ blackValue += 3; } } //计算局面价值 value = whiteValue - blackValue; return value;}/************************************************************** = 第四节 局面搜索 =* * 4.1 搜索函数 -- 极小值极大值算法* * 极小值极大值算法会动态的产生一颗博弈树，这颗树的每一个节点就是一个局面，* 它返回最有利于当前走棋方的走法和搜索到的最佳局面的评分。极小值极大值算* 法是很多其他博弈搜索算法的基础。* * 极小值极大值算法的设计思想是轮到双方走棋时，都去寻找最有利与自己的走法* 并假设对方也会走出一步好棋。* * 总之，极小值极大值算法的作用就是从庞大的博弈树中尽可能的找到最有利于当* 前走棋方的走法。* * 在局面搜索的过程中搜索函数会尝试在棋盘上走棋，以取得未来几步的局面。* 为了不破坏当前局面，我们还需要一个撤销走一步棋的函数，用来还原局面。* * (1)我们需要一个变量来保存搜索函数找到的最佳走法 (2)需要一个全局变量来跟踪搜索的当前深度。* (3)需要写一个撤销走法的函数 * (4)一个极小值极大值搜索函数 */#define SEARCH_DEPTH 7 //设置搜索深度#define INFINITY_VALUE 100 //设置局面价值无穷大为100，因为局面价值最大为36， //100不可能达到，所以就相当于无穷大。 //最佳走法int bestMove; //搜索深度int theDepth; //撤销一步棋的函数 void undoOneMove(int move, int eatCount, int *eatTable){ int i, from, to; from = generateMoveFrom(move); to = generateMoveTo(move); //还原被吃的子 for(i = 0; i eatCount; i++){ addPiece(eatTable[i]); //添加对方棋子(注意，这时走棋方为对方，添加对方棋子) } changePlayer(); //交换走棋方 delPiece(to); //删除棋子 addPiece(from); //添加己方棋子}//极小值极大值搜索函数int MinMaxSearch(int depth){ //depth是搜索博弈树的深度，就相当于能看到将来的多少步棋。 //因为随着深度的增加，博弈树的节点树呈指数级增长，数据相 //当庞大，所以深度不易太深，一般7层以上PC机算起来就很吃力了。 int i, genCount, value, bestValue; int allMoves[MAX_GEN_MOVES]; int eatCount, eatTable[2]; //还原局面时用 //如果搜索到指定深度，则返回局面评估值 if(depth == 0){ return evaluatePosition(); } //初始化最佳值 if(currentPlayer){ bestValue = INFINITY_VALUE; //正无穷 }else{ bestValue = -INFINITY_VALUE; //负无穷 } genCount = generateAllMoves(allMoves); for(i = 0;