我目前正在研究一個「dots and boxes」程序，其中輸入是由計算機自動生成的，我們的輸出是我們將要做的動作。我將與另一名球員（他們的算法）競爭。圓點和盒子求解算法
我在Python中將點和盒子板表示爲矩陣。贏得比賽是首要任務：算法效率並不那麼重要。
是否有一個最好的，並不複雜的算法來自動計算出我們應該制定什麼樣的舉措？
P.S. - 如果你想要的話，你不需要在代碼中給我任何東西......英語算法是完全可以接受的。
這場比賽是zero sum game，所以我建議使用min-max algorithm它。這個算法被deep-blue用於在國際象棋中贏得卡斯帕羅夫。
創建啓發函數，它評估遊戲的每個狀態，並將其用作min-max算法的評估函數。
您還可以使用alpha-beta prunning提高最小最大值。
最小 - 最大的想法是窮舉搜索所有可能的行動 [達到一定的深度，通常，由於美國需要走過去是深度的數量指數]，並選擇最好的移動，假設你的反對者也將盡其最大可能的舉措。
p.s.
贏得比賽是重中之重：算法效率不是 重要。
它們牢固地連接在一起，因爲您的算法效率更高，您將能夠檢查可能的解決方案，以達到更好的深度，以及獲得更好的機會。請注意，在無限的時間內，您可以瀏覽整個遊戲樹並從每個遊戲狀態中制定一個獲勝策略。然而 - 探索整個遊戲樹可能是不現實的。
我認爲minimax不是dot-and-boxes算法的最佳選擇。關於這個遊戲的完整故事，你真的需要閱讀The Dots and Boxes Game: Sophisticated Child's Play by Elwyn R. Berlekamp這本書，但我會在這裏給你一個簡短的總結。
Berlekamp進行了許多有力的觀察。首先是雙交叉策略，我假設您瞭解它（在Wikipedia page on the game中對此進行了描述）。
第二個是長鏈的平價規則。這從關於大多數玩法良好的遊戲的三個事實得出：
加上約束條件，即您開始的點數加上雙十字的數量等於遊戲中的轉數。所以如果有16個點開始，並且有一個雙十字，那麼將會有17個圈。 （在大多數遊戲中，這意味着第一名玩家將獲勝。）
這極大地簡化了對遊戲中游位置的分析。例如，考慮這個位置有16個點和11個動作（Berlekamp的書中的問題3.3）。這裏最好的舉措是什麼？
好了，如果有兩個長鏈的，將會有一個雙交叉，遊戲將陸續6個移動（16 + 1 = 11 + 6）結束，玩家移動就會失去。但是如果只有一條長鏈，則不會出現雙交叉，並且在另外五次移動（16 + 0 = 11 + 5）後遊戲結束，並且移動的玩家將獲勝。那麼玩家如何確保只有一條長鏈？唯一獲勝的舉動犧牲了兩箱：
極小會發現這一招，但有更多的工作。
第三個也是最有力的觀察是點和盒子是impartial game：可用的移動是相同的，不管輪到誰玩，並且在遊戲過程中出現的典型位置（即，包含長鏈的盒子），這也是一個normal game：最後一個移動的球員獲勝。這些屬性的組合意味着可以使用Sprague–Grundy theory靜態分析位置。
下面是使用Berlekamp書中的圖25來說明這種方法有多強大的一個例子。
有在這個位置可能33個移動，和一間玩的遊戲持續約20個動作，所以我會感到驚訝，如果它是可行的極大極小到一個合理的完成其分析時間。但該位置有一個長鏈（上半部分爲六個方格的鏈），因此可以靜態分析。位置分成三塊其值nimbers：
這些nimbers可以通過動態編程時間爲O（2 Ñ）來計算用於位置與Ñ移動剩餘，並無論如何，你可能都想緩存許多常見小職位的結果。
Nimbers添加使用獨家或：* 1 + * 4 + * 2 = * 7。所以唯一的獲勝舉動（將nim-sum減至* 0的舉動）是將* 4改爲* 3（以使位置總和爲* 1 + * 3 + * 2 = * 0）。任何三個紅色虛線移動是贏：
編輯補充：我知道，內容並不真正構成算法因爲如此，並留下許多問題無人接聽。對於一些答案，您可以閱讀Berlekamp的書。但是在開幕式上存在一些差距：連鎖計數和斯普拉格 - 格倫迪理論在中期和末期實際上只是實用的。對於開幕式，你需要嘗試一些新的東西：如果是我，我會試着嘗試Monte Carlo tree search，直到鏈條可以被計數。這種技術爲Go的遊戲創造了奇蹟，並且在這裏也可能是有生產力的。
我認爲Gareth的上面的答案很好，但只是添加（我沒有任何聲譽來添加評論），點和盒已經顯示（至少有一個草圖）是np-hard根據這個：arxiv.org/pdf/cs/0106019v2.pdf
我寫了一個javascript版本的點和盒子，試圖合併上面提到的策略dotsandboxes.org。它不是最好的（不包括Gareth提到的所有技術），但圖形很好，它擊敗了大多數人類和其他實現:)請隨時查看代碼，並且還有其他一些鏈接指向其他人們可以訓練你的遊戲版本。
這是一個很好的建議，但對我的項目來說似乎太複雜了。 – 2012-04-07 19:06:23
@CaseyPatton：那麼你會以100％的概率輸掉一個這樣做的程序，除非這個遊戲有一個已知的啓發式方法來完美地規定最佳的遊戲。即使是蠻力搜索也意味着這樣做。 – ninjagecko 2012-04-07 19:07:23
@CaseyPatton：這實際上是所有零和遊戲中最好和最常用的算法。 **代理人現在的日子之間的區別是使用的啓發式，而不是使用或不使用**。另外，我相信你可以在Python上在線找到它的現有實現，並且實現min-max算法並不難。 – amit 2012-04-07 19:09:12