1. 序章


このチュートリアルでは、tic-tac-toeのゲームに勝つためのすべての方法を見つける方法を示します。


2. 問題文








minimaxやMonteCarlo Tree Search などの敵対的な検索アルゴリズムを使用してプレイできるゲームを扱っていますが、現在解決している問題に注意する必要があります。ゲームプレイではありません。 実際の対戦相手に対して1つのゲームに勝つ代わりに、 プレーヤーまたはプレーヤーの勝利を表す三目並べグリッドのすべての状態を検索します。 


もう1つ注意しなければならないのは、これも、従来の検索最適なソリューションとして分類できる問題ではないということです。 。 代わりに、移動の数に関係なく、すべての勝利が等しいと見なし、それらすべてを発見したいと考えています。 


3. ブルートフォースソリューション


最も簡単な方法は、三目並べのすべての状態を反復処理し、プレーヤーが勝った状態のみを返すことです。


3.1. 州


これを行うには、最初に三目並べの状態を定義する必要があります。 グリッド上でプレイし、各セルを空白にするか、またはでマークすることができるため、ゲームの状態を行列として定義できます。 例えば：


      


グリッドが存在できる状態がありますが、すべてが合法であるとは限りません。 プレイヤーと交代なので、ゲームの任意の時点でのグリッド上のsとsの数の差は最大で1になる可能性があります。たとえば、次の状態は3回の移動中に合法ではありません。 1つだけ作った。


      


3.2. 状態と一致


各状態は、いくつかの一致に対応します。 プレイヤーがセルを占有し、セルを埋める場合、その状態につながる一連の動きがあります。 たとえば、これら2つのシーケンスは同じ状態で終了します。


      




同じように終了する移動シーケンスがあります。


3.3. 勝利の州


正当なグリッド状態がプレーヤーの勝利を表すかどうかを確認するためのテストを定義しましょう。


最初に確認する必要があるのは、すべてのsで構成される行、列、または対角線が含まれているかどうかです。ただし、このテストでは、勝つすべてのグリッド状態がキャプチャされますが、かなりの数の誤った勝利を生み出します。 たとえば、次のグリッド状態は、プレーヤーのこのテストに合格します。


      


実際のゲームでは出会えませんが！ 真ん中の列がいっぱいになるとすぐにゲームが停止し、3番目のセルをマークできなかったため、1つは違法です。


したがって、プレイヤーが勝った場合、プレイヤーよりも1セル多くなります。 ただし、プレイヤーが勝った場合、常にプレイヤーと同じ数のセルがあります。 これは、最初の動きがあり、勝者が最後の動きをした後にゲームが停止するためです。


同じ理由で、奇数ターンでのみ勝つことができますが、偶数ターンでのみ勝つことができます。 満たされたセルの数が偶数で、両方が勝つ資格がある場合、その状態は違法であることがわかります。 奇数ターンで勝ったので、ゲームは3つのセルを接続する前に終了していました。


したがって、これはプレーヤーが勝ったかどうかを確認するための擬似コードです。




3.4. 擬似コード


最後に、ブルートフォースアプローチを次のように定式化します。




3.5. 複雑


アルゴリズムの空間と時間の両方の複雑さは、検索空間のサイズに依存します。 合計の状態があると計算しました。 最近のコンピュータは、それらすべてをメインメモリに簡単に保存できます。 したがって、実際に使用されているハードウェアやCPUが同時に実行している他のジョブによっては、このアルゴリズムの実行にそれほど時間がかからないと予想するのが妥当です。


そのため、この場合、ブルートフォースアプローチが正当化されます。 問題は扱いやすいので、複雑なロジックのない単純なアルゴリズムで処理できます。


4. Tic-Tac-Toeの一般化


ただし、三目並べの一般化には、より高度なアプローチが必要です。


それら、n、k-game では、グリッド上で三目並べをプレイします。 勝者は、最初にセルを水平、垂直、または斜めに接続するプレーヤーです。 グリッドは状態を持つことができます。 たとえば、ボードには状態があります。 したがって、との値が小さい場合でも、ブルートフォースソリューションを効率化するには状態が多すぎます。


三目並べについても同様のことが当てはまり、通常はセルの立方体で再生されます。


これらの形式の三目並べですべての勝ち状態を見つけるには、より効率的な制約充足手法を使用する必要があります。 勝利状態が満たすグリッドセルに制約を定義してから、セルごとに状態を構築します。 状態が違法であることに気付いた場合、またはプレーヤーが勝てないと推測した場合は、前に空白のままにした、またはまたはで埋めたセルの1つの割り当てをバックトラックして変更します。 勝ちの状態が見つかったら、それを記録してバックトラックし、検索を続行します。


5. 結論


この記事では、勝利を表すすべての三目並べグリッドを見つける方法を示しました。単純なブルートフォースアルゴリズムで標準ゲームを処理するのに十分であることが証明されましたが、三目並べの一般化-三目並べおよびより大きなグリッドには、より効率的なアプローチが必要です。