モンテカルロ木探索による五目並べAI

Google Colaboratoryの中で五目並べ

Google Colaboratoryの出力部分に五目並べの盤面が表示されてAIと対戦することができます。五目並べAIは、モンテカルロ木探索という手法によって実装されています。

盤面のサイズは6×6、4つのコマが縦、横、斜めにそろうと勝ちとなります。

とりあえずプレイしてみる。

以下に公開されています。
https://colab.research.google.com/drive/1-2wPY_eUUYN7CG7YlP6kQvDQxrR2Hphf?usp=sharing

• Googleアカウントでログインしてください。
• メニューの「ランタイム」「すべてのセルを実行」を選択してください。
• 画面をスクロールして一番下まで移動すると五目並べのゲームが起動しています。
• 「Start」ボタンを押してください。先手がAIで始まります。人の手は、打ちたい盤面をクリックしてください。

モンテカルロ木探索 (MCTS: Monte Carlo tree search)

このAIは、モンテカルロ木探索という手法で実装されています。モンテカルロ木探索とは、盤面がノード（葉）、その盤面から打てる手がエッジ（枝）になっているツリーを、育てながらかつ各盤面の良さをシミュレーションしていく方法です。

大まかにいうと、より良い手になる可能性の高い盤面については出来るだけ先読みをする、だけどあまり試していない盤面についてもそれなりに調べる、という手法です。ある盤面がAIにとって良いか悪いかを判定する手法には様々なものがあります。囲碁で人間の世界チャンピオンに勝利したAlpha Goではニューラルネットワークによってこの盤面の優勢判定をしています。ここでは、その盤面からランダムに手を打ってどちらが勝つかによって決めるとします。このようなとりあえず手を進めてゲームの結末を得ることをplayoutと呼びます。

より詳細には、次の図のように行っています。

1. ある盤面(1)があるとします。この盤面から黒丸の次の一手を決めるのが今回の目的です。
2. (1)から一手先の探索ツリー(2)～(5)を作成します。この時に同じ盤面となるものは作成しません。
3. (2)～(5)から以下の基準によって1つを選択します。それが(2),(3)のような枝ノードの場合はさらにその子ノードから1つを選択するということを繰り返します。
4. 選択された葉ノードの選択回数がn以上となる場合は、そこからさらにその先の探索ツリーを作成します。そうではない場合、ランダムにプレイ(playout)して勝者を決めます。
5. playoutした場合には、その結果を上位ノードに伝搬します。
6. 指定回数だけ、3に戻って処理を繰り返します。
7. 指定回数後に、盤面(1)の子ノード(2)～(5)の中から、最も選択回数の多い手を選び、実際に打ちます。

AIは、一手を選ぶために、上記の処理を行います。特に、3から5までは、時間の許す限り何回も実行します。この回数が多いほどAIは強くなるといわれていて、この五目並べAIの場合には、3から5までを2000回繰り返すと、強いAIが作れることが経験的に分かっています。また、繰り返しシミュレーションしたあとの実際にAIが打つ一手は、参考文献¹と同じようにシミュレーションが実行された最も回数の多い盤面への一手としています。

子ノードから1つのノードを選択する基準：次の式が最大値のノードが選択されます。

Q(s,a)+C_p\frac{\sqrt{2\log{n_s}}}{n_{s,a}}

$Q(s,a)$ : ある盤面sのaという手を打った時の勝率に相当する評価値
$C_p$ : 勝率と選択回数のバランスをとる係数
$n_{s}$ : ある盤面sが選択された回数
$n_{s,a}$ : ある盤面sからaという手が打たれた回数

AIの強さ

このAIの強さは、何回playoutを実行したかのシミュレーション回数によって決まります。何度か試したところ、100回のシミュレーション回数で人間より強くなることがある、2000回で人間より強いことが多い、3000回ぐらいだとAIが失敗してくれない限りAIには人間は勝てない、という感じになります。もちろんこれは、先手をAIとしているためです。先手が強いこのゲームでは、2000回ぐらいのシミュレーション回数以降は、あまり失敗をせず、後手は勝てないという感じです。

このAIは、何をしているのか？

とにかくランダムに手を打って、その中から良いものを選んでいます。AIが知っていることは、①勝利条件は4つのコマが連続に並ぶことである、②すでにコマが置いてあるマスの上に新たなコマを置けない、だけです。人がゲームの攻略法として考えたりする、例えばこのゲームの場合には”両端に空きがある3個連続のコマを作ると相手は片方の端を防いでも次の回に残った方の端を打たれて勝負は決する”という攻略法のようなものはAIは一切知りません。それらの人間の知識を実装しなくても、結果的に、それらの知識を知っているかのような動きをAIはします。それを人間が見ると、AIは攻略法を学んだというように見えることもあります。実際には学んでいないのですけど....

モンテカルロ木探索の可能性と限界

盤面の状態をすべて表した探索空間を全探索することができない限り、何かしらの手法によって、限定的に手を探索することになります。そのときに、どれを探索対象として、どれを探索しないのかを決めるのの違いが、探索手法の違いです。例えば、αβ探索のような手法では、実際に探索してみなければ、探索するためにどれだけの時間が必要なのかを知ることはできません。言い換えると、探索を途中でやめてしまうと、その段階での最適解とはなっていないことが多いです。一方モンテカルロ木探索は、最適解の可能性の高いところから基本的には探索します。よって、探索を途中でやめても、その段階における最も良い解になっているとみることができます。この時間に比例した探索性能は、現実的にゲームAIなどとして使用するときにとても良い特性となります。

一方、playoutが実装しにくいゲームような盤面からのゲームの結末が容易に得られない問題に対しては、モンテカルロ木探索を効果的に使用することは出来ません。そこを克服するために、このplayoutの部分にディープラーニングのような機械学習手法¹を取り入れることがあります。

ソースコード

実際のソースコードです。主なコンポーネントは次のように構成されています。

昨日	構成
五目並べの画面	JavaScriptで記述し、display(IPython.display.Javascript(js_code))で表示する。
五目並べAI	Pythonのnext_aiという関数で作成する。そのnext_aiをfrom google.colab import outputでインポートしたoutput.register_callback("next_ai",next_ai)によってJavaScript側からコールできるようにする。
モンテカルロ木探索	class Stateで実装され、next_ai関数の中で実体化され指定回数だけ処理が実行される。
モンテカルロ木探索の処理に関係が無いゲーム独自の部分	class Gameで実装され、勝利判定、同一盤面かの比較、playoutなどが実行される。
勝利判定	judge関数として実装される。
同一盤面の比較	class cell_comparatorとして実装される。
盤面サイズと勝利条件になる何個の駒が連続すれば良いかの設定	params = {"length":6,"n_pieces":4}という変数で、lengthに盤面のサイズ、n_piecesに勝利条件の連続駒数を設定する。

盤面サイズと勝利条件になる連続駒数の設定

#
# ゲーム盤面の大きさ(length)と、何個並べると勝ちか(n_pieces)の設定
#
params = {"length":6,"n_pieces":4}

勝利判定

#
# 勝利判定(map, filterなどを使用して、より簡潔にまとめたもの)
#
import random
from itertools import chain
from itertools import groupby

# 勝者判定
def judge(cells,length=params["length"],n_pieces=params["n_pieces"]):
  # 盤面の特定の位置をx,yで表しているpから、盤面配列のインデックス（1つの数値）に変換する。
  def xy2i(p):
    return p[1]*length+p[0]
  # x,yが盤面の中に入っているかを判定する。
  def is_in(p):
    return p[0]>=0 and p[0]<length and p[1]>=0 and p[1]<length
  
  # 行、列番号を生成する。
  index = [i for i in range(length)]
  xindex0 = [i for i in range(-length+n_pieces,length-n_pieces+1)]
  xindex1 = [i for i in range(n_pieces-1,length*2-n_pieces)]

  # 横、縦、斜めのラインをすべて列挙する。
  lines = chain.from_iterable([
    # 縦のライン
    map(lambda x:map(lambda y:[x,y],index),index),
    # 横のライン
    map(lambda y:map(lambda x:[x,y],index),index),
    # 右下がりの斜めライン
    map(lambda x:list(filter(lambda p:is_in(p),map(lambda y:[x+y,y],index))),xindex0),
    # 左下がりの斜めライン
    map(lambda x:list(filter(lambda p:is_in(p),map(lambda y:[x-y,y],index))),xindex1),
  ])

  # チェック対象のラインを1つずつ取り出して確認する。
  for line in lines:
    # ラインの配列インデックスから、配列の値を求める。
    values = [cells[xy2i(p)] for p in line]
    # 連続する個数を調査する（第1回小テストの内容をgroupbyを使って簡略化したもの）
    win = list(filter(lambda x:len(list(x[1]))>=n_pieces,groupby(values)))
    if len(win)>0:
      # 勝者がいる場合は、その勝者の数値(1 or -1)を返す
      return (win[0][0])
    pass
  # 勝者なしの場合は、0を返す。
  return 0

# judgeメソッドのテスト
n = params["length"]
cells = [random.randint(-1,1) for i in range(n**2)]
[print(list(map(lambda x:"〇" if x==1 else "×" if x==-1 else "  ",cells[i*n:i*n+n]))) for i in range(n)]
print("勝者",["なし","〇","×"][[0,1,-1].index(judge(cells))])

同一盤面の比較

#
# 同一盤面のチェック
# (回転、反転したインデックス配列を保持して、すべてのケースをチェックするクラス)
#
import random

# 予めすべての同一盤面ケースのインデックス配列を作成しておいて、
# それによって同一盤面かをチェックするクラス
class cell_comparator:
  # インデックス配列を保持する配列
  indexes = []
  # 盤面のサイズ（1辺にあるセルの数）
  length = 0

  # 横軸縦軸の座標からセル配列におけるインデックスを求める。
  def xy2i(self,x,y):
    return y*self.length+x

  # インデックスを右に90度回転させる
  def rotate(self,index):
    return [index[self.xy2i(y,self.length-1-x)] for y in range(self.length) for x in range(self.length)]

  # インデックスを左右反転する。
  def flip(self,index):
    return [index[self.xy2i(self.length-1-x,y)] for y in range(self.length) for x in range(self.length)]

  # クラスのコンストラクタ
  # インスタンス生成時に一度だけ実行される。
  # ここで、同一盤面になるすべてのインデックス配列を作成して、メンバ変数に保存しておく。
  def __init__(self,length):
    self.length = length

    # 最初に0から順番のインデックス配列を作成する。
    self.indexes = [[i for i in range(self.length**2)]]
    for i in range(2):
      # self.indexesにある最後のインデックス配列を3回、右に回転する。
      for j in range(3):
        self.indexes.append(self.rotate(self.indexes[-1]))
        pass
      # 1巡目の場合には、最初のインデックス配列を左右反転したものをself.indexesの最後に追加する。
      if i==0:
        self.indexes.append(self.flip(self.indexes[0]))
        pass
      pass
    return

  # 2つの盤面を指定して、回転、左右反転を含めて同一盤面かをチェックする。
  # 戻り値: True 同じ盤面、False 違う盤面
  def compare(self,cells0,cells1):
    # 回転、反転等のすべてのインデックス配列について調査する。
    for index in self.indexes:
      # index配列のインデックスはcells0のインデックス、
      # index配列の値は、cells1のインデックスとして比較すると、
      # cells0は無変換、cells1はindexで変換した行列を比較することになる。
      for i0,i1 in enumerate(index):
        if cells0[i0]!=cells1[i1]:
          break
      else:
        # すべてのインデックスで同じ値だった場合は同じ盤面なので、Trueで終了する。
        return True
    return False
  pass

# cell_comparatorのテスト
# 〇(配列上の数値は1)から3手をランダムに打って、同じ盤面かどうかを確認する。
# これを、同じ盤面になるまで繰り返す。
# 同じ盤面なる2つの盤面を見つけたときに、それを出力して、プログラムは終了する。

n = params["length"]
comparator = cell_comparator(params["length"])

モンテカルロ木探索に依存しないゲーム独自の部分の実装

#
# モンテカルロ木探索で使用するゲームの種類に依存する部分
#
# 状態
# cells: マスの配列で、その要素は、コマがあるところはプレイヤーの番号、0は空とする。
# p0_q: p0(この盤面における次の手番プレイヤ)の評価値
#
import copy
class Game():
  # 勝利判定を行う。player番号は1と-1とし、勝者の番号を出力する。勝利状態ではない場合は0を返す。
  def judge(self,state):
    return judge(state["cells"])
  # 2つの盤面が同一かどうかを比較する。同じ場合True、違う場合はFalseを返す。
  def compare(self,state0,state1):
    return comparator.compare(state0["cells"],state1["cells"])
  # 引数の盤面からの有効手を取得する。同じ盤面になる手は、ここでは考慮しなくて良い。
  # MTCSは、game.compareを使用して、有効手から同じ盤面になる手を除外して処理を進める。
  # playoutは、この有効手をシャッフルしてランダムに手を進める。
  def actions(self,state):
    return [i for i,v in enumerate(state["cells"]) if v==0]
  # 現在の盤面から一手を打つ
  # state: 盤面、player: 手を打つプレイヤの番号、action: 何をするか(五目並べの場合は、打つ場所)
  def move(self,state,action):
    # ステートのコピー
    state2 = copy.deepcopy(state)
    # 一手を打つ
    state2["cells"][action] = state["p0_q"]
    #プレイヤの交代
    state2["p0_q"] = state["p0_q"]*-1
    return state2
  
  # playout
  def playout(self,state):
    # 盤面の空欄を有効手一覧をして取得する。
    actions = self.actions(state)
    # 空欄のインデックスをシャッフルする。
    random.shuffle(actions)
    # 現在の盤面をコピーする。
    s2 = copy.deepcopy(state)
    # 勝敗が付くまで、空欄に手番を変えて順番にコマを置いていく。
    for i,a in enumerate(actions):
      s2 = self.move(s2,a) #state["p0_q"]*[1,-1][i%2]
      j = game.judge(s2)
      if(j!=0):
        # 勝者のプレイヤー番号を返す。
        return j
      pass
    # 引き分けの場合は、プレイヤー番号(1,-1)の中間値の0を返す。
    return 0.0 #引き分け

  def str2state(self,state_str):
    state = {}
    state["cells"] = list(map(lambda x:int(x),state_str.split(",")))
    state["p0_q"] = -1
    return state
  pass

game = Game()

モンテカルロ木探索

#
# モンテカルロ木探索
# 1つ前のセルにある、勝利判定と盤面の同一性調査を使用する。
#
# プレイヤの番号は、1と-1とする。それをそのまま評価値として使用する。
# よってgame.judgeは、勝者の番号をそのまま出力し、引き分けは0を返すとする。
#
from google.colab import output
import numpy as np
import math

# この回数だけ選択された盤面は、Expand処理として子ノードを作成して木を成長させる。
exp_limit = 8
# 選択フェーズにおいて、選択の評価値q+c(n) (q:盤面の評価値、c(n)選択回数の評価値)の選択回数の方にかける係数
cp = 1.0

# Stateオブジェクトを再利用するために、グローバル変数に配列を用意してそこにすべて保存する。
# この配列内のインデックスは、Stateオブジェクトのcss_indexで保持している。
css = []
# 盤面sと、そこからの次の一手のプレイヤーplayerを表すStateオブジェクトを検索する。
# Stateオブジェクトが無い場合は、生成して返す。
def find(s):
  global css
  for csi in css:
    if(game.compare(csi.s,s)):
      return csi
    pass
  css += [State(s)]
  css[-1].set_css_index(len(css)-1)
  return css[-1]

# class a state representing an condition of all stones on the borad
class State():
  # この盤面の状態、ゲームによって表し方は異なる。
  s = None
  # この盤面からの有効手一覧。配列要素の形式は、ゲームによって異なる。expandで初期化される。
  sa = None
  # この盤面からの有効手が選択された回数。親ノードのcss_index毎に管理される。
  na = None
  # この盤面からの有効手の評価値。親ノードのcss_index毎に管理される。
  qa = None
  # このオブジェクトのグローバル配列css内でのインデックス
  css_index = -1
  def __init__(self,s,expand=False):
    self.s = s
    #self.p = p
    self.na = {}
    self.qa = {}
    if(expand):
      # 初期化時に展開する場合は、選択回数、評価値ともに0、このノードの親は無いのでcss_indexは-1
      self.expand(n=0,q=0,css_index=-1)
      pass
    return
  # このオブジェクトにグローバル変数css内のこのオブジェクトのインデックスを設定する。
  def set_css_index(self,index):
    self.css_index = index
    pass
  def debug_print(self,switch=False):
    if(switch):
      print("---------------------")
      print("self.sa",self.sa)
      print("self.na",self.na)
      print("self.qa",self.qa)
      pass
    pass
  # css_indexを親ノードとして、その親ノードからのルートでこのノードに子ノードが存在しない場合にTrueを返す。
  def is_leaf(self,css_index):
    return css_index not in self.na
  # 終局しているかを確認する。
  def is_finished(self):
    return (not 0 in self.s) or 0!=game.judge(self.s)
  # 選択するノードを選ぶ。css_indexは、このノードの親のノードが指定される。
  def select(self,css_index=-1):
    ns = sum(self.na[css_index])
    def cost(ns,n):
      return math.sqrt(2*math.log(ns))/n
    
    i = np.argmax(list(map(lambda x:x[1]*self.s["p0_q"]+cp*cost(ns,x[0]),zip(self.na[css_index],self.qa[css_index]))))
    
    ai = self.sa[i]
    #print("selected",ai)
    # 盤面の選択回数self.naは、同じ回数だったときにランダムに1つが選ばれるように、1未満の乱数を足しておく。
    # その乱数は、選択回数が増えるたびに更新する。
    self.na[css_index][i] = (self.na[css_index][i]+1)//1 + random.random()
    # 選択された次の一手を打つ。
    s2 = game.move(self.s,ai)
    
    # 次の手を打った盤面のStateオブジェクトを検索する。ここで盤面が履歴にない場合は、自動的に作成される。
    cs2 = find(s2)
    if(cs2.is_leaf(self.css_index)): #葉の場合
      if(cs2.is_finished()==False and self.na[css_index][i]>=exp_limit):        
        cs2.expand(self.na[css_index][i],self.qa[css_index][i],self.css_index)
      else:
        self.qa[css_index][i] = (self.qa[css_index][i]*(self.na[css_index][i]-1)+cs2.evaluate())/self.na[css_index][i]
      pass
    else: #葉ではない
      self.na[css_index][i],self.qa[css_index][i] = cs2.select(css_index=self.css_index)
      pass

    return sum(self.na[css_index]),np.average(self.qa[css_index], weights=self.na[css_index])
  # 木を展開する。n,q,css_indexは、親ノード（このStateオブジェクト）の選択された回数、評価値、グローバル変数css内のインデックス
  def expand(self,n,q,css_index):
    # 盤面が空欄（==0）のインデックスを配列として取得する。
    sa_candidate = game.actions(self.s)
    
    # 同じ盤面になる手を除外した有効手一覧
    sa_candidate_s = []
    
    # 既に同じ盤面になる手がsa_candidate_sに含まれているかを確認する関数
    def already_in(s):
      for si in sa_candidate_s:
        if(game.compare(s,si)):
          return True
        pass
      return False
    
    # この盤面が管理する次の有効手一覧
    self.sa = []
    
    # 有効手の候補をすべてループする。
    for sa_i in sa_candidate:
      # 次の一手をsa_iの場所に打つ。
      s2 = game.move(self.s,sa_i)
      #s2[sa_i] = self.p
      # 一手打った手が、初見の盤面の場合、
      if(already_in(s2)==False):
        # 既にチェックした盤面sa_candidate_sに追加する。
        sa_candidate_s += [s2]
        # 子ノードの盤面一覧に追加する。
        self.sa += [sa_i]
        pass
      pass
    # 重複を除去した有効手の個数
    ns = len(self.sa)
    # 有効手が選ばれた回数を初期化する。乱数によって初期化することによって、
    # 選択回数が1未満のときは、ランダムに1つが選ばれることになる。
    na = [random.random() for i in range(ns)]
    rtotal = sum(na)
    # nはこのノード（expandするノードの親)の選択回数でこれを下の子ノードに分配する。
    # 計算上エラーがでないように、浮動小数点誤差を考慮して、最小値を1ではなく1.01とする。
    n = max(1.01,n)
    self.na[css_index] = list(map(lambda x:n*x/rtotal,na))
    self.qa[css_index] = [q for i in range(ns)]    
    return
  # 現在の盤面を評価する。
  def evaluate(self):
    # すでに勝敗が決まっているかをチェックする。
    j = game.judge(self.s)
    if(j!=0):
      # 勝者のプレイヤー番号を返す。
      return j
    
    # ゲームのplayout(最後まで手を進めて勝敗を決める)
    return game.playout(self.s)
    
  # シミュレーションの結果から、一手を選ぶ。
  def solution(self):
    # 親ノード無しのcss_index=-1の値を取得する。css_index=0のオブジェクトでしか実行できない。
    return self.sa[np.argmax(self.na[-1])]
  pass

# next ai interface
def next_ai(state,n=2000):
  # 現在の盤面状態(cells)、次の手番(-1)、最初のStateは無条件でExpandするのでexpand=TrueによってStateオブジェクトを生成する。
  #cs = State(game.str2state(state.data),expand=True)
  #print(type(state["data"]),state["data"])
  cs = State(game.str2state(state["data"]),expand=True)
  cs.set_css_index(0)
  
  # グローバル変数のstate一覧に、最初のstateを追加する。
  global css
  css = [cs]

  # 指定回数分だけ、selectを実施する。selectの中では、evaluate, expand, (暗黙的に)backupを実行している。
  for epoch in range(n):
    cs.select()
    pass
  return cs.solution()
output.register_callback("next_ai",next_ai)

五目並べのユーザインターフェースとゲームの開始

#
# 五目並べのUI
#
import IPython
html = '''
<link rel="stylesheet" href="//code.jquery.com/ui/1.12.1/themes/base/jquery-ui.css">
<script src="https://code.jquery.com/jquery-1.12.4.min.js" type="text/javascript"></script>
<style>
    #dialog {
        padding: 10px;
    }

    #canvas-wrapper {
        float: left;
        width: 120px;
        height: 120px;
    }

    #status {
        clear: both;
    }

    .unavailable {
        pointer-events: none;
        background-color: grey;
    }

    .status-none:before {
        background-color: white;
        color: black;
        content: "please tap start button";
    }

    .status-human_turn:before {
        background-color: blue;
        color: white;
        content: "your turn";
    }

    .status-ai_turn:before {
        background-color: pink;
        color: black;
        content: "ai turn";
    }

    .status-human_win:before {
        background-color: lime;
        color: black;
        content: "you win !";
    }

    .status-ai_win:before {
        background-color: purple;
        color: white;
        content: "AI win !";
    }

    .status-tie_win:before {
        background-color: white;
        color: black;
        content: "draw!"
    }
</style>
<div id="dialog" title="Gomoku">
    <div id="canvas-wrapper">
        <canvas id="dlg-canvas"></canvas>
    </div>
    <button id="start">Start</button>
    <div id="status"></div>
</div>
<script>
    let websocket = undefined;
    const dtool = {
        "ctx": undefined,
        "params": undefined,
        "values": undefined,
        "screen_width": undefined,
        "screen_height": undefined,
        "turn": 0,
        "init": function (params) {
            this.params = params;
            const canvas = document.getElementById(this.params.canvas_id);
            this.ctx = canvas.getContext('2d');
            canvas.addEventListener("click", e => this.onClick(e), false);
            $("#" + this.params.canvas_id).attr("width", $("#" + this.params.canvas_wrapper_id).width());
            $("#" + this.params.canvas_id).attr("height", $("#" + this.params.canvas_wrapper_id).height());
            this.screen_width = canvas.width;
            this.screen_height = canvas.height;
            this.params.cell_width = Math.trunc(canvas.width / this.params.cell_size);
            this.params.cell_height = Math.trunc(canvas.height / this.params.cell_size);
            this.setTurn(0);
            const button_start = document.getElementById(this.params.start_id);
            button_start.addEventListener("click", e => this.onStart(e), false);
            this.clear();
        },
        "clear": function () {
            this.ctx.clearRect(0, 0, this.screen_width, this.screen_height);
            this.values = Array(this.params.cell_size * this.params.cell_size).fill(0);
            this.setTurn(0);
            this.draw();
        },
        "start": function () {
            if (websocket !== undefined) {
                websocket.send(JSON.stringify({ action: "reset" }));
            }
            this.setTurn(this.params.first_turn);
            this.draw();
        },
        "setTurn": function (t) {
            if (t == -1) {
                $("#start").addClass("unavailable");
                this.next_ai();
            } else {
                $("#start").removeClass("unavailable");
            }
            this.turn = t;
        },
        "onStart": function (e) {
            this.clear();
            this.start();
        },
        "onClick": function (e) {
            if (this.turn == 1) {
                const rect = e.target.getBoundingClientRect();
                x = e.clientX - rect.left;
                y = e.clientY - rect.top;
                const isin = function (v, st, l) {
                    return v >= st && v <= (st + l);
                };
                if (isin(x, this.params.offset_x, this.params.cell_width * this.params.cell_size) && isin(y, this.params.offset_y, this.params.cell_height * this.params.cell_size)) {
                    xi = Math.floor((x - this.params.offset_x) / this.params.cell_width);
                    yi = Math.floor((y - this.params.offset_y) / this.params.cell_height);
                    if (this.values[yi * this.params.cell_size + xi] === 0) {
                        this.values[yi * this.params.cell_size + xi] = 1;
                        w = this.judge(this.params.n_pieces);
                        this.setTurn(w.player === 0 ? (this.tie() ? 10 : -1) : w.player * 2);
                        this.draw();
                    }
                }
            }
        },
        "tie": function () {
            return this.values.indexOf(0) == -1;
        },
        "judge": function (num_chain) {
            const sz = this.params.cell_size;
            const nc = num_chain;
            const xy2i = function (x, y) { return y * sz + x; };
            const is_in = function (a) {
                return a[0] >= 0 && a[1] >= 0 && a[0] < sz && a[1] < sz;
            };
            const index = [...Array(sz).keys()];
            const xindex0 = [...Array(sz * 2 - 1).keys()].map(x => x - sz + 1);
            const xindex1 = [...Array(sz * 2 - 1).keys()].map(x => sz * 2 - 2 - x);
            const p = [
                index.map(x => index.map(y => [x, y])),
                index.map(y => index.map(x => [x, y])),
                xindex0.map(x => index.map(y => [x + y, y]).filter(a => is_in(a))).filter(a => a.length >= nc),
                xindex1.map(x => index.map(y => [x - y, y]).filter(a => is_in(a))).filter(a => a.length >= nc),
            ];
            const self = this;
            const count = function (p) {
                for (let i in p) {
                    const counter = { "1": 0, "-1": 0 };
                    const max_counter = { "1": 0, "-1": 0 };
                    for (let j in p[i]) {
                        const v = self.values[xy2i(p[i][j][0], p[i][j][1])];
                        if (v in counter) {
                            counter[v]++;
                            counter[v == 1 ? "-1" : "1"] = 0;
                            max_counter[v] = Math.max(max_counter[v], counter[v]);
                        } else {
                            counter["1"] = 0;
                            counter["-1"] = 0;
                        }
                    }
                    for (let k in max_counter) {
                        if (max_counter[k] >= nc) {
                            return { "player": Number(k), "chains": max_counter[k] };
                        }
                    }
                }
                return { "player": 0 };
            };
            let w;
            for (let i in p) {
                w = count(p[i]);
                if (0 !== w.player) {
                    break;
                }
            }
            return w;
        },
        "draw": function () {
            const x = this.params.cell_size;
            const y = this.params.cell_size;
            for (let xi = 0; xi < x; xi++) {
                for (let yi = 0; yi < y; yi++) {
                    let v = this.values[yi * x + xi];
                    px = xi * this.params.cell_width + this.params.offset_x;
                    py = yi * this.params.cell_height + this.params.offset_y;
                    if (v == 1) {
                        this.ctx.fillStyle = "blue";
                        this.ctx.fillRect(px, py, this.params.cell_width, this.params.cell_height);
                        this.ctx.fillStyle = "black";
                    } else if (v == -1) {
                        this.ctx.fillStyle = "pink";
                        this.ctx.fillRect(px, py, this.params.cell_width, this.params.cell_height);
                        this.ctx.fillStyle = "black";

                    }
                    this.ctx.strokeRect(px, py, this.params.cell_width, this.params.cell_height);
                }
            }
            const tnames = ["none", "human_turn", "human_win", "ai_turn", "ai_win", "tie_win"];
            tnames.map(c => $("#" + this.params.status_id).removeClass("status-" + c));
            const tname = tnames[[0, 1, 2, -1, -2, 10].indexOf(this.turn)];
            $("#" + this.params.status_id).addClass("status-" + tname);
            const winner = tname.match(/_win$/);
            if (websocket !== undefined && null !== winner) {
                websocket.send(JSON.stringify({ action: "gameset", "winner": winner.input.substring(0, winner.index) }));
            }
        },
        "play": function (pos) {
            this.values[pos] = -1;
            w = this.judge(this.params.n_pieces);
            this.setTurn(w.player === 0 ? (this.tie() ? 10 : 1) : w.player * 2);
            this.draw();
        },
        "next_ai": function () {
            params = { data: this.values.join(), };
            if (websocket === undefined) {
                const self = this;
                const command = "next_ai('" + this.values.join() + "')";
                const f = async function () {
                    const result = await google.colab.kernel.invokeFunction("next_ai", [params]);
                    if ('data' in result) {
                        const out = Number(result.data['text/plain'].replace(/\'/g, ""));
                        self.play(out);
                    }
                };
                f();
            } else {
                websocket.send(JSON.stringify(Object.assign({ action: "next" }, params)));
            }
        },
    }
    dtool.init({
        first_turn: -1,
        cell_size:%%length,
        n_pieces:%%n_pieces,
        canvas_id: "dlg-canvas",
        canvas_wrapper_id: "canvas-wrapper",
        start_id: "start",
        status_id: "status",
        offset_x: 0,
        offset_y: 0,
        cell_width: undefined,
        cell_height: undefined,
    });
    if (websocket === undefined) {
    } else {
        websocket.onopen = function (event) {
            websocket.onmessage = function (event) {
                data = JSON.parse(event.data);
                if (data.type === "action") {
                    var out = Number(data.place);
                    dtool.play(out);
                } else if (data.type === "users") {

                } else if (data.type === "state") {
                    for (var k of Object.entries(data).filter(x => x[0] != "type")) {
                        $("#" + k[0]).text(k[1]);
                    }
                }
            };
        };
    }
</script>
'''
for k in params:
  html = html.replace("%%"+k,str(params[k]))
  print("%%"+k,str(params[k]))
display(IPython.display.HTML(html))

1. https://www.nature.com/articles/nature16961 ↩ ↩²