棋盤遊戲AI設計：選擇STL數據容器

Question

我正在爲一個簡單的棋盤遊戲編寫一個AI引擎。現在我的簡單實現是遍歷所有可選的棋盤狀態，根據遊戲規則和我的簡單算法對每個狀態進行加權，然後根據該得分選擇最佳棋步。由於評分算法是完全無狀態的，因此我希望通過創建一些（所有？）棋盤配置的哈希表來節省計算時間，並從那裏獲得得分而不是實時計算得分。

我的問題是：
1.我的方法是否合乎邏輯？ （如果沒有，你能給我一些提示，以便更好嗎？:)）
2.什麼是最適合我的需求的線程安全的STL容器？我正在考慮使用char數組（板配置）作爲關鍵字，並將得分作爲值。
3.你可以給我一些提示讓我的AI成爲一個殺手鐗？ :)

編輯：更多信息：
董事會是10x10，有兩個玩家，每個有10個兵。規則很像跳棋。

Answer 1

是的，通常會將評估板存儲到散列表中，它被稱爲換位表。一個STL容器可能是std::vector。一般來說，你必須創建一個哈希函數（例如zobrist hashing）。散列函數計算特定板的散列值。 hash_value modulo HASH_TABLE_SIZE的結果將是std::vector的索引。

換位表項可不僅僅是板得分和最佳移動存儲更多的信息，你也可以存儲深度董事會評估其如果評價分數（如果你是做α-β搜索）是

• 確切
• 一個上界
• 或下界

我可以推薦chessprogramming網站，我從中學到了很多。尋找術語alpha-beta,換位表,zobrist哈希,迭代加深。也有進一步閱讀好論文：

• TA Marsland - Computer Chess and Search
• TA Marsland - A Review of Game Tree Pruning
• AL Zobrist - A New Hashing Method with Application for Game Playing
• J Schaeffer - The games Computers (and People) Play

Answer 2

你符合邏輯的做法是好的，你應該閱讀，也許嘗試使用極小的算法：

http://en.wikipedia.org/wiki/Minimax

我認爲，除了從井字遊戲狀態的數量將是太大了，你應該儘快地進行計數。

Answer 3

國際象棋和跳棋可以用這種方法來實現，但它不是一個我d推薦。

如果你走這條路線，那麼我會使用某種形式的樹。如果你仔細想想，一舉一動都會減少移動之前存在的全部可能性。另外，這允許難度等級。不要總是挑選最好的，有時會選擇第二好的。

我不會走這條路的原因是它一般不好玩。人們直覺地認識到這一點，他們認爲這是不公平的。我寫了一個無與倫比的連接4遊戲，但是基於規則而不是基於遊戲棋盤狀態。它很無聊。一舉一動都得到了同樣的迴應。我認爲這也是這種方法所發生的。另外，這取決於你爲什麼這樣做。如果是爲了學習人工智能，那麼很少人工智能就是這樣完成的。如果它有一個有趣的遊戲，它通常不是。如果是因爲Deep Blue的原因，爲了擴展計算機可以執行的限制，那麼確定。

我會使用一個基於個人AI的片段，然後選擇一個最引人注目的論據，或者我會使用爬山的變體，並將一種策略的高度放入董事會。這取決於多少支持件給對方。對於個人AI我會使用神經網絡。

戰略身高系統對於FPS來說很好，因爲士兵們想知道哪條路線最有效。神經網絡給每個實體更多的個性。你甚至可以使用級聯神經網絡，其中一個是策略，第二個是個性。