上周跟着 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 分。
于是,基本的程序逻辑就是:
遍历棋盘上每个点:
如果不能走:
判断下一个点
加上横向得分
加上纵向得分
如果在对角线上:
加上斜向得分
如果是中间点:
加分
如果总分超过最高分:
记录下当前位置
更新最高分
返回最高分所在位置
为了节省再次遍历的开销,在计算得分的同时,就可以把最高分和位置记录下来。
代码如下:
def moveAI():
print 'AI\'s turn...'
point = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0],
]
max_point = -1
position = (0, 0)
for i in range(3):
for j in range(3):
if board[i][j] != 0:
point[i][j] = -1
continue
# row
point[i][j] += calcPoint(board[i])
# col
line = [board[k][j] for k in range(3)]
point[i][j] += calcPoint(line)
# left-top to right-bottom
if i == j:
line = [board[k][k] for k in range(3)]
point[i][j] += calcPoint(line)
# right-top to left-bottom
if i + j == 2:
line = [board[k][2 - k] for k in range(3)]
point[i][j] += calcPoint(line)
# center
if i == 1:
point[i][j] += 1
if j == 1:
point[i][j] += 1
if point[i][j] > max_point:
max_point = point[i][j]
position = (i, j)
print point
board[position[0]][position[1]] = 2
在判断每条线得分时,我们把一个含有 3 个位置的数组传给 calcPoint,经它计算得到分值。下面再来看这个核心的算分函数:
def calcPoint(line):
point = 0
if line.count(2) == 2:
point += 1000
if line.count(1) == 2:
point += 900
if line.count(2) == 1 and line.count(1) == 0:
point += 100
if line.count(2) == 0 and line.count(1) == 1:
point += 90
if line.count(0) == 3:
point += 10
return point
用到了 list 的 count 方法,判断列表中某个元素出现的次数。就这么多代码,完成了电脑的 AI。
这里顺便说一句,我在最开始写这段代码时,并没有考虑到把几种情况整合到一个函数中处理,而且先写了横向的判断。之后再写纵向时,发现可以复用,于是再重构了代码。在实际写代码的时候,经常也有类似的情况。你不用一开始就想一个完美的解决方案,可以先用想到的方法把功能实现,再逐步优化。
把代码添加到已有的游戏代码中,再跟电脑大战三百回合试试看。
由于井字棋棋盘太小,先走的一方具有巨大的优势。理论上来说,只要先手方不犯错,后手方是不可能赢的。现在的电脑作为后手方,已经可以保证不输。而当它先手时,你得保证不犯错才能打成平手。
(完整代码和程序运行效果已上传论坛。)
最后,一个小问题:
如何改动最小的代码,让这个程序变成随机先后手,而不是现在固定玩家先走。
一个大问题:
你能不能用 Pygame 把它改写成一个鼠标操作的游戏,甚至可以保存对战结果和对局过程。
联系客服