爲遊戲'接近'找到最佳/足夠好的策略和人工智能？

Question

'接近'是一個類似於黑白棋，圍棋和風險的領土統治戰略遊戲。兩個玩家，使用10x12六角形網格。遊戲發明者Brian Cable在2007年。

似乎是一個值得討論的遊戲a）優化算法然後b）如何構建AI。
由於隨機性因素和瘋狂的分支因子（20^120），策略將是概率性的或基於啓發式的。 因此，客觀地比較是很難的。 每回合最多5秒的計算時間限制似乎是合理的=>這排除了所有暴力嘗試。（玩遊戲的AI上專家的水平來感受 - 它基於一些簡單的規則十分出色）

遊戲：Flash version here，iPhone version iProximity here和許多副本在網絡上其他地方 規則：here

對象：在所有瓷磚放置完畢後控制大多數軍隊。你從一個空的木板開始。每回合你收到一個隨機編號的瓦片（值在1到20軍）放置在任何空置的電路板空間。如果此貼磚與任何ALLY貼磚相鄰，則會加強每個貼磚的防禦+1（最高可達20）。如果它與任何ENEMY牌相鄰，如果其號碼高於敵方牌上的號碼，則會控制它們。

關於策略的思考：以下是一些初步想法;設置電腦AI專家可能會教導很多：

1. 儘量減少你的周邊似乎是一個很好的策略，以防止翻轉和減少最壞情況下的損傷
2. 像圍棋，留孔內的形成是致命的，只有更多的六角網格，因爲你可以在一次移動中失去多達6個方格的軍隊
3. 低編號的瓷磚是一種責任，所以把它們放置在遠離你的主要領土，靠近電路板邊緣並散落的地方。你也可以使用低編號的瓦片來堵住你陣型的洞，或者在對手不會打擾攻擊的周界上進行小幅度增益。
4. 由於它們相互加強，並且還減少了邊界，所以三個三角形的形成是強的。每個瓦片可以翻轉至多6次，即當其鄰居瓦片被佔用時。地層的控制可以來回流動。有時候你會失去一部分陣型並堵住任何漏洞，導致該部分棋盤「死亡」並鎖定在你的領土內/防止進一步的損失。
5. 低編號的瓷磚是顯而易見但價值低的負債，但編號較高的瓷磚如果翻轉（這更難）會是更大的負債。一次20軍瓦片的幸運玩法可能導致200的揮杆（從+100到-100軍隊）。所以拼貼放置會有攻擊和防禦兩方面的考慮。

評論1,2,4似乎類似於一個極小極小戰略，我們儘量減少最大的預期可能損失（通過一些概率考慮值的修正，對手可以從1..20得到，即一個結構可以只有被ß= 20瓦翻轉纔是'幾乎堅不可摧'。） 我不清楚評論3,5,6對最佳策略的影響。 對Go，Chess or Othello玩家的評論感興趣。

（續集ProximityHD for XBox Live, allows 4-player -cooperative or -competitive local multiplayer增加分支因素，因爲你現在在你的手牌5在任何給定的時間，而你只能起到盟友瓷磚之一。加固增加到+2每盟友。）

Answer 1

對於一般算法，我建議您檢查由艾伯塔大學AI Games小組完成的研究：http://games.cs.ualberta.ca許多算法保證找到最佳策略。不過，我懷疑你是在尋找最佳的真正的興趣，瞄準了「足夠好」，除非你想出售在韓國的那場比賽：d

從你的描述，我已經明白遊戲是兩具有完全可觀測性的玩家（即沒有隱藏單位）以及完全確定性的玩家的行動結果不需要滾動，那麼你應該看看阿爾伯塔傢伙提出的實時有界搜索極小極小導數。但是，能夠限制值函數備份的深度也許是向遊戲添加「難度級別」的好方法。他們一直在做一些工作 - 有點腥意 - 抽樣搜索空間以改進價值​​函數估計。

關於「策略」部分中，您描述：在我提到的框架，你將不得不編碼知識作爲評價函數。看看MichaelBüro和其他人 - 也就是U阿爾伯塔集團 - 的工作，例如這樣的知識工程。

另一種可能性將是造成這一問題的強化學習問題，在對手的動作是編譯爲「afterstates」。你看，截至上巴託&薩頓書：http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html但是從這樣的編譯產生的RL問題的價值函數可能證明有點困難，以最佳解決 - 美國的數量將炸燬像氫彈。但是，如果您看到如何使用因式分解，事情會變得更容易。而你的「策略」也許可以編碼爲一些整形功能，這將大大加快學習過程。

編輯：該死的英語介詞

Answer 2

這裏遊戲組的U的前成員。

那分支因素是瘋了。遠比Go差。

基本上，你囉嗦。

這個遊戲的問題是，它不具有確定性，由於隨機瓷磚的選擇。這實際上增加了樹中每個現有節點層之間的另一層節點。您將對我的publications on *-Minimax感興趣，以瞭解隨機域中搜索技術。

爲了本世紀結束前完成的一層搜索，你會需要一些非常積極的向前修剪技術。儘可能的投擲最好儘早移開窗戶，專注於建立良好的移動順序。