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

分享讨论IT相关的内容
回复
头像
ejsoon
圈圈精英
圈圈精英
帖子: 2173
注册时间: 2022年 11月 18日 17:36
为圈友点赞: 96 次
被赞次数: 92 次
联系:

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

帖子 ejsoon »

這裡是我向弈棋程序大神,sanmill的作者,學習弈棋AI製作的筆記。

sanmill是目前AI難度最高、玩家最多的直棋程式,現已跨平臺,支持Android、IOS、Windows、Linux。歐洲也有一大批忠粉,因為歐洲人也玩九子棋。

我一直想學習弈棋AI,已經想了十幾年了。借此機會,真的要好好了解一下。

希望大家不吝賜教!
https://ejsoon.win/
天蒼人頡:發掘好玩事物
头像
ejsoon
圈圈精英
圈圈精英
帖子: 2173
注册时间: 2022年 11月 18日 17:36
为圈友点赞: 96 次
被赞次数: 92 次
联系:

我之前用深度算法來找出多聯骨牌解法

帖子 ejsoon »

图片
https://ejsoon.win/
天蒼人頡:發掘好玩事物
头像
ejsoon
圈圈精英
圈圈精英
帖子: 2173
注册时间: 2022年 11月 18日 17:36
为圈友点赞: 96 次
被赞次数: 92 次
联系:

to calcitem,想知道如何能在1秒內算出多聯骨牌解法

帖子 ejsoon »

多聯骨牌由是12塊不同的立體,每一塊由五個立方體構成。

它的一些題目是很難的,比如下圖,只有4種解法,基本上用人腦是很難解出來的。

图片

這道題,我在兩年多前,用兩個多月的時間,想不借助電腦,徒手找出答案。但是我失敗了。

後來,我用python花一周時間,寫了個暴力破解程式,之後就找到了2組解法。

當時是從下午三點左右開始跑,跑到六點左右,得到一組,再過了幾個小時,又得一組。

但是,接下來還有兩組,我估算了下,用我這個python代碼,可能要跑大概45日,才能找到。

可能在找到之前,我的破電腦就已經冒煙了。

後來我去pentoma.de下載到一個破解器.exe,它只要一秒就能找到全部四組解法!

我的問題就是,它如何能在1秒內找到全部的解法?除了溯洄之外,還用到哪些高科技?

根據我的理解,你說的「溯回法」應該就是深度優先算法。也就是一條道走到黑,再返回上一個分岔口,再走另一條道,直到看見亮光。

但是12!種可能還是有點太多了,要跑很久。

象棋軟件的做法是,製作開局庫,因為開局變化很多,如果從開局開始算,會很耗時,計算量太大。

而多聯骨牌是不可能有「開局庫」的,因為不管我們給它甚麼圖形,它都能立即算出,它應該是從頭開始算…

所以我想知道深度優先算法,還要依靠甚麼輔助算法…
https://ejsoon.win/
天蒼人頡:發掘好玩事物
头像
Calcitem
圈圈新人
圈圈新人
帖子: 3
注册时间: 2023年 1月 23日 20:13

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

帖子 Calcitem »

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++ 的基础上进行的比较,如果使用 Python,大约比 C/C++ 会再慢 50 倍左右),将运行时间减少到大约 0.167 秒。以这种速度检查每一个可能的解决方案的时间开销是极少的。

算法是比较复杂的,我对算法也不太擅长,长项只是做工程,能搜罗各种资料拼接到一起形成产品化的程序。

Sanmill 的 AI 難度准确而言是在未联网读取云库,未加载完美数据库的前提下是最优的,但是还有很多改进空间。核心的搜索算法函数的规模只有 Stockfish 的 1/5 左右,很多细节未处理。目前优化的方向,一是将局面评估公式的系数通过机器学习的方式获取更优值,二是借鉴 Stockfish 的做法加入 NNUE。

弈棋 AI 最基本的三大组件是搜索函数、局面评估函数和棋规逻辑实现。其中搜索函数无论如何优化,基本上是 Alpha-Beta 算法的变体。而局面评估函数则依赖于对这种棋类的深刻理解,需要丰富的对弈经验,这方面我是极度缺少经验的,还望不吝赐教!
头像
ejsoon
圈圈精英
圈圈精英
帖子: 2173
注册时间: 2022年 11月 18日 17:36
为圈友点赞: 96 次
被赞次数: 92 次
联系:

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

帖子 ejsoon »

Calcitem 写了: 2023年 1月 23日 20:54 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++ 的基础上进行的比较,如果使用 Python,大约比 C/C++ 会再慢 50 倍左右),将运行时间减少到大约 0.167 秒。以这种速度检查每一个可能的解决方案的时间开销是极少的。

算法是比较复杂的,我对算法也不太擅长,长项只是做工程,能搜罗各种资料拼接到一起形成产品化的程序。

Sanmill 的 AI 難度准确而言是在未联网读取云库,未加载完美数据库的前提下是最优的,但是还有很多改进空间。核心的搜索算法函数的规模只有 Stockfish 的 1/5 左右,很多细节未处理。目前优化的方向,一是将局面评估公式的系数通过机器学习的方式获取更优值,二是借鉴 Stockfish 的做法加入 NNUE。

弈棋 AI 最基本的三大组件是搜索函数、局面评估函数和棋规逻辑实现。其中搜索函数无论如何优化,基本上是 Alpha-Beta 算法的变体。而局面评估函数则依赖于对这种棋类的深刻理解,需要丰富的对弈经验,这方面我是极度缺少经验的,还望不吝赐教!
你講了不少專業名詞,我需要去逐個搜索研究才能看懂…

關於算法:

我看到直棋程序裡有「alpha-beta、PVS、MTD(f)」三種算法,請問這些算法是一整套可以直接使用的模塊,還是說只是概念?這些算法之間有何區別?


之後我去找了一些資料,然後…我先研究一下…

https://zhuanlan.zhihu.com/p/65108398?utm_id=0
https://ejsoon.win/
天蒼人頡:發掘好玩事物
头像
Calcitem
圈圈新人
圈圈新人
帖子: 3
注册时间: 2023年 1月 23日 20:13

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

帖子 Calcitem »

也可以借助 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: https://www.xqbase.com/computer/advanced_pvs.htm
MTD(f): https://www.xqbase.com/computer/basic_advanced.htm

后两种算法,其实我理解起来也是有些云里雾里的,只是照葫芦画瓢实现,大体上理解为这两种算法是进行一些假设,以加快剪枝速度,MTD(f) 的猜测更激进一些,也更不稳定。
头像
ejsoon
圈圈精英
圈圈精英
帖子: 2173
注册时间: 2022年 11月 18日 17:36
为圈友点赞: 96 次
被赞次数: 92 次
联系:

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

帖子 ejsoon »

Calcitem 写了: 2023年 1月 25日 00:12 也可以借助 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: https://www.xqbase.com/computer/advanced_pvs.htm
MTD(f): https://www.xqbase.com/computer/basic_advanced.htm

后两种算法,其实我理解起来也是有些云里雾里的,只是照葫芦画瓢实现,大体上理解为这两种算法是进行一些假设,以加快剪枝速度,MTD(f) 的猜测更激进一些,也更不稳定。

你給的中文資料很有用,目前我正在學習中…

我目前的理解,α-β算法用於二人博弈遊戲,α跟β相當於兩個人,每個人都會聰明的選擇對己最有利的,而對己有利就等於對敵方不利。

剪枝的依據應該是價值判定,對於象棋或直棋等吃子類弈棋而言,棋子數量應該是一個最大的價值判定(因此我有時能用棄子戰術贏某些象棋軟件)。

可否講解一下sanmill的局面評估函數?除了棋子數量之外,還有哪些評判標準?

另,圍棋一直無法用傳統算法實現高棋力,原因我認為還是無法評估局面。是否如此?
https://ejsoon.win/
天蒼人頡:發掘好玩事物
头像
ejsoon
圈圈精英
圈圈精英
帖子: 2173
注册时间: 2022年 11月 18日 17:36
为圈友点赞: 96 次
被赞次数: 92 次
联系:

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

帖子 ejsoon »

另,據我了解,弈棋的溯洄算法,一般是「廣度優先」,即先算完某一層,再算下一層。是否如此?
https://ejsoon.win/
天蒼人頡:發掘好玩事物
头像
Calcitem
圈圈新人
圈圈新人
帖子: 3
注册时间: 2023年 1月 23日 20:13

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

帖子 Calcitem »

每個人都會聰明的選擇對己最有利的,而對己有利就等於對敵方不利 —— 这是 Minimax 的算法思想,Alpha-Beta 强调的是 Minimax 算法基础上的剪枝,α 跟 β 是表征结点的特征,和人应该没有关系。

Sanmill 的局面评估函数在 https://github.com/calcitem/Sanmill/blo ... aluate.cpp 实现,简单而言,就是双方棋子数的差乘以 5,再加上双方可走的着法数即可移动性之差。5 可能不是最优值,后续考虑通过机器学习的方式找到最优值,并考虑在不同阶段,如摆棋和走棋分别使用不同的值。目前这个公式是经过机器自对弈九子直棋观察胜率调出的粗略值,对于十二子直棋而言,可能不需要考虑可移动性,暂未通过自对弈调优这个公式。

回溯算法就是残局每个局面都需要遍历到,只是直棋可以有多达16种局面变换方法,如旋转,转置,镜像或上述方式的组合,共16种,所以一种局面可以衍生出16种,在做回溯算法时可以利用这一点来节省残局库的存储空间。
头像
ejsoon
圈圈精英
圈圈精英
帖子: 2173
注册时间: 2022年 11月 18日 17:36
为圈友点赞: 96 次
被赞次数: 92 次
联系:

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

帖子 ejsoon »

Calcitem 写了: 2023年 1月 25日 12:08 每個人都會聰明的選擇對己最有利的,而對己有利就等於對敵方不利 —— 这是 Minimax 的算法思想,Alpha-Beta 强调的是 Minimax 算法基础上的剪枝,α 跟 β 是表征结点的特征,和人应该没有关系。

Sanmill 的局面评估函数在 https://github.com/calcitem/Sanmill/blo ... aluate.cpp 实现,简单而言,就是双方棋子数的差乘以 5,再加上双方可走的着法数即可移动性之差。5 可能不是最优值,后续考虑通过机器学习的方式找到最优值,并考虑在不同阶段,如摆棋和走棋分别使用不同的值。目前这个公式是经过机器自对弈九子直棋观察胜率调出的粗略值,对于十二子直棋而言,可能不需要考虑可移动性,暂未通过自对弈调优这个公式。

回溯算法就是残局每个局面都需要遍历到,只是直棋可以有多达16种局面变换方法,如旋转,转置,镜像或上述方式的组合,共16种,所以一种局面可以衍生出16种,在做回溯算法时可以利用这一点来节省残局库的存储空间。
謝謝!我這幾日研究下,有問題再來問…
https://ejsoon.win/
天蒼人頡:發掘好玩事物
回复

在线用户

正浏览此版面之用户: Google [Bot] 和 2 访客