「囲碁AIにおける革命「モンテカルロ木探索」とは何か?」に参加したのモンテカルロ木探索で、勝率が高いであろう手を調べる回数を増やす方法。

美添氏の「コンピュータ囲碁におけるモンテカルロ法」(理論編) の Multi-Armed Bandit 問題(何台もあるスロットマシンのどれにどれだけつぎ込んだら儲けが多くできるか)てやつ。どのマシンにも平均してつぎ込むのはダメな手段(原始モンテカルロ法)。UCB1 (Upper Confidence Bound) を計算して一番大きい値のマシンにコインを投入していけば儲けを大きくできるらしい。

Ruby でテストのプログラム:

#!/usr/bin/ruby
# -*- coding: utf-8 -*-

include Math

# 勝率
def win_ratio(test, win)        # 試行回数, 勝利回数
  return (test > 0) ? (1.0 * win / test) : 0
end

# UCB1 (Upper Confidence Bound) の計算
#       test:   そのマシンのテスト回数
#       win:    そのうちの勝った回数
#       total:  総試行回数
def calc_ucb1(test, win, total)
  if total == 0 # まだ1つもテストしてない
    return 0
  else
    c = 1       # 期待値の値域によって決まる定数
    if test > 0
      per = win_ratio(test, win)
      return per + c * sqrt(2 * log(total) / test)
    else
      return c * sqrt(2 * log(total) * 1000)    # てきとうにでかい値を掛けておく
    end
  end
end


class Array
  # 配列中の最大値のインデクスを返す
  def max_idx
    n = self.size
    maxi = maxv = nil
    (0...n).each do |i|
      if !maxv || maxv < self[i]
        maxi = i
        maxv = self[i]
      end
    end
    return maxi
  end
end


# それぞれの手を選んだときに勝つ確率(テスト用データ)
Tbl = [0.30, 0.31, 0.29, 0.32, 0.28]

# テスト回数
N = 1000

# プレイアウト(ランダムの手でゲームを進めて勝敗をつける)
def playout(hand)
  # ここではテストで、乱数で決定
  rand < Tbl[hand]
end


# それぞれの手の試行回数、勝利回数
test_data = Tbl.map{ [0, 0] }

# モンテカルロ木探索
N.times do |n|
  ucb1s = test_data.map{|test, win| calc_ucb1(test, win, n)}

  # UCB1 が一番大きな手を選択
  hand = ucb1s.max_idx

  # その手でプレイアウトさせて勝ったかどうかを調べる
  win = playout(hand)

  test_data[hand][0] += 1               # その手の試行回数 +1
  if win
    test_data[hand][1] += 1             # その手の勝利回数 +1
  end
  puts %!hand #{hand}: #{win ? "WIN!" : "lose"}, #{test_data[hand][1]}/#{test_data[hand][0]}!
end

# 勝率が高い順に並べる
order = (0...test_data.size).sort_by {|i| -win_ratio(test_data[i][0], test_data[i][1])}

puts "\n**** Result ****"
order.each do |i|
  test = test_data[i][0]
  win = test_data[i][1]
  printf("hand #{i}: %4d/%4d (%f)\n", win, test, 1.0 * win / test)
end

実行例:

hand 0: WIN!, 1/1
hand 0: lose, 1/2
hand 1: lose, 0/1
hand 2: WIN!, 1/1
hand 3: lose, 0/1
hand 4: lose, 0/1
hand 2: lose, 1/2

...

**** Result ****
hand 3:   74/ 235 (0.314894)
hand 4:   61/ 213 (0.286385)
hand 1:   60/ 211 (0.284360)
hand 0:   58/ 206 (0.281553)
hand 2:   30/ 135 (0.222222)

だいたい勝率が一番高くしてある3番目の手が最高の勝率になって試行回数も一番多くなる。総試行回数がたった1000回だからしばしば間違うけど。

ま、例によって論文は読んでないんですが。