用 Python 跟自己下棋（续）

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

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

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

• 尽可能让自己走成 3 个

• 在自己走成 3 个之前，不要让对方走成 3 个

• 最好能在 2 条路线上同时走到 2 个，且第 3 个位置可走

• 选择还有可能走出 3 个的路线上

• 尽量选择路线的交叉点

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

---

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

1. 每个位置默认 0 分

2. 对横、竖、斜三条线分别进行判断，分值累加

3. 如果线上有 2 个己方棋子，+1000

4. 如果线上有 2 个对方棋子，+900

5. 如果线上有 1 个己方棋子，0 个对方棋子，+100

6. 如果线上有 1 个对方棋子，0 个己方棋子，+90

7. 如果线上没有任何棋子，+10

8. 如果此位置是线上的中间位置，+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 把它改写成一个鼠标操作的游戏，甚至可以保存对战结果和对局过程。

---