实战项目：通过自我学习让AI学习五子棋 - 1 - 项目定义
项目介绍
五子棋是一种博弈游戏。在棋盘上黑子和白子交替落子，先于在任何方向上将至少五个棋子连在一起的一方获胜。在我们这个项目中我们尝试使用自学习的方法训练出一套走五子棋的算法。
这个项目本身并无特别大的实用价值。我们的目的在于：
- 尝试自我学习的方法，从实践中了解实际应用该想法的挑战和可能性
- 出于娱乐的目的，后期我们可以为该算法开发出一个UI，从而发布一个属于我们自己的五子棋游戏
- 相同的算法未来可以被应用以解决多个不同的问题
项目需求
我们对本项目有以下的需求：
- 分别针对先手和后手，产生出一套具有一定智能的五子棋算法
- 棋盘的大小为15行和15列
- 该算法可以被用来和某个UI即成以形成一个真正可以使用的电脑棋类小游戏
- 因为仅仅是学习的目的，这里的五子棋即是一般业余规则的五子棋，也就是没有任何限制的五子棋规则
- UI是可选的。我们先关注在后端任务，也是必要的任务的完成。根据具体的情况决定是否制作一个UI以更好的理解算法
算法描述
对于五子棋（或者任何一种棋类游戏），我们可以把它看成是一种状态转移的游戏。也就是说我们可以把当前的棋盘看成是当先状态。当我们在某个位置落子之后，棋盘就转移到下一个状态。因为棋盘上可能会有多个可供选择的落子店，也就是说有多个可供选择的未来状态，我们算法的任务就是从其中选择最优的（或者是较优的）状态进行转移。
假如是基于规则的算法，我们会预先根据各种情况定义很多规则来决定应该转移到哪一个未来状态。比如，如果我们下在一个位置就可以直接赢下比赛，我们就应该直接下载那个位置；否则如果对手下在一个位置就直接赢下比赛，我们应该考虑先占有那个位置，等等。在这里我们想尝试使用另一种算法，让机器通过自我对弈最终产生一个较优的算法。
在描述算法思路前，我们先定义几个术语：
- 状态：棋盘上黑白双方全部落子的位置的集合
- 当前状态：在当前的最新状态
- 下一状态：在当前棋盘上任何一空白处落子后所形成的状态
- 状态转移策略：决定从当前状态转移到哪一个下一状态的决定
我们的算法思路如下：
- 获取当前棋盘所对应的状态信息；
- 在当前状态所对应的所有下一状态集合中，随机选择最优状态中的一个，并将当前状态转移到下一状态；
- 如果棋局已经结束，对于赢的一方所有被选择的策略权重加一，对于输的一方所有被选择的策略权重减一；否则重新进入步骤1。
在这个算法中，我们看到如果某一个状态转移策略失误，最终导致棋局落败，那个该策略的权重就会被降低；相反，如果一个策略是较优的策略，也就是最后导致赢下了棋局，该策略的权重就会提升。当然，更多的情况我们会看到好的策略和不好的策略共同出现在一个棋局中。我们希望通过足够多的对弈最终让好的转移策略和不好的转移策略可以区分开，这也就是学习的过程。
项目架构
我们的程序是一个单机程序。大体上我们可以认为我们的程序可以分为三个层次，如下图所示：
- UI Controller：获取并在UI上显示当前的状态
- Policy Engine：更具当前的状态和历史的策略权重，决定转移到哪一个下一状态
- DAO：即data-access-object，负责从文件读取历史状态和转移策略的信息和将新的状态和转移策略写入到文件中
技术选择
- 后端编程语言：python
- 前端编程语言：[pygame](https://www.pygame.org/news)
- 状态和转移策略的存储：文件
相关资源
- codes repository
- project track