大変ですが読みます。。。ほぼコピペですが。

https://www.kaggle.com/code/alexisbcook/n-step-lookahead

導入

前回のチュートリアルでは、一手先読みのエージェントを作成する方法を学びました。このエージェントはまあまあの性能を発揮しますが、まだ改善の余地があります！たとえば、以下の図に示す潜在的な動きを考えてみてください。 （注：列に対して0ベースの番号付けを使用しているため、最も左の列はcol=0、次の列はcol=1、というようになります。）

一手先読みを使用すると、赤いプレイヤーは列5または6のいずれかを選び、それぞれが50%の確率で選ばれます。しかし、列5は明らかに悪手です。なぜなら、それによって対戦相手が次のターンでゲームに勝つことを許してしまうからです。残念ながら、エージェントは将来の1手しか見ることができないため、これを知りません。

このチュートリアルでは、エージェントが将来をより深く見るのを助け、よりよく情報を得た判断を下すために、ミニマックスアルゴリズムを使用します。

ミニマックス

ゲームツリーのより深い部分からの情報を活用したいと思います。今のところ、深さ3で動作すると仮定します。この方法では、手を決めるとき、エージェントは以下の結果として生じるすべての可能なゲームボードを考慮します。

1. エージェントの動き、

2. 対戦相手の動き、そして

3. エージェントの次の動き。

視覚的な例で作業します。簡単のため、各ターンでエージェントと対戦相手の両方が2つの可能な動きしか持たないと仮定します。以下の図の青い長方形は、異なるゲームボードに対応しています。

私たちはツリーの一番下にある「葉ノード」すべてに、ヒューリスティックからのスコアを付けています。（図では架空のスコアを使用しています。コードでは、前のチュートリアルと同じヒューリスティックを使用します。）前と同様に、現在のゲームボードは図の一番上にあり、エージェントの目標はできるだけ高いスコアを得ることです。

しかし、エージェントがスコアを完全にコントロールできなくなったことに注意してください。エージェントが動きを決めた後、対戦相手が自分の動きを選ぶのです。そして、対戦相手の選択はエージェントにとって悲劇的になる可能性があります！具体的には、

- エージェントが左の枝を選ぶと、対戦相手は-1のスコアを強制できます。

- エージェントが右の枝を選ぶと、対戦相手は+10のスコアを強制できます。

今すぐこの図で確認して、これが理にかなっているか確認してください！

これを考えると、右の枝がエージェントにとってより良い選択であると言えるかもしれません。それは、リスクが少ないオプションだからです。確かに、左の枝でのみアクセスできる大きなスコア（+40）の可能性を放棄しますが、エージェントが少なくとも+10ポイントを得ることを保証します。

これがミニマックスアルゴリズムの背後にある主なアイディアです：エージェントは可能な限り高いスコアを得るための動きを選び、対戦相手はスコアを可能な限り低くする動きを選ぶことでこれに対抗すると仮定します。つまり、エージェントと対戦相手は相反する目標を持っており、対戦相手が最適にプレイすると仮定します。

実際には、エージェントはこの仮定をどのように使用して動きを選ぶのでしょうか？以下の図でエージェントの思考過程を示します。

例では、ミニマックスは左の動きに-1のスコアを割り当て、右の動きには+10のスコアを割り当てます。そのため、エージェントは右の動きを選択します。

コード

前のチュートリアルのいくつかの関数を使用します。これらは以下の隠れたコードセルに定義されています。（それらを表示したい場合は、下の「コード」ボタンをクリックしてください。）

また、対戦相手がゲームボードを変更することができるようになったため、前回のチュートリアルのヒューリスティックをわずかに修正する必要があります。

特に、対戦相手がディスクをプレイしてゲームに勝ったかどうかを確認する必要があります。新しいヒューリスティックは、(水平、垂直、または斜めの)ラインで隣接する4つの位置の各グループを見て、次のようにスコアを付けます：

- 1000000 (1e6) ポイント: エージェントが4つのディスクを連続して持っている場合（エージェントが勝利）。

- 1 ポイント: エージェントが3つの場所を埋め、残りの場所が空いている場合（エージェントが空いている場所を埋めると勝利）。

- -100 ポイント: 対戦相手が3つの場所を埋め、残りの場所が空いている場合（対戦相手が空いている場所を埋めると勝利）。

- -10000 (-1e4) ポイント: 対戦相手が4つのディスクを連続して持っている場合（対戦相手が勝利）。

これは以下のコードセルで定義されています。

# Helper function for minimax: calculates value of heuristic for grid
def get_heuristic(grid, mark, config):
num_threes = count_windows(grid, 3, mark, config)
num_fours = count_windows(grid, 4, mark, config)
num_threes_opp = count_windows(grid, 3, mark%2+1, config)
num_fours_opp = count_windows(grid, 4, mark%2+1, config)
score = num_threes - 1e2*num_threes_opp - 1e4*num_fours_opp + 1e6*num_fours
return score

次のコードセルでは、ミニマックスエージェントに必要ないくつかの追加の関数を定義します。

# Uses minimax to calculate value of dropping piece in selected column
def score_move(grid, col, mark, config, nsteps):
next_grid = drop_piece(grid, col, mark, config)
score = minimax(next_grid, nsteps-1, False, mark, config)
return score

Helper function for minimax: checks if agent or opponent has four in a row in the window

def is_terminal_window(window, config):
return window.count(1) == config.inarow or window.count(2) == config.inarow

Helper function for minimax: checks if game has ended

def is_terminal_node(grid, config):
# Check for draw
if list(grid[0, :]).count(0) == 0:
return True
# Check for win: horizontal, vertical, or diagonal
# horizontal
for row in range(config.rows):
for col in range(config.columns-(config.inarow-1)):
window = list(grid[row, col:col+config.inarow])
if is_terminal_window(window, config):
return True
# vertical
for row in range(config.rows-(config.inarow-1)):
for col in range(config.columns):
window = list(grid[row:row+config.inarow, col])
if is_terminal_window(window, config):
return True
# positive diagonal
for row in range(config.rows-(config.inarow-1)):
for col in range(config.columns-(config.inarow-1)):
window = list(grid[range(row, row+config.inarow), range(col, col+config.inarow)])
if is_terminal_window(window, config):
return True
# negative diagonal
for row in range(config.inarow-1, config.rows):
for col in range(config.columns-(config.inarow-1)):
window = list(grid[range(row, row-config.inarow, -1), range(col, col+config.inarow)])
if is_terminal_window(window, config):
return True
return False

Minimax implementation

def minimax(node, depth, maximizingPlayer, mark, config):
is_terminal = is_terminal_node(node, config)
valid_moves = [c for c in range(config.columns) if node[0][c] == 0]
if depth == 0 or is_terminal:
return get_heuristic(node, mark, config)
if maximizingPlayer:
value = -np.Inf
for col in valid_moves:
child = drop_piece(node, col, mark, config)
value = max(value, minimax(child, depth-1, False, mark, config))
return value
else:
value = np.Inf
for col in valid_moves:
child = drop_piece(node, col, mark%2+1, config)
value = min(value, minimax(child, depth-1, True, mark, config))
return value

最後に、競技フォーマットでミニマックスエージェントを実装します。N_STEPS変数は、ツリーの深さを設定するために使用されます。

# How deep to make the game tree: higher values take longer to run!
N_STEPS = 3

def agent(obs, config):
# Get list of valid moves
valid_moves = [c for c in range(config.columns) if obs.board[c] == 0]
# Convert the board to a 2D grid
grid = np.asarray(obs.board).reshape(config.rows, config.columns)
# Use the heuristic to assign a score to each possible board in the next step
scores = dict(zip(valid_moves, [score_move(grid, col, obs.mark, config, N_STEPS) for col in valid_moves]))
# Get a list of columns (moves) that maximize the heuristic
max_cols = [key for key in scores.keys() if scores[key] == max(scores.values())]
# Select at random from the maximizing columns
return random.choice(max_cols)

次のコードセルでは、ランダムエージェントとの1回のゲームラウンドの結果を見ることができます。

from kaggle_environments import make, evaluate

Create the game environment

env = make("connectx")

Two random agents play one game round

env.run([agent, "random"])

Show the game

env.render(mode="ipython")

結果を見ます。

def get_win_percentages(agent1, agent2, n_rounds=100):
# Use default Connect Four setup
config = {'rows': 6, 'columns': 7, 'inarow': 4}
# Agent 1 goes first (roughly) half the time
outcomes = evaluate("connectx", [agent1, agent2], config, [], n_rounds//2)
# Agent 2 goes first (roughly) half the time
outcomes += [[b,a] for [a,b] in evaluate("connectx", [agent2, agent1], config, [], n_rounds-n_rounds//2)]
print("Agent 1 Win Percentage:", np.round(outcomes.count([1,-1])/len(outcomes), 2))
print("Agent 2 Win Percentage:", np.round(outcomes.count([-1,1])/len(outcomes), 2))
print("Number of Invalid Plays by Agent 1:", outcomes.count([None, 0]))
print("Number of Invalid Plays by Agent 2:", outcomes.count([0, None]))

In [7]:

get_win_percentages(agent1=agent, agent2="random", n_rounds=50)
Agent 1 Win Percentage: 1.0
Agent 2 Win Percentage: 0.0
Number of Invalid Plays by Agent 1: 0
Number of Invalid Plays by Agent 2: 0