设为首页收藏本站
开启辅助访问 切换到宽版

 找回密码
 立即注册

QQ登录

只需一步，快速开始

热门： 51单片机 | 24小时必答区 | 单片机教程 | 单片机DIY制作 | STM32 | Cortex M3 | 模数电子 | 电子DIY制作 | 音响/功放 | 拆机乐园 | Arduino | 嵌入式OS | 程序设计

搜索
»论坛 › 电子技术分类讨论区 › 程序设计/上位机 › 博弈树加上α-β剪枝算法做出来的五子棋AI往前推6步无压 ...
返回列表 发新帖
查看: 44237|回复: 8
打印 上一主题 下一主题
收起左侧

博弈树加上α-β剪枝算法做出来的五子棋AI往前推6步无压力

[复制链接]
跳转到指定楼层
楼主
ID:72008 发表于 2015-1-11 19:56 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

AI棋力已经非常叼了我反正是一次都赢不了它，所有棋类AI基本都是一个原理只需要根据游戏规则来改写自己的局面评分函数就欧了
以下代码是在博弈树加上α-β剪枝算法做出来的五子棋AI往前推6步无压力在DEV环境下编译的
  1. #include <cstdlib>
  2. #include <iostream.h>
  3. #include<stdlib.h>
  4. #include<string.h>
  5. #include<time.h>
  6. #define GRID_NUM    15 //每一行(列)的棋盘交点数
  7. #define GRID_COUNT  225//棋盘上交点总数
  8. #define BLACK        0 //黑棋用0表示
  9. #define WHITE        1 //白棋用1表示
  10. #define NOSTONE     '+'  //没有棋子
  11. //这组宏定义了用以代表几种棋型的数字
  12. #define STWO        1  //眠二
  13. #define STHREE        2  //眠三
  14. #define SFOUR        3  //冲四
  15. #define TWO        4  //活二
  16. #define THREE        5  //活三
  17. #define FOUR        6  //活四
  18. #define FIVE        7  //五连
  19. #define NOTYPE        11 //未定义
  20. #define ANALSISED   255//已分析过的
  21. #define TOBEANALSIS 0  //已分析过的
  22. //这个宏用以检查某一坐标是否是棋盘上的有效落子点
  23. #define IsValidPos(x,y) ((x>=0 && x<GRID_NUM) && (y>=0 && y<GRID_NUM)
  24. //定义了枚举型的数据类型，精确，下边界，上边界
  25. enum ENTRY_TYPE{exact,lower_bound,upper_bound};
  26. //哈希表中元素的结构定义
  27. typedef struct HASHITEM
  28. {
  29. __int64 checksum;         //64位校验码
  30. ENTRY_TYPE entry_type;//数据类型
  31. short depth;         //取得此值时的层次
  32. short eval;         //节点的值
  33. }HashItem;

  35. typedef struct Node
  36. {
  37. int x;
  38. int y;
  39. }POINT;

  41. //用以表示棋子位置的结构
  42. typedef struct _stoneposition
  43. {
  44. unsigned char x;
  45. unsigned char y;
  46. }STONEPOS;

  48. typedef struct _movestone
  49. {
  50. unsigned char nRenjuID;
  51. POINT ptMovePoint;
  52. }MOVESTONE;
  53. //这个结构用以表示走法

  55. typedef struct _stonemove
  56. {
  57. STONEPOS StonePos;//棋子位置
  58. int Score;         //走法的分数
  59. }STONEMOVE;
  60. //=================================================================//
  61. int AnalysisLine(unsigned char* position,int GridNum,int StonePos);
  62. int AnalysisRight(unsigned char position[][GRID_NUM],int i,int j);
  63. int AnalysisLeft(unsigned char position[][GRID_NUM],int i,int j);
  64. int AnalysisVertical(unsigned char position[][GRID_NUM],int i,int j);
  65. int AnalysisHorizon(unsigned char position[][GRID_NUM],int i,int j);
  66. int Eveluate(unsigned int position[][GRID_NUM],bool bIsWhiteTurn);
  67. int AddMove(int nToX, int nToY, int nPly);
  68. int CreatePossibleMove(unsigned char position[][GRID_NUM], int nPly, int nSide);
  69. void MergeSort(STONEMOVE* source,int n,bool direction);
  70. void MergePass(STONEMOVE* source,STONEMOVE* target,const int s,const int n,const bool direction);
  71. void Merge_A(STONEMOVE* source,STONEMOVE* target,int l,int m,int r);
  72. void Merge(STONEMOVE* source,STONEMOVE* target,int l,int m,int r);
  73. void EnterHistoryScore(STONEMOVE* move,int depth);
  74. int GetHistoryScore(STONEMOVE* move);
  75. void ResetHistoryTable();
  76. int NegaScout(int depth,int alpha,int beta);
  77. void SearchAGoodMove(unsigned char position[][GRID_NUM],int Type);
  78. int IsGameOver(unsigned char position[][GRID_NUM],int nDepth);
  79. void UnMakeMove(STONEMOVE* move);
  80. unsigned char MakeMove(STONEMOVE* move,int type);
  81. void _CSearchEngine();
  82. void InitializeHashKey();
  83. void EnterHashTable(ENTRY_TYPE entry_type, short eval, short depth, int TableNo);
  84. int LookUpHashTable(int alpha, int beta, int depth, int TableNo);
  85. void Hash_UnMakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM]);
  86. void Hash_MakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM]);
  87. void CalculateInitHashKey(unsigned char CurPosition[][GRID_NUM]);
  88. __int64 rand64();
  89. long rand32();
  90. void CTranspositionTable();
  91. void _CTranspositionTable();
  92. bool OnInitDialog();
  93. //=================================================================//
  94. int m_HistoryTable[GRID_NUM][GRID_NUM];//历史得分表
  95. STONEMOVE m_TargetBuff[225];    //排序用的缓冲队列
  96. unsigned int m_nHashKey32[15][10][9];          //32位随机树组，用以生成32位哈希值
  97. unsigned __int64 m_ulHashKey64[15][10][9];//64位随机树组，用以生成64位哈希值
  98. HashItem *m_pTT[10];          //置换表头指针
  99. unsigned int m_HashKey32;          //32位哈希值
  100. __int64 m_HashKey64;          //64 位哈希值
  101. STONEMOVE m_MoveList[10][225];//用以记录走法的数组
  102. unsigned char m_LineRecord[30];          //存放AnalysisLine分析结果的数组
  103. int TypeRecord[GRID_NUM ][GRID_NUM][4];//存放全部分析结果的数组,有三个维度,用于存放水平、垂直、左斜、右斜 4 个方向上所有棋型分析结果
  104. int TypeCount[2][20];          //存放统记过的分析结果的数组
  105. int m_nMoveCount;//此变量用以记录走法的总数
  106. unsigned char CurPosition[GRID_NUM][GRID_NUM];//搜索时用于当前节点棋盘状态的数组
  107. STONEMOVE m_cmBestMove;        //记录最佳走法的变量       
  108. //CMoveGenerator* m_pMG;        //走法产生器指针       
  109. //CEveluation* m_pEval;        //估值核心指针       
  110. int m_nSearchDepth;        //最大搜索深度
  111. int m_nMaxDepth;        //当前搜索的最大搜索深度
  112. unsigned char m_RenjuBoard[GRID_NUM][GRID_NUM];//棋盘数组，用于显示棋盘
  113. int m_nUserStoneColor;         //用户棋子的颜色
  114. //CSearchEngine* m_pSE;         //搜索引擎指针
  115. int X,Y;                               //AI输出落子位置
  116. int SL;                                  //胜利标记
  117. //位置重要性价值表,此表从中间向外,越往外价值越低
  118. int PosValue[GRID_NUM][GRID_NUM]=
  119. {
  120. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  121. {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
  122. {0,1,2,2,2,2,2,2,2,2,2,2,2,1,0},
  123. {0,1,2,3,3,3,3,3,3,3,3,3,2,1,0},
  124. {0,1,2,3,4,4,4,4,4,4,4,3,2,1,0},
  125. {0,1,2,3,4,5,5,5,5,5,4,3,2,1,0},
  126. {0,1,2,3,4,5,6,6,6,5,4,3,2,1,0},
  127. {0,1,2,3,4,5,6,7,6,5,4,3,2,1,0},
  128. {0,1,2,3,4,5,6,6,6,5,4,3,2,1,0},
  129. {0,1,2,3,4,5,5,5,5,5,4,3,2,1,0},
  130. {0,1,2,3,4,4,4,4,4,4,4,3,2,1,0},
  131. {0,1,2,3,3,3,3,3,3,3,3,3,2,1,0},
  132. {0,1,2,2,2,2,2,2,2,2,2,2,2,1,0},
  133. {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
  134. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
  135. };

  137. //全局变量,用以统计估值函数的执行遍数
  138. int count=0;

  140. int Eveluate(unsigned char position[][GRID_NUM],bool bIsWhiteTurn)
  141. {
  142. int i,j,k;
  143. unsigned char nStoneType;
  144. count++;//计数器累加

  146. //清空棋型分析结果
  147. memset(TypeRecord,TOBEANALSIS,GRID_COUNT*4*4);
  148. memset(TypeCount,0,40*4);

  150. for(i=0;i<GRID_NUM;i++)
  151. for(j=0;j<GRID_NUM;j++)
  152. {
  153. if(position[i][j]!=NOSTONE)
  154. {
  155. //如果水平方向上没有分析过
  156. if(TypeRecord[i][j][0]==TOBEANALSIS)
  157. AnalysisHorizon(position,i,j);

  159. //如果垂直方向上没有分析过
  160. if(TypeRecord[i][j][1]==TOBEANALSIS)
  161. AnalysisVertical(position,i,j);

  163. //如果左斜方向上没有分析过
  164. if(TypeRecord[i][j][2]==TOBEANALSIS)
  165. AnalysisLeft(position,i,j);

  167. //如果右斜方向上没有分析过
  168. if(TypeRecord[i][j][3]==TOBEANALSIS)
  169. AnalysisRight(position,i,j);
  170. }
  171. }

  173. //对分析结果进行统计,得到每种棋型的数量
  174. for(i=0;i<GRID_NUM;i++)
  175. for(j=0;j<GRID_NUM;j++)
  176. for(k =0;k<4;k++)
  177. {
  178. nStoneType=position[i][j];
  179. if(nStoneType!=NOSTONE)
  180. {
  181. switch(TypeRecord[i][j][k])
  182. {
  183. case FIVE://五连
  184. TypeCount[nStoneType][FIVE]++;
  185. break;
  186. case FOUR://活四
  187. TypeCount[nStoneType][FOUR]++;
  188. break;
  189. case SFOUR://冲四
  190. TypeCount[nStoneType][SFOUR]++;
  191. break;
  192. case THREE://活三
  193. TypeCount[nStoneType][THREE]++;
  194. break;
  195. case STHREE://眠三
  196. TypeCount[nStoneType][STHREE]++;
  197. break;
  198. case TWO://活二
  199. TypeCount[nStoneType][TWO]++;
  200. break;
  201. case STWO://眠二
  202. TypeCount[nStoneType][STWO]++;
  203. break;
  204. default:
  205. break;
  206. }  
  207. }
  208. }

  210. //如果已五连,返回极值
  211. if(bIsWhiteTurn)
  212. {
  213. if(TypeCount[BLACK][FIVE])
  214. {
  215.             
  216.          
  217.                  
  218. return -9999;
  219.         }
  220. if(TypeCount[WHITE][FIVE])
  221. {
  222.                
  223.             
  224.                         
  225. return 9999;
  226.         }
  227. }
  228. else
  229. {
  230. if(TypeCount[BLACK][FIVE])
  231. {
  232.               
  233.          
  234.                                 
  235. return 9999;
  236.         }
  237. if(TypeCount[WHITE][FIVE])
  238. {
  239.             
  240.      
  241.                              
  242. return -9999;
  243.         }
  244. }
  245. //两个冲四等于一个活四
  246. if(TypeCount[WHITE][SFOUR]>1)
  247. TypeCount[WHITE][FOUR]++;
  248. if(TypeCount[BLACK][SFOUR]>1)
  249. TypeCount[BLACK][FOUR]++;
  250. int WValue=0,BValue=0;

  252. if(bIsWhiteTurn)//轮到白棋走
  253. {       
  254. if(TypeCount[WHITE][FOUR])       
  255.         {       
  256.             
  257.          
  258. return 9990;//活四,白胜返回极值
  259.          }
  260. if(TypeCount[WHITE][SFOUR])       
  261.         {       
  262.             
  263.          
  264. return 9980;//冲四,白胜返回极值
  265.         }
  266. if(TypeCount[BLACK][FOUR])       
  267. {
  268.            
  269.             
  270. return -9970;//白无冲四活四,而黑有活四,黑胜返回极值
  271.         }
  272. if(TypeCount[BLACK][SFOUR] && TypeCount[BLACK][THREE])
  273. {
  274.             
  275.                      
  276. return -9960;//而黑有冲四和活三,黑胜返回极值
  277.         }
  278. if(TypeCount[WHITE][THREE] && TypeCount[BLACK][SFOUR]== 0)       
  279.         {       
  280.            
  281.             
  282. return 9950;//白有活三而黑没有四,白胜返回极值
  283.         }
  284. if(TypeCount[BLACK][THREE]>1 && TypeCount[WHITE][SFOUR]==0 && TypeCount[WHITE][THREE]==0 && TypeCount[WHITE][STHREE]==0)
  285.         {       
  286.             
  287.             
  288. return -9940;//黑的活三多于一个,而白无四和三,黑胜返回极值
  289.         }
  290. if(TypeCount[WHITE][THREE]>1)
  291. WValue+=2000;//白活三多于一个,白棋价值加2000
  292. else
  293. //否则白棋价值加200
  294. if(TypeCount[WHITE][THREE])
  295. WValue+=200;
  296. if(TypeCount[BLACK][THREE]>1)
  297. BValue+=500;//黑的活三多于一个,黑棋价值加500
  298. else
  299. //否则黑棋价值加100
  300. if(TypeCount[BLACK][THREE])
  301. BValue+=100;
  302. //每个眠三加10
  303. if(TypeCount[WHITE][STHREE])
  304. WValue+=TypeCount[WHITE][STHREE]*10;
  305. //每个眠三加10
  306. if(TypeCount[BLACK][STHREE])
  307. BValue+=TypeCount[BLACK][STHREE]*10;
  308. //每个活二加4
  309. if(TypeCount[WHITE][TWO])
  310. WValue+=TypeCount[WHITE][TWO]*4;
  311. //每个活二加4
  312. if(TypeCount[BLACK][STWO])
  313. BValue+=TypeCount[BLACK][TWO]*4;
  314. //每个眠二加1
  315. if(TypeCount[WHITE][STWO])
  316. WValue+=TypeCount[WHITE][STWO];
  317. //每个眠二加1
  318. if(TypeCount[BLACK][STWO])
  319. BValue+=TypeCount[BLACK][STWO];
  320. }
  321. else//轮到黑棋走
  322. {       
  323. if(TypeCount[BLACK][FOUR])       
  324.         {       
  325.    
  326. return 9990;//活四,黑胜返回极值
  327.           }
  328. if(TypeCount[BLACK][SFOUR])       
  329.         {       
  330.            
  331. return 9980;//冲四,黑胜返回极值
  332.         }
  333. if(TypeCount[WHITE][FOUR])
  334. return -9970;//活四,白胜返回极值
  335.       
  336. if(TypeCount[WHITE][SFOUR] && TypeCount[WHITE][THREE])       
  337. return -9960;//冲四并活三,白胜返回极值

  339. if(TypeCount[BLACK][THREE] && TypeCount[WHITE][SFOUR]==0)
  340. return 9950;//黑活三,白无四。黑胜返回极值

  342. if(TypeCount[WHITE][THREE]>1 && TypeCount[BLACK][SFOUR]==0 && TypeCount[BLACK][THREE]==0 && TypeCount[BLACK][STHREE]==0)
  343. return -9940;//白的活三多于一个,而黑无四和三,白胜返回极值

  345. //黑的活三多于一个,黑棋价值加2000
  346. if(TypeCount[BLACK][THREE]>1)
  347. BValue+=2000;
  348. else
  349. //否则黑棋价值加200
  350. if(TypeCount[BLACK][THREE])
  351. BValue+=200;

  353. //白的活三多于一个,白棋价值加 500
  354. if(TypeCount[WHITE][THREE]>1)
  355. WValue+=500;
  356. else
  357. //否则白棋价值加100
  358. if(TypeCount[WHITE][THREE])
  359. WValue+=100;

  361. //每个眠三加10
  362. if(TypeCount[WHITE][STHREE])
  363. WValue+=TypeCount[WHITE][STHREE]*10;
  364. //每个眠三加10
  365. if(TypeCount[BLACK][STHREE])
  366. BValue+=TypeCount[BLACK][STHREE]*10;

  368. //每个活二加4
  369. if(TypeCount[WHITE][TWO])
  370. WValue+=TypeCount[WHITE][TWO]*4;
  371. //每个活二加4
  372. if(TypeCount[BLACK][STWO])
  373. BValue+=TypeCount[BLACK][TWO]*4;

  375. //每个眠二加1
  376. if(TypeCount[WHITE][STWO])
  377. WValue+=TypeCount[WHITE][STWO];
  378. //每个眠二加1
  379. if(TypeCount[BLACK][STWO])
  380. BValue+=TypeCount[BLACK][STWO];
  381. }

  383. //加上所有棋子的位置价值
  384. for(i=0;i<GRID_NUM;i++)
  385. for(j=0;j<GRID_NUM;j++)
  386. {
  387. nStoneType=position[i][j];
  388. if(nStoneType!=NOSTONE)
  389. if(nStoneType==BLACK)
  390. BValue+=PosValue[i][j];
  391. else
  392. WValue+=PosValue[i][j];
  393. }

  395. //返回估值
  396. if(!bIsWhiteTurn)
  397. return BValue-WValue;
  398. else
  399. return WValue-BValue;
  400. }

  402. //分析棋盘上某点在水平方向上的棋型
  403. int AnalysisHorizon(unsigned char position[][GRID_NUM],int i,int j)
  404. {
  405. //调用直线分析函数分析
  406. AnalysisLine(position[i],15,j);
  407. //拾取分析结果
  408. for(int s=0;s<15;s++)
  409. if(m_LineRecord[s]!=TOBEANALSIS)
  410. TypeRecord[i][s][0]= m_LineRecord[s];

  412. return TypeRecord[i][j][0];
  413. }

  415. //分析棋盘上某点在垂直方向上的棋型
  416. int AnalysisVertical(unsigned char position[][GRID_NUM],int i,int j)
  417. {
  418. unsigned char tempArray[GRID_NUM];
  419. //将垂直方向上的棋子转入一维数组
  420. for(int k=0;k<GRID_NUM;k++)
  421. tempArray[k]=position[k][j];
  422. //调用直线分析函数分析
  423. AnalysisLine(tempArray,GRID_NUM,i);
  424. //拾取分析结果
  425. for(int s=0;s<GRID_NUM;s++)
  426. if(m_LineRecord[s]!=TOBEANALSIS)
  427. TypeRecord[s][j][1]=m_LineRecord[s];

  429. return TypeRecord[i][j][1];
  430. }

  432. //分析棋盘上某点在左斜方向上的棋型
  433. int AnalysisLeft(unsigned char position[][GRID_NUM],int i,int j)
  434. {
  435. unsigned char tempArray[GRID_NUM];
  436. int x,y;
  437. int k;
  438. if(i<j)
  439. {
  440. y=0;
  441. x=j-i;
  442. }
  443. else
  444. {
  445. x=0;
  446. y=i-j;
  447. }
  448. //将斜方向上的棋子转入一维数组
  449. for(k=0;k<GRID_NUM;k++)
  450. {
  451. if(x+k>14 || y+k>14)
  452. break;
  453. tempArray[k]=position[y+k][x+k];
  454. }
  455. //调用直线分析函数分析
  456. AnalysisLine(tempArray,k,j-x);
  457. //拾取分析结果
  458. for(int s=0;s<k;s++)
  459. if(m_LineRecord[s]!=TOBEANALSIS)
  460. TypeRecord[y+s][x+s][2]=m_LineRecord[s];

  462. return TypeRecord[i][j][2];
  463. }

  465. //分析棋盘上某点在右斜方向上的棋型
  466. int AnalysisRight(unsigned char position[][GRID_NUM],int i,int j)
  467. {
  468. unsigned char tempArray[GRID_NUM];
  469. int x,y,realnum;
  470. int k;
  471. if(14-i<j)
  472. {
  473. y=14;
  474. x=j-14+i;
  475. realnum=14-i;
  476. }
  477. else
  478. {
  479. x=0;
  480. y=i+j;
  481. realnum=j;
  482. }
  483. //将斜方向上的棋子转入一维数组
  484. for(k=0;k<GRID_NUM;k++)
  485. {
  486. if(x+k>14 || y-k<0)
  487. break;
  488. tempArray[k]=position[y-k][x+k];
  489. }
  490. //调用直线分析函数分析
  491. AnalysisLine(tempArray,k,j-x);
  492. //拾取分析结果
  493. for(int s=0;s<k;s++)
  494. if(m_LineRecord[s]!=TOBEANALSIS)
  495. TypeRecord[y-s][x+s][3]=m_LineRecord[s];

  497. return TypeRecord[i][j][3];
  498. }

  500. int AnalysisLine(unsigned char* position,int GridNum,int StonePos)
  501. {
  502. unsigned char StoneType;
  503. unsigned char AnalyLine[30];
  504. int nAnalyPos;
  505. int LeftEdge,RightEdge;
  506. int LeftRange,RightRange;

  508. if(GridNum<5)
  509. {
  510. //数组长度小于5没有意义
  511. memset(m_LineRecord,ANALSISED,GridNum);
  512. return 0;
  513. }
  514. nAnalyPos=StonePos;
  515. memset(m_LineRecord,TOBEANALSIS,30);
  516. memset(AnalyLine,0x0F,30);
  517. //将传入数组装入AnalyLine;
  518. memcpy(&AnalyLine,position,GridNum);
  519. GridNum--;
  520. StoneType=AnalyLine[nAnalyPos];
  521. LeftEdge=nAnalyPos;
  522. RightEdge=nAnalyPos;
  523. //算连续棋子左边界
  524. while(LeftEdge>0)
  525. {
  526. if(AnalyLine[LeftEdge-1]!=StoneType)
  527. break;
  528. LeftEdge--;
  529. }

  531. //算连续棋子右边界
  532. while(RightEdge<GridNum)
  533. {
  534. if(AnalyLine[RightEdge+1]!=StoneType)
  535. break;
  536. RightEdge++;
  537. }
  538. LeftRange=LeftEdge;
  539. RightRange=RightEdge;
  540. //下面两个循环算出棋子可下的范围
  541. while(LeftRange>0)
  542. {
  543. if(AnalyLine[LeftRange -1]==!StoneType)
  544. break;
  545. LeftRange--;
  546. }
  547. while(RightRange<GridNum)
  548. {
  549. if(AnalyLine[RightRange+1]==!StoneType)
  550. break;
  551. RightRange++;
  552. }
  553. //如果此范围小于4则分析没有意义
  554. if(RightRange-LeftRange<4)
  555. {
  556. for(int k=LeftRange;k<=RightRange;k++)
  557. m_LineRecord[k]=ANALSISED;
  558. return false;
  559. }
  560. //将连续区域设为分析过的,防止重复分析此一区域
  561. for(int k=LeftEdge;k<=RightEdge;k++)
  562. m_LineRecord[k]=ANALSISED;
  563. if(RightEdge-LeftEdge>3)
  564. {
  565. //如待分析棋子棋型为五连
  566. m_LineRecord[nAnalyPos]=FIVE;
  567. return FIVE;
  568. }

  570. if(RightEdge-LeftEdge== 3)
  571. {
  572. //如待分析棋子棋型为四连
  573. bool Leftfour=false;
  574. if(LeftEdge>0)
  575. if(AnalyLine[LeftEdge-1]==NOSTONE)
  576. Leftfour=true;//左边有气

  578. if(RightEdge<GridNum)
  579. //右边未到边界
  580. if(AnalyLine[RightEdge+1]==NOSTONE)
  581. //右边有气
  582. if(Leftfour==true)//如左边有气
  583. m_LineRecord[nAnalyPos]=FOUR;//活四
  584. else
  585. m_LineRecord[nAnalyPos]=SFOUR;//冲四
  586. else
  587. if(Leftfour==true)//如左边有气
  588. m_LineRecord[nAnalyPos]=SFOUR;//冲四
  589. else
  590. if(Leftfour==true)//如左边有气
  591. m_LineRecord[nAnalyPos]=SFOUR;//冲四

  593. return m_LineRecord[nAnalyPos];
  594. }

  596. if(RightEdge-LeftEdge==2)
  597. {
  598. //如待分析棋子棋型为三连
  599. bool LeftThree=false;

  601. if(LeftEdge>1)
  602. if(AnalyLine[LeftEdge-1]==NOSTONE)
  603. //左边有气
  604. if(LeftEdge>1 && AnalyLine[LeftEdge-2]==AnalyLine[LeftEdge])
  605. {
  606. //左边隔一空白有己方棋子
  607. m_LineRecord[LeftEdge]=SFOUR;//冲四
  608. m_LineRecord[LeftEdge-2]=ANALSISED;
  609. }
  610. else
  611. LeftThree=true;

  613. if(RightEdge<GridNum)
  614. if(AnalyLine[RightEdge+1]==NOSTONE)
  615. //右边有气
  616. if(RightEdge<GridNum-1 && AnalyLine[RightEdge+2]==AnalyLine[RightEdge])
  617. {
  618. //右边隔1个己方棋子
  619. m_LineRecord[RightEdge]=SFOUR;//冲四
  620. m_LineRecord[RightEdge+2]=ANALSISED;
  621. }
  622. else
  623. if(LeftThree==true)//如左边有气
  624. m_LineRecord[RightEdge]=THREE;//活三
  625. else
  626. m_LineRecord[RightEdge]=STHREE; //冲三
  627. else
  628. {
  629. if(m_LineRecord[LeftEdge]==SFOUR)//如左冲四
  630. return m_LineRecord[LeftEdge];//返回

  632. if(LeftThree==true)//如左边有气
  633. m_LineRecord[nAnalyPos]=STHREE;//眠三
  634. }
  635. else
  636. {
  637. if(m_LineRecord[LeftEdge]==SFOUR)//如左冲四
  638. return m_LineRecord[LeftEdge];//返回
  639. if(LeftThree==true)//如左边有气
  640. m_LineRecord[nAnalyPos]=STHREE;//眠三
  641. }

  643. return m_LineRecord[nAnalyPos];
  644. }

  646. if(RightEdge-LeftEdge==1)
  647. {
  648. //如待分析棋子棋型为二连
  649. bool Lefttwo=false;
  650. bool Leftthree=false;

  652. if(LeftEdge>2)
  653. if(AnalyLine[LeftEdge-1]==NOSTONE)
  654. //左边有气
  655. if(LeftEdge-1>1 && AnalyLine[LeftEdge-2]==AnalyLine[LeftEdge])
  656. if(AnalyLine[LeftEdge-3]==AnalyLine[LeftEdge])
  657. {
  658. //左边隔2个己方棋子
  659. m_LineRecord[LeftEdge-3]=ANALSISED;
  660. m_LineRecord[LeftEdge-2]=ANALSISED;
  661. m_LineRecord[LeftEdge]=SFOUR;//冲四
  662. }
  663. else
  664. if(AnalyLine[LeftEdge-3]==NOSTONE)
  665. {
  666. //左边隔1个己方棋子
  667. m_LineRecord[LeftEdge-2]=ANALSISED;
  668. m_LineRecord[LeftEdge]=STHREE;//眠三
  669. }
  670. else
  671. Lefttwo=true;

  673. if(RightEdge<GridNum-2)
  674. if(AnalyLine[RightEdge+1]==NOSTONE)
  675. //右边有气
  676. if(RightEdge+1<GridNum-1 && AnalyLine[RightEdge+2]==AnalyLine[RightEdge])
  677. if(AnalyLine[RightEdge+3]==AnalyLine[RightEdge])
  678. {
  679. //右边隔两个己方棋子
  680. m_LineRecord[RightEdge+3]=ANALSISED;
  681. m_LineRecord[RightEdge+2]=ANALSISED;
  682. m_LineRecord[RightEdge]=SFOUR;//冲四
  683. }
  684. else
  685. if(AnalyLine[RightEdge+3]==NOSTONE)
  686. {
  687. //右边隔 1 个己方棋子
  688. m_LineRecord[RightEdge+2]=ANALSISED;
  689. m_LineRecord[RightEdge]=STHREE;//眠三
  690. }
  691. else
  692. {
  693. if(m_LineRecord[LeftEdge]==SFOUR)//左边冲四
  694. return m_LineRecord[LeftEdge];//返回

  696. if(m_LineRecord[LeftEdge]==STHREE)//左边眠三       
  697. return m_LineRecord[LeftEdge];

  699. if(Lefttwo==true)
  700. m_LineRecord[nAnalyPos]=TWO;//返回活二
  701. else
  702. m_LineRecord[nAnalyPos]=STWO;//眠二
  703. }
  704. else
  705. {
  706. if(m_LineRecord[LeftEdge]==SFOUR)//冲四返回
  707. return m_LineRecord[LeftEdge];

  709. if(Lefttwo==true)//眠二
  710. m_LineRecord[nAnalyPos]=STWO;
  711. }

  713. return m_LineRecord[nAnalyPos];
  714. }

  716. return 0;
  717. }

  719. //将历史记录表中所有项目全置为初值
  720. void ResetHistoryTable()
  721. {
  722.     memset(m_HistoryTable,10,GRID_COUNT*sizeof(int));
  723. }

  725. //从历史得分表中取给定走法的历史得分
  726. int GetHistoryScore(STONEMOVE* move)
  727. {
  728. return m_HistoryTable[move->StonePos.x][move->StonePos.y];
  729. }

  731. //将一最佳走法汇入历史记录
  732. void EnterHistoryScore(STONEMOVE* move,int depth)
  733. {
  734. m_HistoryTable[move->StonePos.x][move->StonePos.y]+=2<<depth;
  735. }

  737. //对走法队列从小到大排序
  738. //STONEMOVE* source原始队列
  739. //STONEMOVE* target目标队列
  740. //合并source[l…m]和 source[m +1…r]至target[l…r]
  741. void Merge(STONEMOVE* source,STONEMOVE* target,int l,int m,int r)
  742. {
  743. //从小到大排序
  744. int i=l;
  745. int j=m+1;
  746. int k=l;
  747. while(i<=m && j<=r)
  748. if(source[i].Score<=source[j].Score)
  749. target[k++]=source[i++];
  750. else
  751. target[k++]=source[j++];
  752. if(i>m)
  753. for(int q=j;q<=r;q++)
  754. target[k++]=source[q];
  755. else
  756. for(int q=i;q<=m;q++)
  757. target[k++]=source[q];
  758. }

  760. void Merge_A(STONEMOVE* source,STONEMOVE* target,int l,int m,int r)
  761. {
  762. //从大到小排序
  763. int i=l;
  764. int j=m+1;
  765. int k=l;
  766. while(i<=m &&j<=r)
  767. if(source[i].Score>=source[j].Score)
  768. target[k++]=source[i++];
  769. else
  770. target[k++]=source[j++];
  771. if(i>m)
  772. for(int q=j;q<=r;q++)
  773. target[k++]=source[q];
  774. else
  775. for(int q=i;q<=m;q++)
  776. target[k++]=source[q];
  777. }

  779. //合并大小为 S 的相邻子数组
  780. //direction 是标志,指明是从大到小还是从小到大排序
  781. void MergePass(STONEMOVE* source,STONEMOVE* target,const int s,const int n,const bool direction)
  782. {
  783. int i=0;
  784. while(i<=n-2*s)
  785. {
  786. //合并大小为 s的相邻二段子数组
  787. if(direction)
  788. Merge(source,target,i,i+s-1,i+2*s-1);
  789. else
  790. Merge_A(source,target,i,i+s-1,i+2*s-1);
  791. i=i+2*s;
  792. }
  793. if(i+s<n)//剩余的元素个数小于2s
  794. {
  795. if(direction)
  796. Merge(source,target,i,i+s-1,n-1);
  797. else
  798. Merge_A(source,target,i,i+s-1,n-1);
  799. }
  800. else
  801. for(int j=i;j<=n-1;j++)
  802. target[j]=source[j];
  803. }

  805. void MergeSort(STONEMOVE* source,int n,bool direction)
  806. {
  807. int s=1;
  808. while(s<n)
  809. {
  810. MergePass(source,m_TargetBuff,s,n,direction);
  811. s+=s;
  812. MergePass(m_TargetBuff,source,s,n,direction);
  813. s+=s;
  814. }
  815. }

  817. int CreatePossibleMove(unsigned char position[][GRID_NUM], int nPly, int nSide)
  818. {
  819. int i,j;
  820. m_nMoveCount=0;
  821. for(i=0;i<GRID_NUM;i++)
  822. for(j=0;j<GRID_NUM;j++)
  823. {
  824. if(position[i][j]==(unsigned char)NOSTONE)
  825. AddMove(j,i,nPly);
  826. }

  828. //使用历史启发类中的静态归并排序函数对走法队列进行排序
  829. //这是为了提高剪枝效率
  830. //        CHistoryHeuristic history;
  831. MergeSort(m_MoveList[nPly],m_nMoveCount,0);

  833. return m_nMoveCount;//返回合法走法个数
  834. }

  836. //在m_MoveList中插入一个走法
  837. //nToX是目标位置横坐标
  838. //nToY是目标位置纵坐标
  839. //nPly是此走法所在的层次
  840. int AddMove(int nToX, int nToY, int nPly)
  841. {
  842. m_MoveList[nPly][m_nMoveCount].StonePos.x=nToX;
  843. m_MoveList[nPly][m_nMoveCount].StonePos.y=nToY;

  845. m_nMoveCount++;
  846. m_MoveList[nPly][m_nMoveCount].Score=PosValue[nToY][nToX];//使用位置价值表评估当前走法的价值
  847. return m_nMoveCount;
  848. }

  850. void CNegaScout_TT_HH()
  851. {
  852. ResetHistoryTable();
  853. //        m_pThinkProgress=NULL;
  854. }

  856. void SearchAGoodMove(unsigned char position[][GRID_NUM],int Type)
  857. {
  858. int Score;

  860. memcpy(CurPosition,position,GRID_COUNT);
  861. m_nMaxDepth=m_nSearchDepth;
  862. CalculateInitHashKey(CurPosition);
  863. ResetHistoryTable();
  864. Score=NegaScout(m_nMaxDepth,-20000,20000);
  865. X=m_cmBestMove.StonePos.y;
  866. Y=m_cmBestMove.StonePos.x;
  867. MakeMove(&m_cmBestMove,Type);
  868. memcpy(position,CurPosition,GRID_COUNT);
  869. }

  871. int IsGameOver(unsigned char position[][GRID_NUM],int nDepth)
  872. {
  873. int score,i;//计算要下的棋子颜色
  874. i=(m_nMaxDepth-nDepth)%2;
  875. score=Eveluate(position,i);//调用估值函数
  876. if(abs(score)>8000)//如果估值函数返回极值，给定局面游戏结束
  877. return score;//返回极值
  878. return 0;//返回未结束
  879. }

  881. int NegaScout(int depth,int alpha,int beta)
  882. {
  883. int Count,i;
  884. unsigned char type;
  885. int a,b,t;
  886. int side;
  887. int score;
  888. /*        if(depth>0)
  889. {
  890. i= IsGameOver(CurPosition,depth);
  891. if(i!=0)
  892. return i;  //已分胜负，返回极值
  893. }
  894. */
  895. side=(m_nMaxDepth-depth)%2;//计算当前节点的类型,极大0/极小1
  896. score=LookUpHashTable(alpha,beta,depth,side);
  897. if(score!=66666)
  898. return score;
  899. if(depth<=0)//叶子节点取估值
  900. {
  901. score=Eveluate(CurPosition,side);
  902. EnterHashTable(exact,score,depth,side);//将估值存入置换表

  904. return score;
  905. }
  906. Count=CreatePossibleMove(CurPosition,depth,side);
  907. for(i=0;i<Count;i++)
  908. m_MoveList[depth][i].Score=GetHistoryScore(&m_MoveList[depth][i]);

  910. MergeSort(m_MoveList[depth],Count,0);
  911. int bestmove=-1;
  912.     a=alpha;
  913.     b=beta;

  915.     int eval_is_exact=0;

  917.     for(i=0;i<Count;i++)
  918. {
  919. type=MakeMove(&m_MoveList[depth][i],side);
  920. Hash_MakeMove(&m_MoveList[depth][i],CurPosition);
  921. t=-NegaScout(depth-1,-b,-a);//递归搜索子节点，对第 1 个节点是全窗口，其后是空窗探测
  922. if(t>a && t<beta && i>0)
  923. {
  924. //对于第一个后的节点,如果上面的搜索failhigh
  925. a=-NegaScout(depth-1,-beta,-t);//re-search
  926. eval_is_exact=1;//设数据类型为精确值
  927. if(depth==m_nMaxDepth)
  928. m_cmBestMove=m_MoveList[depth][i];
  929. bestmove=i;
  930. }
  931. Hash_UnMakeMove(&m_MoveList[depth][i],CurPosition);
  932. UnMakeMove(&m_MoveList[depth][i]);
  933. if(a<t)
  934. {
  935. eval_is_exact=1;
  936. a=t;
  937. if(depth==m_nMaxDepth)
  938. m_cmBestMove=m_MoveList[depth][i];
  939. }
  940. if(a>= beta)
  941. {
  942. EnterHashTable(lower_bound,a,depth,side);
  943. EnterHistoryScore(&m_MoveList[depth][i],depth);
  944. return a;
  945. }
  946. b=a+1;                      /* set new null window */
  947. }
  948. if(bestmove!=-1)
  949. EnterHistoryScore(&m_MoveList[depth][bestmove], depth);
  950. if(eval_is_exact)
  951. EnterHashTable(exact,a,depth,side);
  952. else
  953. EnterHashTable(upper_bound,a,depth,side);

  955. return a;
  956. }

  958. unsigned char MakeMove(STONEMOVE* move,int type)
  959. {
  960. CurPosition[move->StonePos.y][move->StonePos.x]=type;
  961. return 0;
  962. }

  964. void UnMakeMove(STONEMOVE* move)
  965. {
  966. CurPosition[move->StonePos.y][move->StonePos.x]=NOSTONE;
  967. }

  969. __int64 rand64(void)
  970. {
  971.     return rand()^((__int64)rand()<<15)^((__int64)rand()<<30)^
  972. ((__int64)rand()<<45)^((__int64)rand()<<60);
  973. }

  975. //生成32位随机数
  976. long rand32(void)
  977. {
  978.     return rand()^((long)rand()<<15)^((long)rand()<<30);
  979. }

  981. void CTranspositionTable()
  982. {
  983. InitializeHashKey();//建立哈希表，创建随机数组
  984. }

  986. void _CTranspositionTable()
  987. {
  988. //释放哈希表所用空间
  989. delete m_pTT[0];
  990. delete m_pTT[1];
  991. }

  993. void CalculateInitHashKey(unsigned char CurPosition[][GRID_NUM])
  994. {
  995. int j,k,nStoneType;

  997. m_HashKey32=0;
  998. m_HashKey32=0;
  999. //将所有棋子对应的哈希数加总
  1000. for(j=0;j<GRID_NUM;j++)
  1001. for(k=0;k<GRID_NUM;k++)
  1002. {
  1003. nStoneType=CurPosition[j][k];
  1004. if(nStoneType!=0xFF)
  1005. {
  1006. m_HashKey32=m_HashKey32^m_nHashKey32[nStoneType][j][k];
  1007. m_HashKey64=m_HashKey64^m_ulHashKey64[nStoneType][j][k];
  1008. }
  1009. }
  1010. }

  1012. void Hash_MakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM])
  1013. {
  1014. int type;

  1016. type=CurPosition[move->StonePos.y][move->StonePos.x];//将棋子在目标位置的随机数添入
  1017. m_HashKey32=m_HashKey32^m_nHashKey32[type][move->StonePos.y][move->StonePos.x];
  1018. m_HashKey64=m_HashKey64^m_ulHashKey64[type][move->StonePos.y][move->StonePos.x];
  1019. }

  1021. void Hash_UnMakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM])
  1022. {
  1023. int type;
  1024. type=CurPosition[move->StonePos.y][move->StonePos.x];//将棋子现在位置上的随机数从哈希值当中去除
  1025. m_HashKey32=m_HashKey32^m_nHashKey32[type][move->StonePos.y][move->StonePos.x];
  1026. m_HashKey64=m_HashKey64^m_ulHashKey64[type][move->StonePos.y][move->StonePos.x];
  1027. }

  1029. int LookUpHashTable(int alpha, int beta, int depth, int TableNo)
  1030. {
  1031. int x;
  1032. HashItem* pht;

  1034. //计算二十位哈希地址，如果读者设定的哈希表大小不是 1M*2 的,
  1035. //而是 TableSize*2，TableSize为读者设定的大小
  1036. //则需要修改这一句为m_HashKey32% TableSize
  1037. //下一个函数中这一句也一样
  1038. x=m_HashKey32 & 0xFFFFF;
  1039. pht=&m_pTT[TableNo][x];//取到具体的表项指针

  1041.     if(pht->depth>=depth && pht->checksum==m_HashKey64)
  1042. {
  1043. switch(pht->entry_type)//判断数据类型
  1044. {
  1045. case exact://确切值
  1046. return pht->eval;

  1048. case lower_bound://下边界
  1049. if(pht->eval>=beta)
  1050. return pht->eval;
  1051. else
  1052. break;

  1054. case upper_bound://上边界
  1055. if (pht->eval<=alpha)
  1056. return pht->eval;
  1057. else
  1058. break;
  1059.         }
  1060. }

  1062. return 66666;
  1063. }

  1065. void EnterHashTable(ENTRY_TYPE entry_type, short eval, short depth, int TableNo)
  1066. {
  1067. int x;
  1068. HashItem* pht;

  1070. x=m_HashKey32 & 0xFFFFF;//计算二十位哈希地址
  1071. pht=&m_pTT[TableNo][x]; //取到具体的表项指针

  1073. //将数据写入哈希表
  1074. pht->checksum=m_HashKey64; //64位校验码
  1075. pht->entry_type=entry_type;//表项类型
  1076. pht->eval=eval;          //要保存的值
  1077. pht->depth=depth;          //层次
  1078. }

  1080. void InitializeHashKey()
  1081. {
  1082. int i,j,k;
  1083. srand((unsigned)time(NULL));
  1084. //填充随机数组
  1085. for(i=0;i<15;i++)
  1086. for(j=0;j<10;j++)
  1087. for(k=0;k<9;k++)
  1088. {
  1089. m_nHashKey32[i][j][k]=rand32();
  1090. m_ulHashKey64[i][j][k]=rand64();
  1091. }

  1093. //申请置换表所用空间。1M "2 个条目，读者也可指定其他大小
  1094. m_pTT[0]=new HashItem[1024*1024];//用于存放取极大值的节点数据
  1095. m_pTT[1]=new HashItem[1024*1024];//用于存放取极小值的节点数据
  1096. }


  1099. //using namespace std;

  1101. int main(int argc, char *argv[])
  1102. {
  1103. SL=0;
  1104. int colour;
  1105. char command[10]; //用于保存命令的字符串
  1106. for (int i = 0; i < GRID_NUM; i++)
  1107. for (int j = 0; j < GRID_NUM; j++)
  1108. m_RenjuBoard[i][j] = NOSTONE; //棋盘初始化

  1110.     int XS;
  1111.     printf("请选择先手棋手：1表示AI先手 0表示棋手先手\n");
  1112. cin >> XS; //是否电脑先手
  1113. colour=BLACK;
  1114. m_nUserStoneColor=WHITE;
  1115. while (!SL)
  1116. {
  1117.         printf("\n请输入落子坐标：\n");
  1118. int rival_x, rival_y; //用于保存对手上一步落子点
  1119. cin >> rival_x >> rival_y; //读入对手上一步落子点  
  1120. if(XS == 1 && rival_x == -1 && rival_y == -1) //如果己方执黑且是第一步，则占据棋盘中心位置
  1121. {
  1122. m_RenjuBoard[GRID_NUM / 2][GRID_NUM / 2] = colour; //更新棋盘信息
  1123. //cout << GRID_NUM / 2 << ' ' << GRID_NUM / 2 << endl; //输出
  1124. //cout << flush; //刷新缓冲区  
  1125. }
  1126. else
  1127. {
  1128. m_RenjuBoard[rival_x][rival_y] =m_nUserStoneColor;
  1129. //更新棋盘信息
  1130.            for (int i = 0; i < GRID_NUM; i++)
  1131.       {
  1132. for (int j = 0; j < GRID_NUM; j++)
  1133. {
  1134.             if(m_RenjuBoard[i][j]==WHITE)
  1135. printf("O "); else  if(m_RenjuBoard[i][j]==BLACK)printf("X "); else printf("+ ");
  1136.         }
  1137.           printf("\n");
  1138.         }
  1139. m_nSearchDepth=4;//AI难度等级设置
  1140. //最大搜索深度       
  1141. do
  1142. {
  1143. CNegaScout_TT_HH();         //创建NegaScout_TT_HH搜索引擎
  1144. CTranspositionTable();
  1145. SearchAGoodMove(m_RenjuBoard,colour);
  1146. m_RenjuBoard[X][Y]=colour;
  1147. printf("\nAI落子坐标为：");
  1148. cout << X << ' ' << Y << endl; //输出
  1149. cout << flush; //刷新缓冲区
  1150. _CTranspositionTable();
  1151. break; //结束循环
  1152. }
  1153. while (!SL);
  1154. //循环直至随机得到一个空位置
  1155. for (int i = 0; i < GRID_NUM; i++)
  1156.     {
  1157. for (int j = 0; j < GRID_NUM; j++)
  1158. {
  1159.             if(m_RenjuBoard[i][j]==WHITE)
  1160. printf("O "); else  if(m_RenjuBoard[i][j]==BLACK)printf("X "); else printf("+ ");
  1161.         }
  1162.           printf("\n");
  1163.         }
  1164.         
  1165.         if(SL==1)printf("很遗憾AI胜利了继续努力吧少年！\n");else if(SL==2)printf("少年你太叼了居然打败了AI！\n");
  1166.         
  1167.         
  1168.      }
  1169. }
  1170.    
  1171.     system("PAUSE");
  1172.     return EXIT_SUCCESS;
  1173. }
复制代码



五子棋, 棋类, 游戏
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏 分享淘帖 顶顶 踩踩

相关帖子
回复

使用道具 举报

沙发
ID:106636 发表于 2016-3-6 23:31 | 只看该作者
本帖最后由 1095222570 于 2016-3-7 11:02 编辑

99999999999999999999999999999999
回复

使用道具 举报

板凳
ID:108772 发表于 2016-3-14 00:26 | 只看该作者

RE: 博弈树加上α-β剪枝算法做出来的五子棋AI往前推6步无压力

楼主的代码有个bug，ai不会防守眠4，胜局时也不会自己连5，希望改全，邮箱1490325170@qq.com
回复

使用道具 举报

地板
ID:295341 发表于 2018-3-22 09:17 | 只看该作者
ccl 发表于 2016-3-14 00:26
**** 作者被禁止或删除 内容自动屏蔽 ****

兄弟，楼主有回复你吗，有的话，代码发我一下，
回复

使用道具 举报

5#
ID:295341 发表于 2018-3-26 09:22 | 只看该作者
楼主真大佬，代码能跑起来，有4个错误，改了就好了
回复

使用道具 举报

6#
ID:315397 发表于 2018-4-24 15:25 | 只看该作者
堕落小CY 发表于 2018-3-26 09:22
楼主真大佬，代码能跑起来，有4个错误，改了就好了

请问是哪四个错误啊
回复

使用道具 举报

7#
ID:572771 发表于 2019-7-4 15:09 | 只看该作者
堕落小CY 发表于 2018-3-26 09:22
**** 作者被禁止或删除 内容自动屏蔽 ****

你好，请问是那几个错误呢
回复

使用道具 举报

8#
ID:623380 发表于 2019-10-13 17:05 | 只看该作者
我第一局13步就赢了，而且它判胜负还有问题
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表