algorithm - 非常に大規模な三目並べゲームを解くには、どのアルゴリズムを使用しますか?

Question

小さな (3x3、4x4) 三目並べは、すべてのケースを考慮することで簡単に解決できます。しかし、たとえば、30x30 の三目並べがあります。その場合、次善の策を決定するためにどのアルゴリズムを使用しますか?

Minimax + alpha-beta pruningは、私が知っている 1 つの方法です。

より効率的/より効率的ではないがよりクールな他の方法はありますか?

あまり面白いゲームではないことはわかっています。30x30 と言ったのは、何をしたいのか、つまり、完璧な解決策を検討するケースの数が非常に多く、実現不可能なこの種のゲームでどのアルゴリズムが最もうまく機能するかを尋ねるためです。

score 7 · Accepted Answer

これはおそらく非常に実り多い問題ではないと思います。理由は次のとおりです。

勝つために必要な連続マークの数が多い場合、自分で勝利を達成するよりも勝利の可能性を防ぐ方がはるかに簡単であるため、ゲームは妥当なレベルのスキルで引き分けられます (私には思えます)。たとえば、30x30 のボードで勝つために 20 列が必要な場合、勝利を防ぐために必要なのは、ボードのほぼ中央付近の各行と列のマークと、それぞれの中央付近のマークだけです。対角線が長い。
勝つために必要なマークの数が少ない場合、ボード上の余分なスペースは戦略に大きな違いをもたらさないと思います.2番目のプレーヤーが防御するための唯一の賢明な戦略は、対戦相手の近くでプレーする。結果として、ある種のアルファ-ベータ方式で問題ありません。

score 4 · Accepted Answer

囲碁の場合、30x30 tic-tac-toe を悩ませているのと同じ理由でコンピューターには難しいです (30x30 tic-tac-toe が囲碁と同じくらい難しいと言っているわけではありません。適用しないでください)、モンテカルロ木検索は最近良い結果をもたらしました。

score 3 · Accepted Answer

五目並べや五目並べを見てみましょう。Web には多くの一般的な戦略があります。ウィキペディアの記事には、gomoku を使用した脅威ベースの検索に関する優れた論文もあります。

score 1 · Accepted Answer

ルールは、どのツリー検索アルゴリズムよりも高速であり、それらと組み合わせることができます。自分でルールを作成するか、（たとえば）遺伝的アルゴリズムを使用できます

score 0 · Accepted Answer

Alpha Beta は、使用できる最高のものです。Alpha ベータで重要なのは、その評価機能にあります。1/0/-1 (勝った/なかった/負けた) (1 人のプレイヤーの観点から) だけでなく、位置の質も返します。

この記事をチェックしてください (彼は三目並べを使用していますが、ゲームの例として主にチェスを使用しています) http://www.fierz.ch/strategy1.htm

score 0 · Accepted Answer

最後の手の隣のスペースを検索し、隣接する対戦相手の駒と並んで空いているスペースにブロックを置こうとする貪欲なアルゴリズムを使用してもよいのではないでしょうか? プレイヤーが勝てない限り、あなたは勝つことができます。

score -1 · Accepted Answer

最初のトークンを行 3 の列 3 に置きます。相手が自分のトークンを行 3 に置いた場合、次のトークンを行 2 の列 3 に置き、そうでなければ行 3 の列 2 に置きます。）動く。

対戦相手が開始した場合は、空の 4x4 ブロックを選択し、上記のように中央から開始します。対戦相手があなたの前にトリプルを完了した場合、あなたは負けます。

これは 4x4 以上のボードに最適な戦略です。

7 に答える 7