私は現在、入力がコンピューターによって自動的に生成される「ドットアンドボックス」プログラムに取り組んでおり、出力は私たちが行う動きです。私は他のプレイヤー（彼らのアルゴリズム）と競争します。
ドットアンドボックスボードをPythonでマトリックスとして表現しています。ゲームに勝つことが最優先事項です。アルゴリズムの効率はそれほど重要ではありません。
ボードを前提として、どのような動きをするべきかを自動的に判断するための、複雑ではない最良のアルゴリズムはありますか？
PS-必要に応じて、コードで何も提供する必要はありません...英語のアルゴリズムは完全に受け入れられます。
ミニマックスはドットアンドボックスのアルゴリズムの最良の選択ではないと思います。このゲームの全容については、エルウィンR.バーレカンプの「ドットとボックスゲーム：洗練された子供の遊び」という本を読む必要がありますが、ここで簡単な要約を示します。
Berlekampは多くの強力な観察を行っています。1つ目はダブルクロス戦略です。これはあなたが知っていると思います（ゲームのウィキペディアのページで説明されています）。
2つ目は、長鎖のパリティルールです。これは、よくプレイされているゲームの大部分に関する3つの事実に基づいています。
加えて、開始するドットの数とダブルクロスの数がゲームのターン数に等しいという制約があります。したがって、最初に16個のドットがあり、1つのダブルクロスがある場合、17ターンになります。（そして、ほとんどのゲームでは、これは最初のプレーヤーが勝つことを意味します。）
これにより、ゲーム中の位置の分析が大幅に簡素化されます。たとえば、16ドットと11ムーブが再生されたこの位置を考えてみます（Berlekampの本の問題3.3）。ここで最高の動きは何ですか？
さて、2つの長いチェーンがある場合、1つのダブルクロスがあり、ゲームはさらに6つの動き（16 + 1 = 11 + 6）の後に終了し、移動するプレーヤーは負けます。ただし、長いチェーンが1つしかない場合、ダブルクロスは発生せず、ゲームはさらに5回の移動（16 + 0 = 11 + 5）後に終了し、移動するプレーヤーが勝ちます。では、プレーヤーが移動して、長いチェーンが1つしかないことを確認するにはどうすればよいでしょうか。唯一の勝利の動きは2つのボックスを犠牲にします：
ミニマックスはこの動きを見つけたでしょうが、もっと多くの仕事があります。
3番目の最も強力な観察は、ドットとボックスが不偏ゲームであるということです。使用可能な動きは、プレイする順番に関係なく、プレイの過程で発生する一般的な位置（つまり、長いチェーンを含むもの）で同じです。ボックスの）それは通常のゲームでもあります：最後に移動したプレイヤーが勝ちます。これらの特性の組み合わせは、スプレイグ・グランディ理論を使用して位置を静的に分析できることを意味します。
Berlekampの本の図25を使用して、このアプローチがいかに強力であるかの例を次に示します。
この位置には33の可能な動きがあり、よくプレイされたゲームはさらに約20の動きが続くので、ミニマックスが妥当な時間で分析を完了することが可能であったとしたら驚きます。ただし、位置には長いチェーン（上半分に6つの正方形のチェーン）があるため、静的に分析できます。位置は、値がニム数である3つの部分に分割されます。
これらのニム数は、 n個の移動が残っている位置の時間O（2 n ）で動的計画法によって計算できます。とにかく、多くの一般的な小さな位置の結果をキャッシュすることをお勧めします。
ニム数は排他的論理和を使用して追加します：* 1 + * 4 + * 2 =*7。したがって、唯一の勝利の動き（nim-sumを* 0に減らす動き）は、*4を*3に変更することです（位置の合計が* 1 + * 3 + * 2 = * 0になるように）。3つの点線の赤い動きのいずれかが勝っています：
追加のために編集：この要約は実際にはそのようなアルゴリズムを構成しておらず、多くの質問に答えられていないことを私は知っています。いくつかの答えについては、バーレカンプの本を読むことができます。しかし、オープニングに関しては少しギャップがあります。チェーンカウントとスプレイグ-グランディ理論は、実際にはゲームの途中と終盤でのみ実用的です。オープニングでは、何か新しいことを試す必要があります。もし私だったら、チェーンを数えることができるところまでモンテカルロ木探索を試してみたくなるでしょう。このテクニックは囲碁のゲームに不思議に働き、ここでも生産的かもしれません。
上記のGarethの答えは素晴らしいと思いますが、ドットアンドボックスが（少なくともスケッチでは）np-hardであることが示されていることを追加するだけです（コメントを追加するという評判はありません）： arxiv。 org / pdf / cs / 0106019v2.pdf
上記のdotsandboxes.orgの戦略を取り入れようとするドットアンドボックスのJavaScriptバージョンを作成しました。利用できる最高のものではありませんが（Garethが言及しているすべての手法はまだ組み込まれていません）、グラフィックは素晴らしく、ほとんどの人間や他の実装に勝っています:)コードを自由に見て、他のリンクがいくつかあります。あなたがあなたを訓練することができるゲームの人々のバージョン。
このゲームはゼロサムゲームなので、 min-maxアルゴリズムを使用することをお勧めします。このアルゴリズムは、チェスでカスパロフを獲得するためにディープブルーによって使用されました。
ゲームの各状態を評価するヒューリスティック関数を作成し、それをmin-maxアルゴリズムの評価関数として使用します。
アルファベータ法を使用して、最小-最大を改善することもできます。
min-maxの考え方は、考えられるすべての動きを徹底的に検索し（通常、特定の深さまで、通過する必要のある状態は深さの数で指数関数的であるため）、対戦相手も彼の可能な限り最高の動きをします。
ps
ゲームに勝つことが最優先事項です。アルゴリズムの効率はそれほど重要ではありません。
それらは強く結びついています。アルゴリズムが効率的であるほど、可能な解決策をより深くチェックすることができ、勝つ可能性が高くなります。無制限の時間で、ゲームツリー全体を探索し、各ゲーム状態から勝利戦略を考え出すことができることに注意してください。ただし、ゲームツリー全体を探索することはおそらく非現実的です。