tic-tac-toe - 4 * 4 ボードの Tic Tac Toe で Minimax を適用することは可能ですか、それとも Alpha-Beta 剪定が必要ですか?

Question

Minimax アルゴリズムのみを適用して、Java で 3 * 3 Tic Tac Toe ゲームを実装しました。しかし、ボードのサイズを 4 * 4 に変更すると、プログラムがハングするようです。この問題を解決するために、アルファ ベータ プルーニングを使用して Minimax を適用する必要があるのか​​、それとも Minimax 自体で問題ないのかを尋ねたいと思います。

Answer 1

完全な深さ検索を実行しようとしている場合は、アルファベータを使用する必要があります。素朴な4x4の探索木には16があります！または約21兆ノード。反対側は次の動きで勝つか、2プライ後に勝つことを強制する位置を作成することによって祖先の位置に反論するため、これらのノードの多くを検索する必要はありません。アルファベータでは、これらの検索スペースの一部を横断せずに切り分けることができます。