最快連接4贏得檢查方法

Question

我試圖做一個ai跟隨alpha-beta pruning井字棋的方法。我需要儘可能快地檢查勝利，因爲AI會經歷許多不同的可能的遊戲狀態。現在我已經想到了兩種方法，但都沒有效率。

1. 創建一個大的元組，用於在連續的條件中對每一個可能的4進行評分，然後遍歷它。
2. 使用for循環，檢查水平，垂直，診斷面向左，診斷面向右。這看起來好像會比#1慢得多。

有人會推薦這樣做嗎？

Answer 1

從你的問題，你的方法將如何實施有點不清楚。但是從alpha-beta修剪，看起來好像你想看看很多不同的遊戲狀態，並且在遞歸中爲每個狀態確定一個「分數」。

一個非常重要的觀察結果是，一旦找到了一個4行，遞歸結束。這意味着在遞歸步驟開始時，遊戲板沒有任何4行的實例。

使用這個，我們可以直觀地看到放置在所述遞歸步驟中的新件必須是在遞歸步驟中創建的任何4行行實例的一部分。這大大減少了從69個（21個垂直，24個水平，12 + 12個對角線）4個行的位置到最多13個（3個垂直，4個水平，3 + 3個對角線）的解決方案的搜索空間， 。

這應該是您的第二種方法的基準。它需要最多52次（13 * 4）的檢查才能實現，或25次（6 + 7 + 6 + 6）檢查更快的算法。

現在很難擊敗25個布爾檢查，我會說這個雙贏檢查，但我猜你的＃1方法交易一些額外的內存使用，以減少每遞歸步驟的計算。這樣做的最簡單方法是存儲8個整數（單字節適用於此應用程序），它代表可在8個方向中的任何一個方向找到的最長的同色芯片鏈。

使用此功能，可以將支票的支票減少爲8個布爾檢查和4個添加。只需在新放置的芯片的兩側獲得鏈長，檢查它們是否與芯片顏色相同，如果是，則添加它們的長度並加1（用於新放置的芯片）。

從這個計算中，看起來好像你的＃1方法可能是最有效的。但是，它具有維護數據結構的更大的開銷，並且使用更多的內存，除非您可以通過引用傳遞，否則應該避免使用這些內存。另外（假設布爾檢查和添加的速度相似），即使在忽略開銷時，更困難的方法也只能獲得因子2。

我做了一些簡化，有些解釋可能不是很清楚，但問問你是否還有其他問題。