这篇博客要讨论一个问题,就是如何让计算机下棋?
有如下三种形式:
1.同人类的做法一样,分析局势,和将帅的安全性,这里会有一些分析策略,还有一些战术,这些混合在一起,最终得到下一步要走哪.不过很遗憾的是,如今的程序都不知道如何包含这类东西.
2.使用 IF-THEN 结构
以这种结构,如果第一步走什么,那么后面可以走哪些步.
3.向前看并进行评估
选择下面最好形式的一个,要做到这点,我们需要设法评估这些形式,确定其中哪个是最好的.要评估形式的好坏需要一系列的特征,比如:f1,f2,f3.....fn,在此基础上我们可以对这些特征建立一些函数,通过这个函数来计算形式的对应值,一般而言,这个函数可以用线性多项式表示:
,这就是博弈的一种方式.
4.或者是一棵包含所有肯能性的树,然后按照人类下棋的形式,我走一步,你走一步,可以我走五十步,你走五十步.
每一层都有好几种选择方式,每一层选择方式的数量,标准叫法是分支因子b,树的深度为d,本例为2,同时还会有一定数量的叶子节点,有b^d个节点,本例中为3^2 有9个叶子结点.
假设标准的一局每个棋手要下50步,,这样d就大约等于100,根据香农定理,最后结果大约有10^120方个叶节点,如果用暴力搜索的方式去评估,那所花费的时间将会是一个天文数字.
4.极大极小化算法
