私はある点まで問題のない三目並べコードを書きました。Alpha-Beta Pruning も機能しています。コードではなくアイデアが必要な問題に遭遇しました。4手で勝つ手と8手で勝つ手はどうやって選べばいいですか？私が抱えている問題は、ミニマックス/AB 刈り込みから最適なスコアを返すブランチが 8 手で勝つ可能性があるため、4 手で勝つ可能性のある枝を刈り取ることです。
キラー ヒューリスティック、転置テーブル、反復的深化検索など、いくつかのアイデアに出くわしました。どんなアイデアでも素晴らしいでしょう
反復深化についてもっと調べたいと思います。これは、8手で勝つ前に4手で勝つことを見つけるのに役立ちます。
取られる手数が少ないほど、ゲームの勝利状態をより高く評価する必要があります。これは非常に簡単に実装できるはずです。通常、勝利したすべてのゲーム状態に 100 の値を割り当てるとします。サイズ 9 のボードの場合、これに数量 (9 - ターン) を追加するだけです。したがって、8 ターン後の勝利ボードは 101 と評価され、5 ターン後の勝利ボードは 104 と評価されます。
あなたができる方法：
勝利が見つからない場合は、最大深度 2 で検索を行い、勝利が見つかるまで深度制限を増やします。
tic-tac-toe、killer heuristic 、transposition table の場合、すべてのボードの可能性をメモリに保持できるため、少し多すぎます。
私のプロジェクトでは、Proof-Number Searchを使用しています。しかし、使えるアルゴリズムはたくさんあります。このサイトでもアイデアを見つけることができますが、チェスに関するものであっても、ほとんどのアイデアはプロジェクトに使用できます。
tictactoe は、少なくとも初期状態から、勝敗を保証するアルゴリズムが存在するという意味で、実際に「解決」されていると考えているため、アルファベータ検索は過剰に見えます。（チェスなどよりも単純なゲームで実装することを学んでいる場合を除きます）
（これをコメントに含めたかったのですが、長くなりすぎました）
反復的な深化は、おそらくこの質問に対する最も簡単な「修正」です。アルファベータ検索をループに入れるだけで、アルファベータが進む深さを着実に増やすことができます。ループ内にいくつかのテストを含めて、ループを早期に終了させることができます (たとえば、勝利の動きが見つかりました)。
元：
while (!win_found && depth < 8)
{
alphaBetaSearch(win_found, depth);
depth++;
}
状態が複数回生成されるため、反復的な深化は無駄に思えるかもしれませんが、これはそれほどコストがかからないことがわかります。これは、各レベルの分岐因子が同じ (またはほぼ同じ) 探索木では、ほとんどのノードが最下位レベルにあるため、上位レベルが複数回生成されてもあまり問題にならないためです。
コンパイルされた言語で記述した場合、ヒューリスティックを使用せずに最初の移動からツリー全体を 1 秒未満で検索できます (-1,0,+1 を返すアルファ ベータと eval 関数のみ)。最初の動きと他の動きにははるかに少ない。