开篇的一点碎碎念
一直没想好博客的第一篇正式文章该写什么，毕竟最近刚找到实习的公司，忙着适应工作和学习相关的技术，所以自从博客搭好后就没时间学点自己感兴趣的东西，自然也就不知道记录啥了。
大学开始学编程，慢慢的写过一些程序后，就想花时间把算法和数据结构系统的学一遍，但是一直没有下定决心。拖到现在，工作了，反而不知道从哪里开始学了。
AI一直是我比较感兴趣的一个方向，从小就喜欢看各种科幻电影和小说，梦想着有生之年能有一个真正意义上的人工智能出现，虽然目前看来还很遥远，但还是有一大批人为这个目标而努力着。而在计算机方面，各种游戏的AI也是热门的研究方向，特别是棋类AI。所以这次我就想编写一个完整的五子棋游戏，以及实现一个水平相对较高的五子棋AI来开始我的算法学习之路。
目前计划将AI作为算法专题的第一个系列，而五子棋AI因为资料相对较多较完善，所以先实现它。
（后续应该还会实现2048、俄罗斯方块、贪吃蛇等经典游戏的AI，算法将侧重于实现一些物理和动画效果）
作为这个五子棋AI系列的第一篇文章，就简单的概述下五子棋及其AI的发展历史和现状。
说是概述，其实就是瞎扯点自己在网上了解到的东西，因为大部分资料在网上基本都能找到，这里并不是写论文，只是总结一些重点，方便大家理解。
五子棋介绍
种类及区别
先说说五子棋吧，通常大家玩的五子棋分为带禁手和不带禁手两个版本，
（前者称之为*连珠Renju，后者一般称之为五子棋Gomoku*）
然而无论哪一个版本，先手黑棋均必胜。
（所谓黑必胜的意思是，只要黑棋按照一定的方式下，白棋选择棋盘上的任何一个点都不可能赢棋。）
（传统五子棋规则以及禁手的定义不再赘述，请自行百度谷歌）
这里只说结果，至于为什么参考文末资料：
1992年Victor Allis通过编程证明不带禁手的五子棋，黑必胜。
2001年Janos Wagner第一次证明的带禁手的五子棋，也是黑必胜。
先手优势及棋谱介绍
黑棋的优势到底有多大呢？在26个职业开局里，已经发现有19个是黑棋必胜的（一打必胜）。
因此为了进一步削弱黑棋的优势，国际上推出五手两打的规则。
(就是黑棋的第三步需要下两个点，但由白棋挑选让其下较弱的哪一个)
可是人们发现黑棋带禁手依然是必胜。
从实践的角度来讲，网上是可以搜索地毯谱的，一般在几百兆左右，可以用renlib软件打开，所谓地毯谱的意思就是**黑棋会指定下法，但白棋每一步都可以选择棋盘任意位置，最后黑棋必胜。**也就是说，只要按照此棋谱下棋，五子棋世界冠军都一定会输给你。
（ 目前花月、浦月、云月、雨月、峡月、溪月、金星、水月、寒星、明星、岚月、新月、名月，山月，残月都是五手两打必胜）
那么正式的比赛是怎么玩的呢？
现在的正式比赛通常会常用三手交换、五手两打这些复杂的规则来平衡比赛，但这些规则的各个分支也是逐渐被人破解，
五子棋的比赛已经很大程度不是在考验自己的临场发挥，而是考验选手对于少量黑白平衡 分支的记忆情况。
广义的五子棋
不带禁手的五子棋是属于一类更为普遍的*m,n,k游戏的一种特例，既15,15,5。**m,n,k游戏是指m行n列，轮流下子，连成k个算赢。**这个在数学中专门的研究如果在最理想下法（Perfect Play）的情况下有什么样不同的结果，比如标准的三连棋（Tic-tac-toe）*是3,3,3是一个平局，同样只有六路棋盘的五子棋也是平局，当然上面我们已经说明了15,15,5是先手必胜，还有研究发现11,11，5也是先手必胜。m,n,k游戏只有先手必胜和平局两种结果。由于每下一个子都一定会对下子一方那一方有优势，所以可以通过反证法证明m,n,k游戏里不可能有后手胜利的情况。如果后手有胜利的方法，那么先手可以提前借鉴（Strategy stealing）过来实现必胜。
五子棋的介绍到此结束，接下来正式进入AI的介绍。
AI介绍
由于AI的部分内容太多，我们只关心和接下来程序开发相关的部分，所以这里仅列出几个主要问题及解答作为介绍。（欲知详细请参考文末列出的资料内容）
-
传统规则下，无禁手和禁手不是已经都证明了先手必胜么，那人类和AI下还有意义么，如果设计一个算法让电脑一定能找出必胜下法，那人类必输啊？
事实上AI先手，人类确实必输，但并非无意义。无禁条件下，如果不指定算法，人类也未必会输。而接下来我们要开发的AI，就是在无禁条件下的。
（AI强制执黑而且必胜的软件，例如*五子棋终结者*） -
在哪些规则下AI必胜，人类的比赛规则下AI也是必胜的么？
如上面所说，带禁手和不带禁手的五子棋，以及部分典型规则下的五子棋，黑必胜，而人类的正式比赛因为有交换和换打的思想，所以ai不是必胜的了。 -
人类比赛有哪些典型规则来限制AI？
Gomocup比赛使用的就是Prepared Balanced Opening等专家提供的开局，通常认为较平衡且AI没有必胜下法。（现在Gomocup提供三种规则Freestyle、Standard和Renju，由于比赛的时候通常会提供没有找到必胜下法的开局，所以可以认为它是没有必胜下法的，虽然不排除有必胜下法但没找到） -
AI vs AI，AI vs 人类，这两个AI的设计概念一样吗？
不一样。你现在看起来可以和AI玩是因为这AI不是为了和你下棋而设计的，它是为了和其他AI玩gomocup才弄出来的，和人玩五子棋与和电脑玩的策略是完全不一样的，你不能说对它赢比输多就证明人能赢AI，因为如果写AI的目的是和人玩，那作者很多地方根本就不会这么写，更不会放着巨大的漏洞给你出骗招。
[1] Kai Sun,Gomoku/Renju Resouces-An Overview,gomoku,renju,resource,Last update: 2016-7-26.aiexp.info/gomoku-renju-resources-an-overview
[2] Gomoku,From Wikipedia,the free encyclopedia,last modified on 26 August 2016, at 11:43.Gomoku,From Wikipedia, the free encyclopedia
[3] Louis Victor Allis,Searching for Solutions in Games and Artifcial Intelligence,Voor Petra en Cindy.Searching for Solutions in Games and Artifcial Intelligence
[4] Janos Wagner,SOLVING RENJU,Budapest,Hungary.SOLVING RENJU