在之前发的贴: 软件分享 – 智慧中国象棋 (Chinese Chess)
有朋友就问我, 你这到底是怎么实现的呀?
在我看来, 有两种算法来实现棋类博弃(中国象棋, 国际象棋, 五子棋等等). 这些棋类博弃的游戏一般有以下特点:
- 两人轮流玩
- 棋盘上的信息都是公开的
- 棋手的目标是相反的, 一个取最大, 另一个取最小. 比如象棋中对棋盘的估值无穷大为对黑方执子有利(黑方胜)而无穷小则为对红方有利(红方胜).
模式化的棋类算法
第一种实现方式(就是我12年前的实现方式), 也是最为传统的实现方式, 就是搜索+剪枝. 搜索是在搜索树上(最大最小数 min-max tree), 树的根节点是棋盘的初始状态, 然后比如红方走一步(目标取最小), 搜索树就往下走一层, 然后轮到黑方走(目标取最大), 以此类推.
中国象棋的分支很多(每一轮棋子的走法开盘有十几种), 这么一算来, 这棵树就很庞大, 暴力搜索完肯定是不行的. 这时候通过剪枝就能大大减少计算量.
最有名的剪枝就是 Alpha beta pruning. 通过 alpha beta 剪枝往往能提前抛弃一棵庞大的子树枝, 因为根据推理不用算也可以知道即使算出来结果也没有相邻节点的已经计算出来的值好, 所以可以果断抛弃.
alpha-beta-pruning
当然存的 Alpha beta 剪枝还需要进一步通过其它技巧来加速. 比如缓存历史上已经计算过的节点的值, 还有通过加入一些人为的经验(比如马后炮或者其它一些经典棋局)可以进一步进行剪枝.
一个棋类游戏主要的几个模块: 棋子走法生成器, 棋盘估值(比如车比马值钱, 残局中马比炮值钱), 还有就是搜索剪枝. 大家要是感兴趣可以到我的帖子中下载 程序哈.
I wrote a Chinese Chess Program 软件分享: 智慧中国象棋 (Chinese Chess)
机器学习的棋类算法
最近几年大数据很火, 主要是因为计算机越来越快越强大, 硬盘越来越不值钱, 可以存的数据量是海量了. 这时候通过大数据分析行为模式来预测下一步走法 就比较流行了, 比如GOOGLE的那个 DeepMind (英国伦敦) 就是通过机器学习, 学习了上万盘棋局得出一些行为模式. 这种潜力是无限的: 因为机器可以日夜不停的快速学习前人的经典棋局, 从而规避胜率较低的走法.
一般来说, 谈机器学习 (Machine Learning), 的基础就是大数据, 没有大数据的支持, 再牛B的机器学习算法也是个空架子.
英文: The Chess AI – Model Base or Machine Learning
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK