如何選擇算法？

Question

我必須爲給定問題選擇算法：

遊戲有兩個玩家：x和o。玩家輪流換人，在每場比賽開始時玩家x先移動。

當o開始於（8,8）時，玩家x從位置（1,1）開始。

每回合，只要她的路徑沒有穿過已經填滿或佔據的方格，玩家就可以象國王棋一樣在八個方向上移動。移動後，玩家空出的空間被指定爲填充，並且不能再移動。注意只有被佔用的空間被填滿，而不是整個路徑。

遊戲結束時，一個玩家不能再移動，而另一個玩家成爲贏家。給出的時間是1分鐘。

座標（1 1）指示電路板的左上角。

板被指定爲行列表。每一行是條目的列表：

• 是空方

• 被填充在方

x是X播放器的當前位置

Ø是o播放器的當前位置

這是一個本地搜索算法嗎或A *？這似乎與國際象棋類似，但同時我不能真正看到這個遊戲的目標......

謝謝！

Answer 1

這是一個zero sum game，有兩名球員，每個球員都對世界有充分的「知識」。

處理這些問題的一般方法是minimax algorithm。

算法思路簡而言之就是試圖找出每次移動的最大保證「值」。這是通過在你的回合中採用「最大」可能性和對手回合中的「最小」可能性來完成的（假設他也在試圖使他的利潤最大化，所以他的利潤最大化是使利潤最小化）。
該算法遞歸地查看所有可能的遊戲狀態達到一定的深度，並選擇你可以採取的最佳策略。

您可能需要一些啓發式函數來評估每個遊戲狀態（因爲由於分支因素較大，算法不太可能擁有整個遊戲樹）。該算法將使用此啓發式爲您和對方選擇最佳舉動。