gobang

我的一个学习python语言的练习。这也是大学时候的一个小想法，20年后开始实现一下。

目标

基础目标：利用pygame库，构造一个结构完备，流程完善的五子棋游戏。扩展目标：作为标准平台，为以后学习AI的机器学习，剪枝搜索算法等提供实践平台。

流程

游戏开始后，显示封面。（仪式感）点击任意位置，进入选择对手页面。在选择对手页面首先选择是人人对弈还是人机对弈。如果选择的是人机对弈，则选择对弈的对手。每一个不同的电脑对手对应一个不同的博弈算法。如果以后学习了AI构造了不同算法，可以用插件的方式安装到这个程序上。完成选择后，点击"开始"按钮，开始对弈。初始化棋盘和数组。人机对弈时玩家执黑先行（目前没有换手和禁手规则，执黑理论上永远立于不败），玩家和程序依次落子。每次落子程序执行判胜检验，如果一方获胜则终止棋局，显示"Player1获胜！是否再来一局？（Y/N)",玩家键盘输入Y或者N，输入Y重新开具，输入N关闭程序。

流程思路

实际上，因为基于游戏设计的原因，这不是一个纯粹的面向过程的程序。

while 未判胜：
    if 当前player=玩家：
        for event in event.get()：
            if 玩家点击落子：
                记录新落子
    else：    
        if ai线程返回下一步棋：
                记录新落子

    if 有新落子：
        if 判胜():
            显示XX获胜
        else:
            更新棋型表
end

基于游戏设计，所有处理要在fps时间片内完成，才能保证显示效果。如果一个处理过程不能在一个时间片内完成，就会造成显示卡顿。假设AI走棋算法非常复杂，或者基于网络传输延迟不可控，落子时间超过一个时间片，就会影响基于fps的其他程序。例如基于时间片显示动画，如果一个落子算法跨越了多个时间片，要么动画变成慢动作要么动画丢帧。

所以，机器落子采用单独起线程的办法，计算落子不影响主线程的循环，计算完成后将结果返回主线程。

判胜

每次落子，以落子为中心，横、竖、左斜、右斜四条斜线上有连续5个同颜色子则判胜。构造两个嵌套的循环，外部循环是四条线，内部循环是两个方向。沿着一套直线的一个方向，如果遇到一个同颜色的棋子，则计数器加一，如果计数器为5则判胜。如果遇到一个其他色棋子或空点，则进入下一个循环。所有循环结束则，则未出现胜局。

规则

无禁

完全没有禁手规则，黑方有巨大优势。

有禁手

黑棋不得走禁手步。包括三三、四四和长连。如走出禁手步直接判负。

三手交换

如人人对弈时，白方在第三手时可以提出交换。

五手两打

如人人对弈时，在盘面第五手白方可以在黑方的两步棋中指定一步。

程序博弈算法一

先不考虑禁手与换手，沿用基本规则。则黑方必胜。

五子棋棋型可以分为"活"和"冲"两大类。活四表示有两个点可以成五的四，活三表示再走一步可以形成活三的棋型，活二表示再走一步可以形成活三的棋型。冲四表示再走一步可以形成五的棋型，再走一步可以形成冲三的棋型叫眠三，同理再走一步可以形成眠三的棋型叫眠二。

冲四只有一种棋型，就是 +OOOO+，+号代表空位，O代表某种颜色的棋子。

可见，活的棋型，有以下特点：

* 连续六个点
* 开始点和结束点均为空
* 只有一种颜色的棋子

从概率可知，活四的棋型，可以有四种活三棋型构成，每种活三的棋型，又可以由两种活二的棋型构成。排除掉相同棋型，则可以统计出：

1. 活四棋型只有1种 (30)
2. 活三棋型只有4种 (14,22,26,28)
3. 活二棋型只有6种 (6,10,12,18,20,24)

（括号里的数字表示棋型的二进制数字）

类似，冲的棋型，有以下特点：

* 连续五个点
* 这五个点的任意一端的下一个点要么是边界外、要么是对方棋子，不能同时为空点
* 只有一种颜色的棋子

从概率论可知，一共有有5种冲四棋型，每种冲四棋型可以有四种眠三棋型，每种眠三棋型，可以有三种眠二棋型。排除掉相同棋型，可以统计出：

1. 冲四棋型有5种  (15,23,27,29,30)
2. 眠三棋型有10种 (7,11,13,14,19,21,22,25,26,28)
3. 眠二棋型有10种 (3,5,6,9,10,12,17,18,20,24)

博弈的思路是：

先看看是否有己方一步赢棋的棋型，就是活四和冲四，如果有则直接赢棋。再看看是否有己方活三这种无法防守的棋型，构造活四。
然后防守对方的活三和冲四。
构造己方的活三和冲四。
防守对方的活二和眠三。
构造己方的活二和眠三。

第一版只是简单的按照上述思路完成功能。之后可以根据这个结构继续改进，例如探索如何一个子防守尽可能多的对方棋型等。

建立棋型库的算法

因为前一节计算出的棋型是不分方向的，所以在统计机型数据，建立棋型库的时候只要计算出横竖左斜右斜四条线上所有的存在的棋型记录下来即可。

记录的数据包括：棋型种类（活四、冲四、活三、眠三、活二、眠二）,棋型起始坐标（x,y),线的方向（横，竖，左斜，右斜），棋型布局（15，23……）

其中，横、竖、左斜、右斜，默认设置方向为从左到右，从上到下，从右上到左下，从左上到右下。

这样，可能的起始点分别为：

*横 (0,0)->(10,14) *竖 (0,0)->(14,10) *右斜 (0,0)->(10,10) *左斜 (4,0)->(14,10)

redknox/gobang