いものやま。

雑多な知識の寄せ集め

変種オセロの思考ルーチンを作ってみた。(その4)

昨日はミニマックス法を実装したけど、処理が遅いという問題が。

そこで、今日はパフォーマンスの改善を行っていく。

プロファイル

パフォーマンスの改善を考えるときに、まず最初にやらないといけないことが、プロファイル。
ボトルネックを勘違いして修正処理を行っても、全然効果が出ないから。

Rubyの場合、標準添付ライブラリの1つであるprofileを使うことで、プロファイルを簡単に行うことが出来る。

使い方は簡単。

$ ruby -r profile (プロファイルしたいRubyスクリプト)

こうすると、標準エラー出力に各メソッドの実行時間に関する統計結果が出力される。

例えば、貪欲AIの実行をプロファイルしてみると、次のような感じ。

$ ruby -r profile greedy_com.rb 1> /dev/null
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 26.47    51.95     51.95  2191201     0.02     0.03  YWF::Board#color
 20.97    93.12     41.17   895402     0.05     0.08  YWF::Board#traverse_to
  7.41   107.66     14.54  2979875     0.00     0.01  BasicObject#!=
  6.52   120.45     12.79  1328418     0.01     0.12  YWF::Board#count
  6.00   132.22     11.77  9759514     0.00     0.00  Array#[]
  4.90   141.83      9.61  8764806     0.00     0.00  Fixnum#<
  4.75   151.15      9.32   270050     0.03     1.37  Range#each
  3.86   158.73      7.58  1392098     0.01     0.06  YWF::Board#has_color_from_to?
  2.83   164.28      5.55   651540     0.01     0.16  YWF::Board#playable?
  2.67   169.53      5.25  4868360     0.00     0.00  Fixnum#==
  2.60   174.64      5.11   997637     0.01     0.15  YWF::Board#has_color_from?
  2.11   178.79      4.15   347256     0.01     0.12  YWF::Board#copy
  2.03   182.77      3.98  3198591     0.00     0.00  Fixnum#+
  2.00   186.69      3.92   730639     0.01     0.44  YWF::Board#playable_places
  1.80   190.23      3.54   144914     0.02     1.80  Array#each
  1.42   193.02      2.79   527489     0.01     0.01  Proc#call
  0.26   193.54      0.52    57039     0.01     0.23  YWF::Board#put_piece
  0.25   194.04      0.50    31846     0.02     0.21  YWF::Board#changeable?
  0.19   194.42      0.38   327849     0.00     0.00  Array#[]=
  0.15   194.71      0.29    16684     0.02     0.02  YWF::BoardViewer#mark
  0.13   194.97      0.26    32919     0.01     0.48  YWF::Board#changeable_places
  0.11   195.18      0.21    18291     0.01     0.21  YWF::BoardViewer#view
  0.07   195.32      0.14     7396     0.02    17.82  YWF::Board#game_end?
  0.06   195.44      0.12    18090     0.01     0.01  Kernel#print
  0.05   195.54      0.10     7195     0.01    17.79  YWF::Board#win?
  0.05   195.64      0.10     3796     0.03    95.93  YWF::GreedyCom#select
  0.04   195.71      0.07     2605     0.03     6.58  YWF::Board#change
  0.04   195.78      0.07    26938     0.00     0.00  IO#write
  0.04   195.85      0.07     7830     0.01    13.94  YWF::Board#must_pass?
  0.03   195.91      0.06     3817     0.02     3.92  YWF::Board#initialize
  0.03   195.96      0.05     4424     0.01     0.01  IO#puts
  0.03   196.01      0.05     2605     0.02     0.02  YWF::Board#change_token
  0.03   196.06      0.05     3816     0.01     0.02  YWF::Board#change_turn
  0.02   196.10      0.04     4424     0.01     0.02  Kernel#puts
  0.02   196.14      0.04     3597     0.01    43.18  YWF::GreedyCom#calculate_board_value
  0.02   196.17      0.03     4245     0.01     0.01  YWF::Board#opponent
  0.02   196.20      0.03     3796     0.01     2.29  YWF::Board#legal_actions
  0.02   196.23      0.03    42422     0.00     0.00  Fixnum#===
  0.01   196.25      0.02    54032     0.00     0.00  Array#push
  0.01   196.27      0.02     8060     0.00     0.00  Array#size
  0.01   196.29      0.02     1191     0.02     5.57  YWF::Board#play
  0.00   196.29      0.00        1     0.00     0.00  TracePoint#enable
  0.00   196.29      0.00      201     0.00     0.00  Kernel#sprintf
  0.00   196.29      0.00        1     0.00     0.00  YWF::Game#initialize
  0.00   196.29      0.00     4019     0.00     3.72  Class#new
  0.00   196.29      0.00        2     0.00     0.00  YWF::GreedyCom#initialize
  0.00   196.29      0.00     1811     0.00     0.00  Fixnum#to_s
  0.00   196.29      0.00        1     0.00     0.00  #<Object:0x007fc6f90de478>.include
  0.00   196.29      0.00        1     0.00     0.00  Module#included
  0.00   196.29      0.00        1     0.00     0.00  Module#append_features
  0.00   196.29      0.00        3     0.00     0.00  Kernel#require_relative
  0.00   196.29      0.00        2     0.00     0.00  String#==
  0.00   196.29      0.00      199     0.00     0.00  Array#initialize
  0.00   196.29      0.00        1     0.00     0.00  Module#module_function
  0.00   196.29      0.00     4245     0.00     0.00  Fixnum#%
  0.00   196.29      0.00        2     0.00     0.00  BasicObject#singleton_method_added
  0.00   196.29      0.00        2     0.00     0.00  Module#private
  0.00   196.29      0.00        1     0.00     0.00  Module#protected
  0.00   196.29      0.00     3816     0.00     0.00  Kernel#class
  0.00   196.29      0.00        1     0.00     0.00  Module#attr_reader
  0.00   196.29      0.00       33     0.00     0.00  Module#method_added
  0.00   196.29      0.00        1     0.00     0.00  TracePoint#disable
  0.00   196.29      0.00        6     0.00     0.00  IO#set_encoding
  0.00   196.29      0.00     3816     0.00     0.00  YWF::Board#add_move
  0.00   196.29      0.00        1     0.00     0.00  MonitorMixin#mon_exit
  0.00   196.29      0.00        1     0.00     0.00  Mutex#unlock
  0.00   196.29      0.00     3596     0.00     0.00  Fixnum#-
  0.00   196.29      0.00        1     0.00     0.00  MonitorMixin#mon_check_owner
  0.00   196.29      0.00     3598     0.00     0.00  Fixnum#>
  0.00   196.29      0.00        1     0.00     0.00  MonitorMixin#mon_enter
  0.00   196.29      0.00        1     0.00     0.00  Mutex#lock
  0.00   196.29      0.00        3     0.00     0.00  Thread.current
  0.00   196.29      0.00      199     0.00     0.00  Symbol#to_s
  0.00   196.29      0.00      398     0.00     0.00  Fixnum#inspect
  0.00   196.29      0.00      199     0.00     0.00  Array#to_s
  0.00   196.29      0.00      199     0.00     0.00  Array#flatten
  0.00   196.29      0.00      202     0.00  1943.27  YWF::Game#start
  0.00   196.29      0.00       20     0.00    10.00  YWF::Board#pass
  0.00   196.29      0.00        3     0.00     0.00  Class#inherited
 -0.00   196.29     -0.00        1    -0.00 196250.00  Kernel#loop
  0.00   196.29      0.00        1     0.00 196290.00  #toplevel

メソッドが呼び出されてから返るまでの時間を「全体時間」、全体時間のうち、そのメソッド自身が処理を行ってた時間を「正味時間」と呼ぶことにしたとき、各列は左から順に

  • 正味時間の合計のプログラム実行全体に対する割合(%)
  • 全体時間の合計(秒)
  • 正味時間の合計(秒)
  • 呼び出された回数
  • 呼び出し1回あたりの正味時間の平均(ミリ秒)
  • 呼び出し1回あたりの全体時間の平均(ミリ秒)
  • メソッド

を表している。

例えば、YWF::Board#traverse_toメソッド(上から2つ目)は、1回の呼び出しで正味時間として平均0.05ミリ秒、全体時間として平均0.08ミリ秒かかっていて、それが895,402回呼び出されていて、結果として、正味時間の合計は41.17秒、全体時間の合計は93.12秒となっていて、プログラム全体の20.97%の時間を使っている、となっている。

時間がかかっている処理で、自分が書いた部分の上位を見ていくと、

  • YWF::Board#color
  • YWF::Board#traverse_to
  • YWF::Board#count
  • YWF::Board#has_color_from_to?
  • YWF::Board#playable?

という感じ。
なので、このあたりをいかに改善していくかがポイントとなる。

ここで、時間がかかっている原因を分けて考える必要がある。

  • 1回の処理は軽いけれど、たくさん呼ばれているので、合計として時間がかかっている
  • たくさん呼ばれているわけじゃないけど、1回の処理が重いので、合計として時間がかかっている
  • その両方(処理も重いし、呼ばれる回数も多い)

たくさん呼ばれるので時間がかかるというのであれば、それを呼び出してる側で出来るだけ呼び出す回数を少なくする必要があるし、1回の処理が重いというのであれば、その処理自体を軽くする必要がある。

上位に挙がっているメソッドをみてみると、それ自体の処理時間はそれほど多くかかってない。
しかし、とにかく呼び出される回数が多いので、そのせいで全体として時間がかかってしまっている感じだ。
なので、いかにこれらのメソッドを呼び出さなくて済むようにするのかが、パフォーマンス改善の肝となる。

キャッシュ

こういったときに有効なのが、キャッシュだ。
メソッドの実行結果をメモリに保存しておくことで、2回目以降はそのメソッドを呼び出さずに、キャッシュに残っている結果だけを見ればよくなる。

キャッシュを使う場合、一つ気をつけなければいけないのは、キャッシュが無効になる場合があるということ。
メソッドの呼び出しがオブジェクトの状態に依存している場合、オブジェクトの状態が変わってしまうと、そのキャッシュはもはや有効とは限らなくなる。

しかし、今回の場合、ボードの状態は不変なので、そういったことを気にする必要はない。
これは、石を置くときに、オブジェクトの状態を変えてしまうのではなく、新たにオブジェクトを作るようにしたことのメリットでもある。

さて、あとはどのデータをキャッシュしておくのかの問題で、playable?→has_color_from_to?→traverse_toと呼び出しがされていくわけだから、playable?やchangeable?の結果をキャッシュしておくのがまずよさそうだ。
さらに、playable?やchangeable?を呼び出すplayable_placesやchangeable_placesの結果もキャッシュしてしまってもいいかもしれない。
それと、countからは各マスごとにcolorが呼び出されるので、countの結果もキャッシュしておくとよさそうだ。

そこで、次のような修正を加える。

     def initialize(other=nil)
       @board = [
         # 省略
       ]
       @move = 1
       @turn = BLACK
       @token = GRAY
       if other
         copy(other)
       end
+
+      # cache (lazy)
+      @count = Array.new(4)
+      @legal_check_cache = Array.new(ROW_MAX*COL_MAX)
+      @playable_places_cache = nil
+      @changeable_places_cache = nil
     end
 
     # 省略

     def count(color)
       if (color != EMPTY) && (color != BLACK) && (color != GRAY) && (color != WHITE)
         raise "invalid color. [color: #{color}]"
       end
 
-      count = 0
-      (ROW_MIN..ROW_MAX).each do |row|
-        (COL_MIN..COL_MAX).each do |col|
-          if self.color(row, col) == color
-            count += 1
+      if @count[color].nil?
+        count = 0
+        (ROW_MIN..ROW_MAX).each do |row|
+          (COL_MIN..COL_MAX).each do |col|
+            if self.color(row, col) == color
+              count += 1
+            end
           end
         end
+        @count[color] = count
       end
 
-      count
+      @count[color]
     end
 
     def playable?(row, col)
       if self.color(row, col) != EMPTY
         return false
       end
 
-      has_color_from?(row, col)
+      index = (row - 1) * COL_MAX + (col - 1)
+      if @legal_check_cache[index].nil?
+        @legal_check_cache[index] = has_color_from?(row, col)
+      end
+      @legal_check_cache[index]
     end
 
     def changeable?(row, col)
       if self.color(row, col) != GRAY
         return false
       end
 
-      if (@token != GRAY) && (@token != @turn)
-        return false
+      index = (row - 1) * COL_MAX + (col - 1)
+      if @legal_check_cache[index].nil?
+        if (@token != GRAY) && (@token != @turn)
+          @legal_check_cache[index] = false
+        else
+          @legal_check_cache[index] = has_color_from?(row, col)
+        end
       end
-
-      has_color_from?(row, col)
+      @legal_check_cache[index]
     end
 
     # 省略
 
     def playable_places
-      places = []
-      (ROW_MIN..ROW_MAX).each do |row|
-        (COL_MIN..COL_MAX).each do |col|
-          if self.playable?(row, col)
-            places.push [row, col]
+      if @playable_places_cache.nil?
+        places = []
+        (ROW_MIN..ROW_MAX).each do |row|
+          (COL_MIN..COL_MAX).each do |col|
+            if self.playable?(row, col)
+              places.push [row, col]
+            end
           end
         end
+        @playable_places_cache = places
       end
-      places
+      @playable_places_cache.clone
     end
 
     def changeable_places
-      places = []
-      if @token != opponent
-        (ROW_MIN..ROW_MAX).each do |row|
-          (COL_MIN..COL_MAX).each do |col|
-            if self.changeable?(row, col)
-              places.push [row, col]
+      if @changeable_places_cache.nil?
+        places = []
+        if @token != opponent
+          (ROW_MIN..ROW_MAX).each do |row|
+            (COL_MIN..COL_MAX).each do |col|
+              if self.changeable?(row, col)
+                places.push [row, col]
+              end
             end
           end
         end
+        @changeable_places_cache = places
       end
-      places
+      @changeable_places_cache.clone
     end

キャッシュを保存するためのインスタンス変数を新たに追加し、キャッシュが空なら実際の呼び出しを行って、そうでなければキャッシュに保存されている内容を使うようにしてある。

この修正を加えて先程と同じようにプロファイルをしてみると、次のような結果になった。

$ ruby -r profile greedy_com.rb 1> /dev/null
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 28.60    35.97     35.97  1549276     0.02     0.03  YWF::Board#color
 16.61    56.87     20.90   441897     0.05     0.08  YWF::Board#traverse_to
  7.66    66.51      9.64  1004058     0.01     0.12  YWF::Board#count
  6.26    74.38      7.87  1594437     0.00     0.01  BasicObject#!=
  6.03    81.96      7.58  6102807     0.00     0.00  Array#[]
  5.77    89.22      7.26  6197106     0.00     0.00  Fixnum#<
  5.33    95.93      6.71   190800     0.04     1.22  Range#each
  3.94   100.89      4.96   310206     0.02     0.16  YWF::Board#playable?
  3.16   104.87      3.98   347256     0.01     0.13  YWF::Board#copy
  3.08   108.75      3.88   698284     0.01     0.06  YWF::Board#has_color_from_to?
  2.71   112.16      3.41  2806018     0.00     0.00  Fixnum#==
  1.92   114.57      2.41  1806569     0.00     0.00  Fixnum#+
  1.80   116.83      2.26   351379     0.01     0.46  YWF::Board#playable_places
  1.73   119.00      2.17   469574     0.00     0.15  YWF::Board#has_color_from?
  1.49   120.88      1.88    70356     0.03     2.26  Array#each
  1.05   122.20      1.32   287180     0.00     0.01  Proc#call
  0.37   122.67      0.47   404806     0.00     0.00  Array#[]=
  0.37   123.14      0.47    57039     0.01     0.24  YWF::Board#put_piece
  0.33   123.56      0.42    23179     0.02     0.18  YWF::Board#changeable?
  0.21   123.82      0.26    18291     0.01     0.23  YWF::BoardViewer#view
  0.18   124.05      0.23   143114     0.00     0.00  Fixnum#-
  0.14   124.23      0.18    16684     0.01     0.01  YWF::BoardViewer#mark
  0.11   124.37      0.14    18090     0.01     0.01  Kernel#print
  0.11   124.51      0.14    69759     0.00     0.00  Fixnum#*
  0.09   124.62      0.11     7396     0.01     9.56  YWF::Board#game_end?
  0.09   124.73      0.11    23289     0.00     0.52  YWF::Board#changeable_places
  0.06   124.81      0.08    26938     0.00     0.00  IO#write
  0.06   124.88      0.07     7830     0.01     7.18  YWF::Board#must_pass?
  0.06   124.95      0.07     3597     0.02    26.17  YWF::GreedyCom#calculate_board_value
  0.06   125.02      0.07     8458     0.01     0.01  Kernel#clone
  0.06   125.09      0.07    69759     0.00     0.00  BasicObject#==
  0.06   125.16      0.07     4424     0.02     0.02  IO#puts
  0.05   125.22      0.06     2605     0.02     6.25  YWF::Board#change
  0.05   125.28      0.06     3796     0.02    61.90  YWF::GreedyCom#select
  0.04   125.33      0.05    11653     0.00     1.37  Class#new
  0.04   125.38      0.05     4108     0.01     0.01  YWF::Board#opponent
  0.04   125.43      0.05    28772     0.00     0.00  Array#push
  0.03   125.47      0.04    42422     0.00     0.00  Fixnum#===
  0.03   125.51      0.04     7195     0.01     9.28  YWF::Board#win?
  0.02   125.54      0.03     8458     0.00     0.01  Kernel#initialize_clone
  0.02   125.57      0.03     1191     0.03     5.80  YWF::Board#play
  0.02   125.60      0.03     3796     0.01     0.73  YWF::Board#legal_actions
  0.02   125.63      0.03     3817     0.01     4.17  YWF::Board#initialize
  0.02   125.66      0.03     7833     0.00     0.00  Array#initialize
  0.02   125.68      0.02     2605     0.01     0.01  YWF::Board#change_token
  0.02   125.70      0.02     4424     0.00     0.03  Kernel#puts
  0.02   125.72      0.02     8458     0.00     0.00  Array#initialize_copy
  0.02   125.74      0.02     3816     0.01     0.02  YWF::Board#change_turn
  0.01   125.75      0.01      199     0.05     0.05  Array#to_s
  0.01   125.76      0.01    15101     0.00     0.00  NilClass#nil?
  0.01   125.77      0.01     3598     0.00     0.00  Fixnum#>
  0.01   125.78      0.01     8060     0.00     0.00  Array#size
  0.01   125.79      0.01     7955     0.00     0.00  Kernel#nil?
  0.00   125.79      0.00        1     0.00     0.00  TracePoint#enable
  0.00   125.79      0.00      201     0.00     0.00  Kernel#sprintf
  0.00   125.79      0.00        1     0.00     0.00  YWF::Game#initialize
  0.00   125.79      0.00        2     0.00     0.00  YWF::GreedyCom#initialize
  0.00   125.79      0.00        1     0.00     0.00  #<Object:0x007fce938de460>.include
  0.00   125.79      0.00        1     0.00     0.00  Module#included
  0.00   125.79      0.00        1     0.00     0.00  Module#append_features
  0.00   125.79      0.00        3     0.00     0.00  Kernel#require_relative
  0.00   125.79      0.00        2     0.00     0.00  String#==
  0.00   125.79      0.00        1     0.00     0.00  Module#module_function
  0.00   125.79      0.00     4108     0.00     0.00  Fixnum#%
  0.00   125.79      0.00     1811     0.00     0.00  Fixnum#to_s
  0.00   125.79      0.00        2     0.00     0.00  BasicObject#singleton_method_added
  0.00   125.79      0.00        2     0.00     0.00  Module#private
  0.00   125.79      0.00     3816     0.00     0.00  Kernel#class
  0.00   125.79      0.00        1     0.00     0.00  Module#protected
  0.00   125.79      0.00        1     0.00     0.00  Module#attr_reader
  0.00   125.79      0.00        1     0.00 125780.00  Kernel#loop
  0.00   125.79      0.00     3816     0.00     0.01  YWF::Board#add_move
  0.00   125.79      0.00        3     0.00     0.00  Class#inherited
  0.00   125.79      0.00        6     0.00     0.00  IO#set_encoding
  0.00   125.79      0.00        1     0.00     0.00  MonitorMixin#mon_exit
  0.00   125.79      0.00        1     0.00     0.00  Mutex#unlock
  0.00   125.79      0.00        1     0.00     0.00  MonitorMixin#mon_check_owner
  0.00   125.79      0.00        1     0.00     0.00  MonitorMixin#mon_enter
  0.00   125.79      0.00        1     0.00     0.00  Mutex#lock
  0.00   125.79      0.00      199     0.00     0.00  Symbol#to_s
  0.00   125.79      0.00      398     0.00     0.00  Fixnum#inspect
  0.00   125.79      0.00        3     0.00     0.00  Thread.current
  0.00   125.79      0.00      199     0.00     0.00  Array#flatten
  0.00   125.79      0.00        1     0.00     0.00  TracePoint#disable
  0.00   125.79      0.00       20     0.00     2.00  YWF::Board#pass
  0.00   125.79      0.00       33     0.00     0.00  Module#method_added
 -0.00   125.79     -0.00      202    -0.00  1245.40  YWF::Game#start
  0.00   125.79      0.00        1     0.00 125790.00  #toplevel

見ての通り、かなり改善されていることが分かると思う。
2,191,201回あったYWF::Board#colorの呼び出しは1,549,276回に減り、YWF::Board#traverse_toの呼び出しも895,402回から441,987回に減っている。
全体の実行時間としても、元は196秒近くかかっていたのが、126秒に減っている。
これは約1.5倍のスピードだ。

実行例

さて、スピードも改善されたことだし、ミニマックスAIの実行例を。

[001] turn: O, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | - | O | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | X | - | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [3, 7].
[002] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   |   | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | - | O | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | X | O | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [3, 6].
[003] turn: O, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   | X | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | - | - | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | X | O | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [3, 4].
[004] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   | O |   | X | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | O | O | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | - | O | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [7, 6].
[005] turn: O, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   | O |   | X | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | O | O | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | - | O | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [2, 7].
[006] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   | O |   | - | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | O | O | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | - | O | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [3, 3].
[007] turn: O, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   | X | O |   | - | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | - | O | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | - | - | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [4, 3].
[008] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   | X | O |   | - | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   | O | O | O | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | - | - | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [4, 2].
[009] turn: O, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   | X | O |   | - | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   | X | - | - | - | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | - | - | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [6, 3].
[010] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   | X | O |   | O | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   | X | - | - | O | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | O | - | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   | O | O | X | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
play [3, 2].

〜長いので省略〜

[081] turn: O, token: O
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 2 | O | O | O | - | X | - | - | - | - |
   +---+---+---+---+---+---+---+---+---+
 3 | O | O | - | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 4 | O | - | - | - | - | - | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 5 | O | O | X | O | O | - | O | O | - |
   +---+---+---+---+---+---+---+---+---+
 6 | O | O | X | - | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 7 | - | O | X | O | - | O | O | O |   |
   +---+---+---+---+---+---+---+---+---+
 8 | O | O | X | O | O | - | - | O |   |
   +---+---+---+---+---+---+---+---+---+
 9 | X | - | X | - | - | X | X | O |   |
   +---+---+---+---+---+---+---+---+---+
change [2, 9].
[082] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 2 | O | O | O | O | - | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 3 | O | O | - | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 4 | O | - | - | - | - | - | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 5 | O | O | X | O | O | - | O | O | - |
   +---+---+---+---+---+---+---+---+---+
 6 | O | O | X | - | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 7 | - | O | X | O | - | O | O | O |   |
   +---+---+---+---+---+---+---+---+---+
 8 | O | O | X | O | O | - | - | O |   |
   +---+---+---+---+---+---+---+---+---+
 9 | X | - | X | - | - | X | X | O |   |
   +---+---+---+---+---+---+---+---+---+
change [4, 7].
[083] turn: O, token: O
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 2 | O | O | O | O | - | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 3 | O | O | - | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 4 | O | - | - | - | - | - | X | O | O |
   +---+---+---+---+---+---+---+---+---+
 5 | O | O | X | O | O | X | - | O | - |
   +---+---+---+---+---+---+---+---+---+
 6 | O | O | X | - | - | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 7 | - | O | X | - | - | O | - | O |   |
   +---+---+---+---+---+---+---+---+---+
 8 | O | O | X | O | O | - | X | O |   |
   +---+---+---+---+---+---+---+---+---+
 9 | X | - | X | - | - | X | X | O |   |
   +---+---+---+---+---+---+---+---+---+
change [4, 4].
[084] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 2 | O | O | O | O | - | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 3 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 4 | O | O | O | O | O | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 5 | O | O | - | O | O | X | - | O | - |
   +---+---+---+---+---+---+---+---+---+
 6 | O | O | X | - | - | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 7 | - | O | X | - | - | O | - | O |   |
   +---+---+---+---+---+---+---+---+---+
 8 | O | O | X | O | O | - | X | O |   |
   +---+---+---+---+---+---+---+---+---+
 9 | X | - | X | - | - | X | X | O |   |
   +---+---+---+---+---+---+---+---+---+
play [7, 9].
[085] turn: O, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 2 | O | O | O | O | - | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 3 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 4 | O | O | O | O | O | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 5 | O | O | - | O | O | X | - | O | - |
   +---+---+---+---+---+---+---+---+---+
 6 | O | O | X | - | - | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 7 | - | O | X | X | X | - | X | - | X |
   +---+---+---+---+---+---+---+---+---+
 8 | O | O | X | O | O | - | X | - |   |
   +---+---+---+---+---+---+---+---+---+
 9 | X | - | X | - | - | X | X | O |   |
   +---+---+---+---+---+---+---+---+---+
play [9, 9].
[086] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 2 | O | O | O | O | - | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 3 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 4 | O | O | O | O | O | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 5 | O | O | - | O | O | X | - | O | - |
   +---+---+---+---+---+---+---+---+---+
 6 | O | O | X | - | - | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 7 | - | O | X | X | X | - | - | - | X |
   +---+---+---+---+---+---+---+---+---+
 8 | O | O | X | O | O | - | X | O |   |
   +---+---+---+---+---+---+---+---+---+
 9 | X | - | X | - | - | X | X | O | O |
   +---+---+---+---+---+---+---+---+---+
play [8, 9].
[087] turn: O, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 2 | O | O | O | O | - | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 3 | O | O | O | O | O | O | O | O | O |
   +---+---+---+---+---+---+---+---+---+
 4 | O | O | O | O | O | O | - | O | O |
   +---+---+---+---+---+---+---+---+---+
 5 | O | O | - | O | O | X | - | O | - |
   +---+---+---+---+---+---+---+---+---+
 6 | O | O | X | - | - | O | X | O | O |
   +---+---+---+---+---+---+---+---+---+
 7 | - | O | X | X | X | - | - | X | X |
   +---+---+---+---+---+---+---+---+---+
 8 | O | O | X | O | O | - | X | - | X |
   +---+---+---+---+---+---+---+---+---+
 9 | X | - | X | - | - | X | X | O | O |
   +---+---+---+---+---+---+---+---+---+
----------
black: 51, white: 15
O win.

ランダムAIとの対戦成績も調べたいところだけど、スピードが速くなったとはいえ、まだまだそれなりに時間がかかる・・・
なので、これについてはちょっと持ち越し。

今日はここまで!