ミニマックスアルゴリズムでチックタックトー

この記事では、Tic Tac Toeソルバーの実装をminimax アルゴリズム.それは比較的少ない状態でそのような単純なゲームだから、私はチックタックトーは機械学習とAI実験のための便利なケーススタディであると思いました.ここでは、ミニマックスと呼ばれる単純なアルゴリズムを実装しました.
ミニマックスの背後にある基本的な考え方は、我々はどのように我々は相手が可能な最善の動きを再生すると仮定するときに再生する方法を知りたいです.たとえば、それがXのターンとXが特定の動きをすると言いましょう.この動きの価値は何ですか.oが2つの方法のうちの1つで応じることができると仮定してください:最初の場合では、次の動きのO勝.oによる他の動きは、以下の動きの上でXによる勝利につながります.Oが勝つことができるので、我々はXによって元の動きを悪いものと考えます-それは損失につながります.私たちは、Oが間違いをするならば、Xが勝つという事実を無視します.私たちは勝つために1のために値1を定義します、oによる勝利のための- 1、そして、抽選のための0.上記のシナリオでは、次の移動でOが勝つことができるので、Xによる元の移動には- 1の値が割り当てられる.
ミニマックスアルゴリズムは、任意の指定された位置から再帰的にこの戦略を適用します-我々はゲーム状態のすべての可能な端に到達するまで、我々は与えられた開始位置からゲームを探る.我々は、ツリーの各レベルを与えられたプレーヤーのターンの可能なボードの位置を示すとして、これを表すことができます.私たちがゲームの状態の終わりに到達すると、それがなされる選択がないので、値はゲームの結果です.それがXのターンであり、それが最終的なボード状態でないならば、我々は木のその位置からの次の可能な動きの値の最大値を選びます.これはoのための最も可能なオプションを表します、それがoのターンであるならば、我々はこれらの値の最小値を選びます.そして、それは我々にとって最高のオプションです.
以下の図は、ボード位置に適用されるミニマックスの例を示します.

位置がゲーム状態の終わりならば、その位置の値はそのゲームの結果です.一旦我々がゲーム位置の終わりに達したならば、我々はルート位置に向かって我々の方法を働かせます.ツリーの最大レベルの位置のために- Xのターンです-我々は可能な継続から最大値で移動を選択します.木のMINレベルの位置のために-それはOのターンです-私たちは最小値をとります.各ケースでは、我々は、現在のプレーヤーの次の動きのための最良の結果を探しています.私たちが見ることができるように、最高のXはダイアグラムで行うことができます(Oが間違いをしない限り)ボードの右上のコーナーで描画することによって描画を取得することです.

It's worth emphasizing that minimax works fine for a toy scenario like tic-tac-toe: There are few distinct game positions - 765 if we take rotation and reflection symmetry into account. For more complex scenarios, including games like chess and go, minimax would, at the very least, have to be combined with other techniques. I haven't implemented it here, but alpha-beta pruning can be used to reduce the number of positions that need to be visited. The overall idea is that if we know that exploring a subtree won't produce a better result than what we've already got, then we don't need to bother with it. There are additional heuristics as well. We can limit the depth of search, and once we hit that limit, we can use a heuristic to estimate the likely value of the position. This idea has been used extensively in chess engines like Stockfish. MCTS is another technique that can be applied to simplify scenarios where minimax would result in too many combinations to keep track of. These days, for games like chess and go, deep learning has proven remarkably effective. In fact, it's far more effective than any other known technique.

ミニマックスを実装するために必要なコードを簡単に見てみましょう.このコードは、基本的な概念を説明するために、最大効率のために書かれていないことに注意してください.プロジェクトは利用可能ですgithub . このコードは minimax.py ファイル

def play_minimax_move(board):
    move_value_pairs = get_move_value_pairs(board)
    move = filter_best_move(board, move_value_pairs)

    return play_move(board, move)

play_minimax_move 決定は、与えられたボードの位置の再生に移動します.最初に、それぞれの可能な動きに対応する値を取得し、それがXのターン、またはOのターンならば最小値で移動する場合は、最大値で移動を果たしている.get_move_value_pairs 現在のボード位置から次の各移動の値を取得します.

def get_move_value_pairs(board):
    valid_move_indexes = get_valid_move_indexes(board)

    assert not_empty(valid_move_indexes), "never call with an end-position"

    move_value_pairs = [(m, get_position_value(play_move(board, m)))
                        for m in valid_move_indexes]

    return move_value_pairs

get_position_value , 以下に、キャッシュから現在の位置の値を取得するか、ゲームツリーを探索することによって直接計算します.キャッシュせずに、1つのゲームをプレイ私のコンピュータ上で約1.5分かかります.キャッシュは約0.3秒にダウン!フル検索は再び何度も同じ位置に遭遇します.キャッシュは、我々がかなりこのプロセスを速めるのを許します:我々が前に位置を見たならば、我々はゲーム木のその部分を再調査する必要はありません.

def get_position_value(board):
    cached_position_value, found = get_position_value_from_cache(board)
    if found:
        return cached_position_value

    position_value = calculate_position_value(board)

    put_position_value_in_cache(board, position_value)

    return position_value

calculate_position_value 指定したボードが既にキャッシュにない場合の値を検索します.我々がゲームの終わりにいるならば、我々は位置の値としてゲーム結果を返します.さもなければ、私たちは再帰的にget_position_value を指定します.次に、これらの値の最小値または最大値を取得します.

def calculate_position_value(board):
    if is_gameover(board):
        return get_game_result(board)

    valid_move_indexes = get_valid_move_indexes(board)

    values = [get_position_value(play_move(board, m))
              for m in valid_move_indexes]

    min_or_max = choose_min_or_max_for_comparison(board)
    position_value = min_or_max(values)

    return position_value

その下で見ることができますchoose_min_or_max_for_comparison はmin 関数がoのターンであるならばmax Xのターンならば

def choose_min_or_max_for_comparison(board):
    turn = get_turn(board)
    return min if turn == CELL_O else max

キャッシュキャッシュに戻ると、キャッシュコードも同様のアカウント位置になります.これは、水平方向と垂直方向の反射だけでなく、回転が含まれます.回転時の4等分位置は0°,90°,180°,270°である.また、4つの反射:水平方向と垂直方向の元の位置を反転し、また、90度で最初に回転し、水平方向と垂直方向に反転します.残りの回転を反転する冗長されています:180度回転を反転すると、元の位置を反転すると同じ位置を生成します270°回転を反転させると90°回転を反転させるのと同じ位置になる.アカウントの回転と反射を取ることなく、1つのゲームは、私たちのコンピュータ上で約0.8秒かかります.get_symmetrical_board_orientations すべての等価ボード位置を取得します.

def get_symmetrical_board_orientations(board_2d):
    orientations = [board_2d]

    current_board_2d = board_2d
    for i in range(3):
        current_board_2d = np.rot90(current_board_2d)
        orientations.append(current_board_2d)

    orientations.append(np.flipud(board_2d))
    orientations.append(np.fliplr(board_2d))

    orientations.append(np.flipud(np.rot90(board_2d)))
    orientations.append(np.fliplr(np.rot90(board_2d)))

    return orientations

あなたがより近い観察をすることに興味があるならば、このプロジェクトのためにコードのすべてでGithub Repoは利用できます:

ソフトウェア開発 / ティクタック

チックタックつま先を再生するためのさまざまな手法で実験する

チックタックトーを再生するためのさまざまなアプローチのデモプロジェクト.
コードにはPython 3 , numpy , PyTestが必要です.
Pipenvをインストールする

pipenv shell

pipenv install --dev

設定するPYTHONPATH メインプロジェクトディレクトリへ

Windowsでは、実行path.bat

バッシュでsource path.sh

テストとデモを実行する

実行テスト:pytest

デモを実行するpython -m tictac.main

以下は、最新のデモ結果です.現在のQTableエージェント自体は、ミニマックス、およびランダムに対してOとして完璧なゲームの近くで再生します.Xプレーヤーのために良い結果を得ることはかなり簡単でした、しかし、Oのために、それは非常に少しのパラメタをいじることをとりました.
最新の結果

C:\Dev\python\tictac>python -m tictac.main
Playing random vs random
-------------------------
x wins: 60.10%
o wins: 28.90%
draw  : 11.00%
Playing minimax not random vs minimax random
---------------------------------------------
x wins: 0.00%
o wins: 0.00%
draw  : 100.00%

Playing minimax random vs minimax not random:
---------------------------------------------
x wins: 0.00%
o wins: 0.00%
draw  : 100.00%

…
View on GitHub
以下は、各組み合わせのためにプレー1000ゲームでミニマックスとランダムな選手のさまざまな組み合わせの勝利率です.

両方のプレーヤーが完全にプレーするならば、引き分けだけが可能であるとわかります、しかし、両方のプレーヤーがランダムに遊ぶならば、Xは勝ちそうです.

関連