大変ですが読みます。。。ほぼコピペですが。 <a href="https://www.kaggle.com/code/alexisbcook/n-step-lookahead" rel="noopener noreferrer" target="_blank">https://www.kaggle.com/code/alexisbcook/n-step-lookahead</a> 導入前回のチュートリアルでは、一手先読みのエージェントを作成する方法を学びました。このエージェントはまあまあの性能を発揮しますが、まだ改善の余地があります！たとえば、以下の図に示す潜在的な動きを考えてみてください。 （注：列に対して0ベースの番号付けを使用しているため、最も左の列はcol=0、次の列はcol=1、というようになります。） <img src="https://assets.blueqat.com/public/uploads/us-east-2:4805ff4b-c3cc-4344-b165-86544c34d0bf/2023/10/12/n1.png"/> 一手先読みを使用すると、赤いプレイヤーは列5または6のいずれかを選び、それぞれが50%の確率で選ばれます。しかし、列5は明らかに悪手です。なぜなら、それによって対戦相手が次のターンでゲームに勝つことを許してしまうからです。残念ながら、エージェントは将来の1手しか見ることができないため、これを知りません。 このチュートリアルでは、エージェントが将来をより深く見るのを助け、よりよく情報を得た判断を下すために、ミニマックスアルゴリズムを使用します。 ミニマックスゲームツリーのより深い部分からの情報を活用したいと思います。今のところ、深さ3で動作すると仮定します。この方法では、手を決めるとき、エージェントは以下の結果として生じるすべての可能なゲームボードを考慮します。 1. エージェントの動き、2. 対戦相手の動き、そして3. エージェントの次の動き。 視覚的な例で作業します。簡単のため、各ターンでエージェントと対戦相手の両方が2つの可能な動きしか持たないと仮定します。以下の図の青い長方形は、異なるゲームボードに対応しています。 <img src="https://assets.blueqat.com/public/uploads/us-east-2:4805ff4b-c3cc-4344-b165-86544c34d0bf/2023/10/12/n2.png"/> 私たちはツリーの一番下にある「葉ノード」すべてに、ヒューリスティックからのスコアを付けています。（図では架空のスコアを使用しています。コードでは、前のチュートリアルと同じヒューリスティックを使用します。）前と同様に、現在のゲームボードは図の一番上にあり、エージェントの目標はできるだけ高いスコアを得ることです。 しかし、エージェントがスコアを完全にコントロールできなくなったことに注意してください。エージェントが動きを決めた後、対戦相手が自分の動きを選ぶのです。そして、対戦相手の選択はエージェントにとって悲劇的になる可能性があります！具体的には、 - エージェントが左の枝を選ぶと、対戦相手は-1のスコアを強制できます。- エージェントが右の枝を選ぶと、対戦相手は+10のスコアを強制できます。今すぐこの図で確認して、これが理にかなっているか確認してください！ これを考えると、右の枝がエージェントにとってより良い選択であると言えるかもしれません。それは、リスクが少ないオプションだからです。確かに、左の枝でのみアクセスできる大きなスコア（+40）の可能性を放棄しますが、エージェントが少なくとも+10ポイントを得ることを保証します。 これがミニマックスアルゴリズムの背後にある主なアイディアです：エージェントは可能な限り高いスコアを得るための動きを選び、対戦相手はスコアを可能な限り低くする動きを選ぶことでこれに対抗すると仮定します。つまり、エージェントと対戦相手は相反する目標を持っており、対戦相手が最適にプレイすると仮定します。 実際には、エージェントはこの仮定をどのように使用して動きを選ぶのでしょうか？以下の図でエージェントの思考過程を示します。 <img src="https://assets.blueqat.com/public/uploads/us-east-2:4805ff4b-c3cc-4344-b165-86544c34d0bf/2023/10/12/n3.png"/> 例では、ミニマックスは左の動きに-1のスコアを割り当て、右の動きには+10のスコアを割り当てます。そのため、エージェントは右の動きを選択します。 コード前のチュートリアルのいくつかの関数を使用します。これらは以下の隠れたコードセルに定義されています。（それらを表示したい場合は、下の「コード」ボタンをクリックしてください。） また、対戦相手がゲームボードを変更することができるようになったため、前回のチュートリアルのヒューリスティックをわずかに修正する必要があります。 <img src="https://assets.blueqat.com/public/uploads/us-east-2:4805ff4b-c3cc-4344-b165-86544c34d0bf/2023/10/12/n4.png"/> 特に、対戦相手がディスクをプレイしてゲームに勝ったかどうかを確認する必要があります。新しいヒューリスティックは、(水平、垂直、または斜めの)ラインで隣接する4つの位置の各グループを見て、次のようにスコアを付けます： - 1000000 (1e6) ポイント: エージェントが4つのディスクを連続して持っている場合（エージェントが勝利）。- 1 ポイント: エージェントが3つの場所を埋め、残りの場所が空いている場合（エージェントが空いている場所を埋めると勝利）。- -100 ポイント: 対戦相手が3つの場所を埋め、残りの場所が空いている場合（対戦相手が空いている場所を埋めると勝利）。- -10000 (-1e4) ポイント: 対戦相手が4つのディスクを連続して持っている場合（対戦相手が勝利）。これは以下のコードセルで定義されています。 <pre class="ql-syntax" spellcheck="false"># 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
</pre> 次のコードセルでは、ミニマックスエージェントに必要ないくつかの追加の関数を定義します。 <pre class="ql-syntax" spellcheck="false"># 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
</pre> 最後に、競技フォーマットでミニマックスエージェントを実装します。N_STEPS変数は、ツリーの深さを設定するために使用されます。 <pre class="ql-syntax" spellcheck="false"># 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)
</pre> 次のコードセルでは、ランダムエージェントとの1回のゲームラウンドの結果を見ることができます。 <pre class="ql-syntax" spellcheck="false">from kaggle_environments import make, evaluate

# Create the game environment
env = make(&#34;connectx&#34;)

# Two random agents play one game round
env.run([agent, &#34;random&#34;])

# Show the game
env.render(mode=&#34;ipython&#34;)
</pre> 結果を見ます。 <pre class="ql-syntax" spellcheck="false">def get_win_percentages(agent1, agent2, n_rounds=100):
 # Use default Connect Four setup
 config = {&#39;rows&#39;: 6, &#39;columns&#39;: 7, &#39;inarow&#39;: 4}
 # Agent 1 goes first (roughly) half the time 
 outcomes = evaluate(&#34;connectx&#34;, [agent1, agent2], config, [], n_rounds//2)
 # Agent 2 goes first (roughly) half the time 
 outcomes += [[b,a] for [a,b] in evaluate(&#34;connectx&#34;, [agent2, agent1], config, [], n_rounds-n_rounds//2)]
 print(&#34;Agent 1 Win Percentage:&#34;, np.round(outcomes.count([1,-1])/len(outcomes), 2))
 print(&#34;Agent 2 Win Percentage:&#34;, np.round(outcomes.count([-1,1])/len(outcomes), 2))
 print(&#34;Number of Invalid Plays by Agent 1:&#34;, outcomes.count([None, 0]))
 print(&#34;Number of Invalid Plays by Agent 2:&#34;, outcomes.count([0, None]))
</pre>In [7]: <pre class="ql-syntax" spellcheck="false">get_win_percentages(agent1=agent, agent2=&#34;random&#34;, 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
</pre>

Kaggleのイントロを見る、、、強化学習、、、N手先を読む。。。

Yuichiro Minato