私は tictactoe プログラムを書いていますが、それはあなたの伝統的な tictactoe ではありません
まず、ボードは 4x4 で、勝つ方法は、同じ種類のカードを 3 つと、対戦相手を 1 行、1 列、または斜めに並べることです。したがって、次の例では、最初の列で「O」が勝利します。
O|_|X|_
O|X|_|_
O| |_|_
X|_|_|_
プログラムに打ち負かすことができない「ハード」モードを与えるために、ミニマックスアルゴリズムを実装しようとしています。
私の問題は、考えられるすべてのゲーム状態を含むツリーを作成することは期待できないため、生成できるゲーム状態を評価する何らかの関数を考え出す必要があることです。
私の質問だと思いますが、どうすればそのような機能を思い付くことができますか?
このゲームは、ブルートフォースに対して十分に小さいことは間違いありません。
すべての状態を列挙することができます。16個の正方形があり、各正方形に3つの可能な値（X、O、または空）があります。
3 ^ 16 = 43046721、約4,300万。
これは、各状態の勝ちやすさを説明する1バイトのテーブルが43メガバイトしかないことを意味します。
各状態を100万から4300万の間のインデックスにマッピングする関数を作成します（必要なのは状態のみで、プレイの順序は必要ありません）。基本的には、ベース3の数値として表し、状態を作成できるようにします。インデックスから。
各州がとることができる4つの勝ちやすさの値を選んでください-Oで勝ち、Xで勝ち、勝てない、そして不明です。
長さ43046721のバッファーを割り当てて、各ゲーム状態の勝ちやすさを保存します。
すべてのインデックス番号を繰り返し、勝った状態をマークします。次に、残りの各州の勝率がわかっている場合は、それを繰り返し記入します（誰が順番になっているかに基づいて、すべての継承国を確認します）。これには、インデックスのセットに対して最大16回の反復が必要になるため、ブルートフォースがここで機能しない理由はわかりません。
対称性を利用したり、n個下のすべての状態がn + 1個の状態に引き継がれるという事実を利用したりするなどの最適化がありますが、最初はそれらは必要ないと思います。
ゲームのヒューリスティック関数は、ゲームの特定の状態を評価する関数です。ここでは、状態は基本的に 2 つの部分で構成されています。 (1) ボード自体。(2) 誰の番ですか。
可能なヒューリスティック関数:
もっとヒューリスティックを考えることができると思います。
次のように、さまざまなヒューリスティックを 1 つの「大きな」ヒューリスティック関数に組み合わせることができます。
a_1 * h_1(state) + a_2 * h_2(state) + ... + a_n * h_n(state)
注意が必要な部分は、a_1、...、a_n のスコアを学習することです。これはさまざまな方法で実行できます。そのうちの 1 つはモンテカルロ学習です。基本的には、さまざまな値を持つさまざまなエージェントを作成し、それらa_1,..,a_nの間でトーナメントを実行することを意味します。トーナメントが終了したら、勝者に応じて重みを調整し、時間があるうちにプロセスを繰り返します (これはいつでもアルゴリズムです)。
完了したら、学習した重みを最終エージェントに使用します。
PS 可能ゲーム数は～16！(選択された正方形の順序を決定する必要があります - それはゲームの残りの部分がどのように終了するかを選択します) - それがあなたの制約内で開発するのに十分「小さい」かどうかを自問してください - それとも大きすぎてヒューリスティックな解決策が実際に必要ですか? .