井字棋AI

今天翻出很久前写的井字棋程序(也许算得上AI吧)
简单改进了一下与用户交互的方面
然后丢给我弟玩
欣赏着他怎样都下不过计算机时的表情
反正也闲着没事(其实不想做脑力劳动，lazy)，就简单写一篇博客吧

开端

之前不知道是在哪里看到自我博弈这个概念的
然后就突发奇想，想要自己写一个程序\

这个程序只要输入规则\

然后就可以通过自我博弈来成为高手
中间不需要任何人干预，不需要借助任何现成的走法

然后。。。（连简单的最大最小值搜索都不会，你说nm呢）
但我还是拿最简单的井字棋开工了（唉！，当时还是太年轻啊）\

第一代井字棋（无需任何逻辑搜索，失败）

算了，不复习我写的代码了（头疼）
真的，我自己都看不懂（真佩服我当时的思维逻辑）
配个图，这复杂程度，震不震惊

反正想法就是

每步棋只用管自己的下一步（突然想到如果加上深度搜索可能会成功）
通过自我博弈来创建自己的棋谱库（每一步的得分）
每一步的得分就通过这一局的胜负进行统一计算（赢的加5分，输的-5，平局先手-2，后手0）
之后的下棋策略就通过搜索棋谱库来进行
以此循环往复来进行自我博弈\

程序训练过程

但注定是要失败的
我觉得失败原因有

• 没加上逻辑搜索，学习效率非常低（但加上后，对井字棋来讲，就不需要自我博弈了。。。）
• 自我博弈总是陷入循环（加上随机数依旧如此，这个原因还不明）
• 评分系统有很大问题（我后来好像改了，但忘了怎么改了）
• 而且棋谱库会非常庞大，搜索的时间可能会很长（用上图像识别会怎样）
• 甚至这种思路可能根本行不通

  第二代井字棋（全靠逻辑搜索，成功）

  现在回想起来，真的是入门
  核心代码只有这么几行\

  import numpy as np
  
  def evaluate(image, deep):
      poss = [(i, j) for i in range(3)
              for j in range(3) if rule(image, (i, j))]
      mark = np.zeros((3, 3), dtype='long')
      if deep == 0:
          return np.zeros((3, 3))
      for i in poss:
          if ck_over(image_to_pos(image, i)):
              mark[i] = mark[i] + \
                  score(image_to_pos(image, i)) * (deep**3)
          else:
              mark[i] = mark[i] - \
                  sum(sum(evaluate(-image_to_pos(image, i), deep - 1)))
      return mark

  一个简单的深度优先搜索（搜索深度为deep）
  得分规则也很简单

  赢，得分5
  输，得分0
  平局得分1

---

这篇文章，我竟然从年前写到年后
直接跳到第四代

第四代井字棋（真正的极大极小值搜索，再加上alphabeta剪枝）

极大极小值搜索

其实网上已经有很多关于这方面的内容了，我就不再写具体原理了（lazy）
我开始其实搞不明白，直到我把数状图画了下来

1是我走，-1是对方走
最下面画不下了，就竖着画了

简单原理

当我走时，取分数最高的

我定义的分数很简单：

我赢	平局	对方赢
3	2	1

对方走时，取分数最低的

因为对方肯定不想让你得分嘛（分越高越nb）

从最后的叶结点得分，然后向根结点一层一层返回

最后选取分数最高的下一步

然后的评估函数

image为当前的棋盘，player:1为我，-1为对方

例如：

棋	-	盘
-1	0	0
-1	0	0
1	-1	1

用3×3的numpy数组储存

得分也用numpy数组储存

上面棋盘得分为（0代表位置无用，没有任何意义）：

得	-	分
0	2	3
0	2	2
0	0	0

而且很明显3分那个位置是必胜的

def evaluate(self, image, deep, player=1):

    #找出可能位置
    poss = [(i, j) for i in range(3)
            for j in range(3) if self.rule(image, (i, j))]

    #初始化分数矩阵
    mark = np.zeros((3, 3), dtype='int8')

    #深度出口
    if deep == 0:
        print("too deep, return")
        return np.zeros((3, 3))

    #-------
    for i in poss:

        if self.over(self.image_pos(image, i)):#如果结束，获得分数
            mark[i] = self.score(self.image_pos(image, i))
        else:

            #下层分数矩阵
            next_layer = self.evaluate(-self.image_pos(image, i), deep-1, -player)

            #极大极小
            if player == 1:
                #如果下层是对方，对下一层取最小值
                mark[i] = np.min(next_layer[next_layer>0])
            else:
                #如果下层是我，对下一层取最大值
                mark[i] = np.max(next_layer[next_layer>0])
    return mark

然后你就会发现太慢了。。。
这时候就到aplha-beta剪枝出场了

alpha-beta剪枝

具体原理百度哈，我只简单说一下

简单的

还看着这张很丑的图

第三行第八个，这个是对方的，上下都是我的
它从下面得到分数2
由此可以知道它返回上层的分数肯定是<=2的（这一层取最小值）
那么对于上层来讲：有更高的分数3为什么还要2呢（上层取最大值）
因此可以将它后面的剪掉
上代码：

def evaluate(self, image, deep, player=1, alpha=1, beta=3):

    #找出可能位置
    poss = [(i, j) for i in range(3)
            for j in range(3) if self.rule(image, (i, j))]

    #初始化分数矩阵
    mark = np.zeros((3, 3), dtype='int8')

    #深度出口
    if deep == 0:
        print("too deep, return")
        return np.zeros((3, 3))

    #-------
    for pos in poss:

        if self.over(self.image_pos(image, pos)):#如果结束，获得分数
            mark[pos] = self.score(self.image_pos(image, pos))
        else:

            #下层分数矩阵
            next_layer = self.evaluate(-self.image_pos(image, pos), deep-1, -player, alpha, beta)

            #极大极小
            if player == 1:
                #如果这层是我，那下层就是对方，对下一层取最小值
                mark[pos] = np.min(next_layer[next_layer>0])

                #alpha-beta剪枝
                ##更新本层最大值alpha（如果有更大的值的话）
                alpha = max(alpha, mark[pos])
                ##如果本层的最大值（alpha）大于上层的最小值（beta，是从上层来的）剪掉
                if alpha > beta:
                        # print("剪枝", image)
                        return mark
            else:
                #如果这层是对方，那下层就是我，对下一层取最大值
                mark[pos] = np.max(next_layer[next_layer>0])

                #alpha-beta剪枝
                ##更新本层最小值beta（如果有更小的值的话）
                beta = min(beta, mark[pos])
                ##如果本层的最小值（beta）小于上层的最大值（alpha，从上层来的），剪掉
                if beta < alpha:
                        # print("剪枝", image)
                        return mark

    return mark

最后

半夜2点了，放几张图就该溜了
过几天再试试最开始的想法
谁有兴趣和它对战，联系我（谁稀罕这破代码。。。）