ミニマックスアルゴリズムでチックタックトー
ミニマックスの背後にある基本的な考え方は、我々はどのように我々は相手が可能な最善の動きを再生すると仮定するときに再生する方法を知りたいです.たとえば、それが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
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
ソフトウェア開発 / ティクタック
チックタックつま先を再生するためのさまざまな手法で実験する
チックタックトーを再生するためのさまざまなアプローチのデモプロジェクト.
コードにはPython 3 , numpy , PyTestが必要です.
Pipenvをインストールする
pipenv shell pipenv install --dev PYTHONPATH メインプロジェクトディレクトリへpath.batsource path.shpytestpython -m tictac.main最新の結果
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は勝ちそうです.
関連
Reference
この問題について(ミニマックスアルゴリズムでチックタックトー), 我々は、より多くの情報をここで見つけました https://dev.to/nestedsoftware/tic-tac-toe-with-the-minimax-algorithm-5988テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol