搜索找到 3 个匹配

Calcitem
2023年 1月 25日 12:08
版面: 玩机交流
主题: 弈棋AI的實現(學習中…)
回复总数: 9
阅读次数: 607

Re: 弈棋AI的實現(學習中…)

每個人都會聰明的選擇對己最有利的,而對己有利就等於對敵方不利 —— 这是 Minimax 的算法思想,Alpha-Beta 强调的是 Minimax 算法基础上的剪枝,α 跟 β 是表征结点的特征,和人应该没有关系。 Sanmill 的局面评估函数在 https://github.com/calcitem/Sanmill/blob/master/src/evaluate.cpp 实现,简单而言,就是双方棋子数的差乘以 5,再加上双方可走的着法数即可移动性之差。5 可能不是最优值,后续考虑通过机器学习的方式找到最优值,并考虑在不同阶段,如摆棋和走棋分别使用不同的值。目前这个公式是经过机器自对弈九...
Calcitem
2023年 1月 25日 00:12
版面: 玩机交流
主题: 弈棋AI的實現(學習中…)
回复总数: 9
阅读次数: 607

Re: 弈棋AI的實現(學習中…)

也可以借助 ChatGPT 来辅助理解。ChatGPT 擅长解释复杂的概念。 Alpha-Beta、PVS、MTD(f) 这几种算法可以说是概念,在不同的编程语言中有不同的实现,基本流程相同,即均可以用伪代码描述。 PVS 比 Alpha-Beta 约提升 10% 的效率,MTD(f) 比 PVS 提升 5% 的效率,不过对直棋这类评估函数很简单的棋类才能发挥威力,如果评估函数复杂,会有反效果。 你找到的资料通俗,很值得一读! 当时开发直棋时则是主要参考了如下资料: Alpha-Beta: https://www.xqbase.com/computer/basic_search.htm PVS...
Calcitem
2023年 1月 23日 20:54
版面: 玩机交流
主题: 弈棋AI的實現(學習中…)
回复总数: 9
阅读次数: 607

Re: 弈棋AI的實現(學習中…)

Hi! 谢邀。 从 https://github.com/altayhunter/Pentomino-Puzzle-Solver 的讯息看,Donald Knuth 在 2000 年发表了一篇题为 Dancing Links 的论文 https://arxiv.org/pdf/cs/0011047.pdf ,其中他描述了一个双链环面数据结构和一个他命名为 Algorithm X 的算法来解决这个五联骨牌的问题。它用简单的非对称指针操作取代了在矩阵中删除和重新插入行和列的昂贵作业。因此回溯只涉及指针赋值而不是移动整个矩阵。实施这种方法将代码的效能提高了 500000 倍 (是在 C/C++ 的基...