Crossin的编程教室

标题: 用 Python 跟自己下棋（续） [打印本页]

---

作者: crossin先生    时间: 2016-3-18 22:39
标题: 用 Python 跟自己下棋（续）

上周跟着 AlphaGo vs. 李世乭人机大战的风，写了一个命令行下的 TicTacToe 井字棋。不过，电脑是随机选位置，胡乱走子，所以下赢电脑易如反掌，下输给它反倒要点运气。那么本篇的任务就是，给电脑走子加上一点点简单的策略，让它不那么“傻”。

棋类游戏最基本的 AI 方法就是给棋盘上每个位置的优劣程度打分，然后选择的最高分的位置来走。打分算法的好坏，就决定了这个 AI 的“智能”程度。

要给我们的井字棋 AI 制定打分方法，首先就得分析一下井字棋本身的对局策略。好在这个游戏的规则很简单，总结下来基本就是：

• 尽可能让自己走成 3 个
• 在自己走成 3 个之前，不要让对方走成 3 个
• 最好能在 2 条路线上同时走到 2 个，且第 3 个位置可走
• 选择还有可能走出 3 个的路线上
• 尽量选择路线的交叉点
  
  

在继续往下阅读之前，你可以设想一下，自己要如何来完成这段打分的代码，并把它加入现有的代码中。建议亲手试试看。

---

基于上面几点分析，对于棋盘上每一个还未落子的点，我制定了如下的打分方法：

• 每个位置默认 0 分
• 对横、竖、斜三条线分别进行判断，分值累加
• 如果线上有 2 个己方棋子，+1000
• 如果线上有 2 个对方棋子，+900
• 如果线上有 1 个己方棋子，0 个对方棋子，+100
• 如果线上有 1 个对方棋子，0 个己方棋子，+90
• 如果线上没有任何棋子，+10
• 如果此位置是线上的中间位置，+1
  
  

再补充解释一下：

• 这里没有去判断位置是不是交叉点，因为每条线是分开计算的，交叉点本身就会因此多计算多得分，所以不用再额外处理。
• 这个分数是拍脑袋想出来的，不是绝对有意义，但能保证不同条件在数量级上的差别。
• 除了最后一条判断中间位置，其他几个规则都是与当前具体位置无关，只和其所在线上的状况相关。所以可以用同一个方法来处理。
• 只有部分情况需要判断斜线。
• 没有判断既有己方又有敌方的情况，因为这种情况的位置是没有落子的价值的，不用计算它，就是 0 分。
  
  

于是，基本的程序逻辑就是：

1. 
   
2. 遍历棋盘上每个点:
   
3.     如果不能走:
   
4.         判断下一个点
   
5.     加上横向得分
   
6.     加上纵向得分
   
7.     如果在对角线上:
   
8.         加上斜向得分
   
9.     如果是中间点:
   
10.         加分
    
11.     如果总分超过最高分:
    
12.         记录下当前位置
    
13.         更新最高分
    
14. 返回最高分所在位置
    

复制代码

为了节省再次遍历的开销，在计算得分的同时，就可以把最高分和位置记录下来。

代码如下：

1. 
   
2. def moveAI():
   
3.     print 'AI\'s turn...'
   
4.     point = [
   
5.         [0, 0, 0],
   
6.         [0, 0, 0],
   
7.         [0, 0, 0],
   
8.     ]
   
9.     max_point = -1
   
10.     position = (0, 0)
    
11.     for i in range(3):
    
12.         for j in range(3):
    
13.             if board[i][j] != 0:
    
14.                 point[i][j] = -1
    
15.                 continue
    
16.             # row
    
17.             point[i][j] += calcPoint(board[i])
    
18.             # col
    
19.             line = [board[k][j] for k in range(3)]
    
20.             point[i][j] += calcPoint(line)
    
21.             # left-top to right-bottom
    
22.             if i == j:
    
23.                 line = [board[k][k] for k in range(3)]
    
24.                 point[i][j] += calcPoint(line)
    
25.             # right-top to left-bottom
    
26.             if i + j == 2:
    
27.                 line = [board[k][2 - k] for k in range(3)]
    
28.                 point[i][j] += calcPoint(line)
    
29.             # center
    
30.             if i == 1:
    
31.                 point[i][j] += 1
    
32.             if j == 1:
    
33.                 point[i][j] += 1
    
34.             if point[i][j] > max_point:
    
35.                 max_point = point[i][j]
    
36.                 position = (i, j)
    
37.     print point
    
38.     board[position[0]][position[1]] = 2
    

复制代码

在判断每条线得分时，我们把一个含有 3 个位置的数组传给 calcPoint，经它计算得到分值。下面再来看这个核心的算分函数：

1. 
   
2. def calcPoint(line):
   
3.     point = 0
   
4.     if line.count(2) == 2:
   
5.         point += 1000
   
6.     if line.count(1) == 2:
   
7.         point += 900
   
8.     if line.count(2) == 1 and line.count(1) == 0:
   
9.         point += 100
   
10.     if line.count(2) == 0 and line.count(1) == 1:
    
11.         point += 90
    
12.     if line.count(0) == 3:
    
13.         point += 10
    
14.     return point
    

复制代码

用到了 list 的 count 方法，判断列表中某个元素出现的次数。就这么多代码，完成了电脑的 AI。

这里顺便说一句，我在最开始写这段代码时，并没有考虑到把几种情况整合到一个函数中处理，而且先写了横向的判断。之后再写纵向时，发现可以复用，于是再重构了代码。在实际写代码的时候，经常也有类似的情况。你不用一开始就想一个完美的解决方案，可以先用想到的方法把功能实现，再逐步优化。

把代码添加到已有的游戏代码中，再跟电脑大战三百回合试试看。

由于井字棋棋盘太小，先走的一方具有巨大的优势。理论上来说，只要先手方不犯错，后手方是不可能赢的。现在的电脑作为后手方，已经可以保证不输。而当它先手时，你得保证不犯错才能打成平手。

（完整代码和程序运行效果已上传论坛。）

最后，一个小问题：

如何改动最小的代码，让这个程序变成随机先后手，而不是现在固定玩家先走。

一个大问题：

你能不能用 Pygame 把它改写成一个鼠标操作的游戏，甚至可以保存对战结果和对局过程。

tictactoe.py

2016-3-18 22:39 上传

点击文件名下载附件

3.39 KB, 下载次数: 29

---

作者: mike90326    时间: 2016-3-23 12:49
前排先占一个坑，因为刚看完crossing老师pygame的教程，看到这个有点跃跃欲试~~~希望自己能搞定~~！

---

欢迎光临 Crossin的编程教室 (https://bbs.crossincode.com/)

Powered by Discuz! X2.5