解決點和盒子游戲是否可行？

Question

我試圖證明可計算性的遊戲是Dots and Boxes。

但是，我試圖通過創建一個應該在玩家1或玩家2中在該遊戲中具有100％勝率的AI來實現這一點。 如果創建100％winrate AI是不可能的，那麼我的目標就是創造一個至少比所有其他AI更好的人。截至目前，我正在使用PHP編寫所有內容，因爲我正在與另一種用腳本語言編寫的AI進行競爭。

這整個事情是遞歸的，其基本邏輯是： 計算所有可能移動的整個樹木 如果是我的AI輪到，那麼選擇最大AI點數的路線。如果是輪到對手的AI，那麼選擇AI數量最少的路線。 Aka計算每個節點的保證點數。

計算完整樹後，選擇具有最高保證點數的路線。在偶數點上，隨機挑選。

這整個計算過程大概需要永遠在15x15板上進行計算，但是現在我要做的就是在3x3矩陣上進行計算。爲了現在必須重新計算它們，我將爲數據庫中的前6-8次移動存儲最佳移動，這將改變每個計算從24開始的複雜度！到18 !.

這整個事情是可行的嗎？我的計算方式有問題嗎？有一個更好的方法嗎？

Answer 1

這個問題有一個非常大的搜索空間，對於一個4x4的網格，我們在搜索空間中有40個邊緣和2^40個狀態。由於這個原因，完全不可能爲整個遊戲解決更大的地圖。

有什麼解決方案？首先你可以看看Barker和Korf的作品Solving Dots-And-Boxes。這是這種問題的最先進的狀態（2012年，也許現在，我不知道）。他們將經典的Alpha-Beta修剪算法與一組問題特定解決方案結合使用。

您也可以嘗試將Monte Carlo Tree Search應用於該問題。我不知道在這個方向上的作品，但蒙特卡洛已經被證明在圍棋遊戲中取得了成功（這在某種程度上類似於你的問題）。

Answer 2

機器學習應該通過消除許多最初具有不良結果的分支來減少計算時間。它可能需要更多的時間來解決像3x3板這樣的小問題，但是當你在更大的板上開始測試你的算法時，它會（我不能肯定地說沒有寫出算法和嘗試它們）會更快，因爲它應該是at = log（n）函數的一些變量。

例如，使用Reinforcement Learning它將基本上做你的建議，計算一個大規模的決策樹。但是，它會知道一些舉措（例如那些給對手一個盒子的舉動）是不好的，它不會浪費盡可能多的時間計算移動成功。

它可行嗎？取決於你有多少免費處理時間。使用一個小網格，直到你有一個體面的人工智能算法編寫，然後你可以運行一臺機器，看着它自己學習。沒有什麼比看着你的創造學習更令人滿意的了。這就像有一個嬰兒......一個可以在Dots and Boxes打敗你的人。