問題タブ [tic-tac-toe]

三目並べの実装で難しい部分は、マシンが実行する最善の動きを決定することだと思います。

追求できるアルゴリズムは何ですか？単純なものから複雑なものまで、実装を検討しています。問題のこの部分にどのように取り組みますか?

私はJavaで三目並べのゲームを作成しました。ゲームの終了を判断する現在の方法は、ゲームが終了する可能性のある次のシナリオを考慮しています。

1. ボードはいっぱいで、勝者はまだ宣言されていません。ゲームは引き分けです。
2. クロスが勝ちました。
3. サークルが勝ちました。

残念ながら、そうするために、テーブルからこれらのシナリオの事前定義されたセットを読み取ります。ボード上にスペースが9つしかないため、テーブルがやや小さいことを考えると、これは必ずしも悪いことではありませんが、ゲームが終了したかどうかを判断するためのより良いアルゴリズムの方法はありますか？9つのスペースがいっぱいかどうかを確認するのは簡単なので、誰かが勝ったかどうかの判断が問題の核心です。

テーブルメソッドが解決策かもしれませんが、そうでない場合は何ですか？また、ボードがサイズでない場合はどうなりn=9ますか？それがはるかに大きなボード、たとえばn=16、n=25などで、連続して配置されたアイテムの数が、などになるx=4とどうなりx=5ますか？すべてに使用する一般的なアルゴリズムn = { 9, 16, 25, 36 ... }？

私は、大きな（高次元の）三目並べゲームのヒューリスティックをいくつか考えました。それらのどれが実際に一貫しているのかを確認するにはどうすればよいですか？

とにかく一貫性とはどういう意味ですか？

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

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

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

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

だから私は、誰かが勝ったり、負けたり、引き分けたりした後に、三目並べゲームをリプレイする方法をプログラムしようとしています。したがって、基本的に、リプレイを機能させようとする私の試みは機能しません。プレイヤー 1 が勝った場合、リプレイするために 1 と入力すると、プレイヤー 2 に入力を求めます。

擬似コードの概要:

私の実際のコード:

私はある点まで問題のない三目並べコードを書きました。Alpha-Beta Pruning も機能しています。コードではなくアイデアが必要な問題に遭遇しました。4手で勝つ手と8手で勝つ手はどうやって選べばいいですか？私が抱えている問題は、ミニマックス/AB 刈り込みから最適なスコアを返すブランチが 8 手で勝つ可能性があるため、4 手で勝つ可能性のある枝を刈り取ることです。

キラー ヒューリスティック、転置テーブル、反復的深化検索など、いくつかのアイデアに出くわしました。どんなアイデアでも素晴らしいでしょう

少し背景：C ++でマルチノードツリーを学習する方法として、可能なすべてのTicTacToeボードを生成し、ノードで始まるブランチがそのノードから続くことができるすべてのボードになるようにツリーに格納することにしました。ノードは、1つの動きで続くボードです。その後、そのツリーを決定木として使用してTicTacToeを再生するAIを作成するのは楽しいだろうと思いました。

TTTは、完璧なプレーヤーが負けることのない解決可能な問題であるため、AIを初めて試すのは簡単なAIのようでした。

AIを最初に実装したとき、生成時に各ノードに2つのフィールドを追加しました。Xが勝つ回数とOがそのノードの下のすべての子で勝つ回数です。最善の解決策は、各移動でAIを選択し、最も多く勝つサブツリーを下に移動することであると考えました。それから私はそれがほとんどの場合完璧に機能する一方で、私がそれを打ち負かすことができる方法を見つけたことを発見しました。これは私のコードの問題ではなく、AIにパスを選択させる方法の問題でした。

それから私は、コンピューターの最大の勝利または人間の最大の損失のどちらか多い方のツリーを選択することにしました。これにより、パフォーマンスは向上しましたが、それでも完璧ではありません。私はまだそれを打ち負かすことができました。

ですから、私には2つのアイデアがあり、どちらが優れているかについての意見を期待しています。

1）勝ち負けを最大化する代わりに、勝ちに1、引き分けに0、負けに-1の値を割り当てることができます。次に、その次のノードが損失をもたらす移動になることはできないため、最も高い値を持つツリーを選択することが最良の移動になります。ボード生成の変更は簡単ですが、同じ検索スペースとメモリ使用量を維持します。または...

2）ボードの生成中に、XまたはOのいずれかが次の手で勝つようなボードがある場合、その勝ちを妨げる子だけが生成されます。他の子ノードは考慮されず、その後、生成は通常どおり続行されます。ツリーのサイズを縮小しますが、1ムーブの勝利があるかどうかを判断するアルゴリズムを実装する必要があり、それは線形時間でしか実行できないと思います（ボードの生成が大幅に遅くなると思いますか？）

どちらが良いですか、それともさらに良い解決策がありますか？

Post your shortest code, by character count, to check if a player has won, and if so, which.

Assume you have an integer array in a variable b (board), which holds the Tic Tac Toe board, and the moves of the players where:

• 0 = nothing set
• 1 = player 1 (X)
• 2 = player 2 (O)

So, given the array b = [ 1, 2, 1, 0, 1, 2, 1, 0, 2 ] would represent the board

For that situation, your code should output 1 to indicate player 1 has won. If no-one has won you can output 0 or false.

My own (Ruby) solution will be up soon.

Edit: Sorry, forgot to mark it as community wiki. You can assume the input is well formed and does not have to be error checked.

Update: Please post your solution in the form of a function. Most people have done this already, but some haven't, which isn't entirely fair. The board is supplied to your function as the parameter. The result should be returned by the function. The function can have a name of your choosing.

私は、反復アルファ-ベータ プルーニングを使用して三目並べをプレイしようとしています。移動には 1 秒の制限がありますが、何らかの理由でうまく機能しません。

通常の alpha-beta コードを変更して、alpha または beta を返す代わりに状態 (次の動きのあるボード) を返すようにしました。

子を作成するたびに、深さを更新します。

しかし、何らかの理由で私は負け続けており、私のアルファベータは最善の動きを見ていないことがわかりました.

これが私のコードです：

外側のループ:

アルファベータ:

何かが間違っているかどうか誰かが私に教えてくれれば、大いに感謝します。評価を返す通常のアルファベータの代わりに「s」を返していることに関係があるのではないかと思いますが、エラーを見つけることができませんでした。

前もって感謝します、

レナ

C++のゲームtictactoe3Dにミニマックスアルゴリズムを適用しようとしています。良い評価関数を見つけるのに苦労しています。

評価関数を見つけるための良いリソースがどこにあるか誰かが知っていますか？

ありがとうございました。