查看原文
其他

用 Python 跟自己下棋(续)

2016-03-18 Crossin Crossin的编程教室

上周跟着 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 把它改写成一个鼠标操作的游戏,甚至可以保存对战结果和对局过程。



Crossin的编程教室

微信ID:crossincode

论坛:http://bbs.crossincode.com

QQ群:465369080

点击左下角“阅读原文”,查看更多学习资源

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存