常见棋类AI复杂度介绍
本帖子是扫盲帖子，是关于棋类复杂度的介绍这里介绍五种常见棋类：黑白棋，五子棋，中国象棋，国际象棋，围棋
黑白棋：相当经典的游戏，因为棋盘为8X8大小，且每一步变化不多，估算的搜索空间复杂度为10的28次方
而小棋盘版的6X6黑白棋，已经被软件穷尽所有变化，证明是后手必胜，人们猜测8X8也是后手必胜
五子棋：虽然是经典游戏，但在加入禁手，三手交换，五手两打后，变得复杂化起来，特别是禁手会存在各种假禁手，
导致禁手判断的工作一点也不轻松，日本曾有人出的一些禁手题，还能难倒很多爱好者。
目前，即使先不考虑禁手规则，而棋盘大小为15X15的五子棋，
考虑了开局有很多不必要的着法，剪掉以后，空间复杂度仍然有10的105次方
如果加入禁手规则，会让空间复杂度略减（当有禁手点出现的时候），但禁手判断的复杂性，却填补了这个复杂度的减小，
反而使软件的复杂度更大（拖慢软件搜索速度）
中国象棋：几百年以来唯一规则没变化过的古老棋类，棋盘比国际象棋稍大（9X10），
总变化也比国际象棋略多一些，为10的48次方
国际象棋：国际上知名度很高的棋类，并且他的发明的传说也一样出名（就是第一个格子放一个谷子，后面每格是前面的两倍那个）
它的空间复杂度比中国象棋稍低，为10的47次方
围棋：当之无愧的复杂度之王，拥有19X19的超大棋盘，空间复杂度高达10的360次方，居棋类复杂度之首，并且远远抛离第二名的棋类
可能有些人认为，五子棋的AI比象棋AI要容易实现？按状态空间复杂度来看，显然不是这样，
那为什么产生这个错觉？这是因为他看到的只是着法生成的复杂度
着法生成是棋类AI的一个组成部分，着法生成显然和棋类规则的复杂程度有关。对于以上几种棋类，显然是中国象棋和国际象棋的着法最为复杂
但这并不表明这个棋类就复杂，规则更简单的围棋显然不是这样
我猜很可能是他只看到着法生成器的复杂度，因为只要有着法生成器，电脑就已经能应对下子了，
再加上简单的静态评估函数，就可以实现最简单的AI，即使根本没有进行搜索。
但不搜索的AI没有任何意义
如何公平比较AI的实现难度呢？这些棋类都是竞技棋类，有严格的水平段位制
和人类相同段位的棋手做比较，拿五子棋和象棋的话，我们假设和五子棋的初段棋手，和中国象棋的初段棋手来比
目前最顶尖的五子棋软件是黑石，但总体水平只达到了职业初段，虽然局部攻杀水平极高，但也不能和人类最高水平棋手相较量
最顶尖的中国象棋软件，很多，有倚天，旋风，天机，大圣，奇兵，其中大圣曾和许银川（九段）六战成和
如果说国际象棋，最出名的当数1997年的深蓝之战，3.5 : 2.5 击败了人类最顶尖的棋手
其实这也可见，这和棋类的状态空间复杂度有着密切的联系，较低的空间复杂度的棋类，机器在人类面前显得水平越强
特别是黑白棋，自从zebra的出现，就把人类最顶尖棋手远远抛离
更多的其它棋类状态空间复杂度的比较，可以见wiki百科：
http://en.
部分英文词汇：
Chess 国际象棋
Xiangqi 中国象棋
Gomoku 无禁手的五子棋（Renju才是有禁手五子棋的名字）
Reversi 黑白棋（另一名字是Othello）
Go 围棋
