暗記学習(Rote Learning)で三目並べを強くする

Pocket

最近は、機械学習、深層学習を用いたAIと呼ばれるものが流行していますが、我々人間も生まれてからずっと学習しています。例えば、社会などの科目では、暗記をするという学習を行ってきたと思います。そこで今回は、単純で有名なゲームである三目並べ(Tic-Tac-Toe)を、暗記学習で強くしてみます。暗記学習で三目並べを強くする方法は有名らしく、私は以下の書籍の内容を基にPythonで実装してみました。

参考書籍: 

  • 人工知能学大事典
    • 著者  : 人工知能学会 編
    • 版表示 : 初版
    • 出版者 : 共立出版
    • 出版年 : 2017年7月

実装コード:

1.三目並べとは

Wikipedia( https://ja.wikipedia.org/wiki/%E4%B8%89%E7%9B%AE%E4%B8%A6%E3%81%B9 )による説明では、三目並べとは次のようになります。

ノートや黒板などでも手軽に遊べることから広く普及している遊びの一種。まず「井」の文字に似た直線の格子図形を描き、二人で先攻後攻を決める。そしてどちらかが「○」でどちらかが「×」となり、先攻後攻と交互に井の字の空いたマスに書き込んでいく。そして最終的にビンゴのように、縦・横・斜めのいずれか1列に3個自分のマークを並べると勝ちとなる。

私は、これまで「〇×ゲーム」と呼んでいましたが、皆さんもその方がイメージしやすいのではないでしょうか。海外では、先攻が「×」となるそうなので、今回の実装はそれにならっています。ちなみに、Google検索で、キーワード「三目並べ」で検索すると、ブラウザ上で実際にゲームが無料でできますが、そのゲームでも、先攻は「×」でした。

2.暗記学習で三目並べを強くする方法

前述にあるように、私は参考書籍に書かれている内容を基に実装したのですが、そこに書かれていた処理内容は下記の通り認識しました。また、以下にある材料を用意すれば、アナログなものだけで実装できるということです。

■必要な材料:

  • マッチ箱
    • 必要数:全局面数(=19683個)
      (1マス当りに「×」「〇」「空白」の3通りあり、マスが9個あるので、3の9乗)
  • ビーズ
    • 無数(9色。各色毎に無数)
      (各色が、9マスのどこの位置かを示す)

■学習手順:

  • 事前準備
    • 各マッチ箱に各色のビーズを1個ずつ入れておく
  • ゲーム開始
    • 該当する局面のマッチ箱をよく振って、中身を見ないでビーズを1個取り出す
      (取り出したビーズが指し手となる)
    • 上記を繰り返す
    • ゲームに勝った場合
      • 勝者の差した局面のマッチ箱毎に、勝者の取り出したビーズと同じ色のビーズを1個増やす
        ※指し手の重みを増す(=この指し手は選択される確率が高くなる)
    • ゲームに負けた場合
      • 敗者が最後に指した局面のマッチ箱から、敗者の取り出したビーズと同じ色のビーズを全て捨ててしまう
        ※今後のこの指し手は選択できなくなる
    • 該当の局面のマッチ箱が空だった場合
      • 投了とする
      • 敗者が最後に指した局面のマッチ箱から、敗者の取り出したビーズと同じ色のビーズを全て捨ててしまう
        ※今後のこの指し手は選択できなくなる
  • このゲームを何度も繰り返していく
    • これが学習となる

3.実装時のデータ構造

マッチ箱についてはPythonの辞書型データで、マッチ箱の中のビーズは、辞書のvalueとして、リスト型データで対応しました。

  • Key:局面を表す文字列
    • 例えば、以下のようにしてkeyを作成する
  • value:ビース(=次の指し手の重み)を表すリスト
    • 下記例(先攻:×、後攻:〇)の場合、右上を指すようにすべきなので、リストの3番目の要素の重みが増していくことになる
      ※今思えば、使用済みのマスの重みを事前に「0」にしておけばよかった(プログラムでそこは選択できないように制御しています)

4.未学習時の対戦成績

まずは、何も学習せず、空いているマスをランダムに指すマシン同士の対戦成績を確認します。下図は、マシン同士が、100戦1セットの対戦を100セット(合計10,000戦)行った勝敗数をグラフにしたものです。

赤色の「cross」が先攻の「×」の勝ち星数、緑色の「circle」が後攻の「〇」の勝ち星数、青色の「draw」が引き分け数を表しています。点線は、その移動平均です。ランダムに指し手を決めると、先攻がよく勝つようですね。

5.学習と対戦成績

では、いよいよ暗記学習を行ってみます。

最初は、先攻マシンのみを100セット学習させました。先攻マシンは、学習結果を使って次回以降の指し手を決めていきます。後攻マシンは常に空いているマスをランダムに指し続けています。対戦成績は以下の通りです。

先攻「cross」(×)がどんどん勝率を高めていっていますね。引き分けも含めた黄色い線(「not lose」)を見ると、9割負けないマシンに成長しました。

次は、後攻マシンのみを100セット学習させました。後攻マシンは、学習結果を使って次回以降の指し手を決めていきます。先攻マシンは常に空いているマスをランダムに指し続けています。対戦成績は以下の通りです。

後攻「circle」(〇)は、学習開始当初は、先攻「cross」(×)に負けていましたが、その後逆転し、どんどん勝率を高めていっていますね。引き分けも含めた黄色い線(「not lose」)を見ると、9割負けないマシンに成長しました。

ちなみに、それぞれの学習は、どのぐらいの局面(マッチ箱)を学習できたのでしょうか。下図のように、学習の当初に急激に学習した局面の数を伸ばしていますが、逓減していき、2,000ぐらいになっていきました。全ての局面の数は、3の9乗である19,683ですが、学習した局面の数は2,000+2,000の4,000程度です。なぜこのように少ない数でこれだけの成績を収められたのか。それは、負けた際の指し手の重みを0にして、その指し手以降の局面に遭遇しないようにしているからです。

※学習済みの局面数の詳細:

  • 学習済みの局面数(先攻): 2,156 
  • 学習済みの局面数(後攻): 2,071 
  • 学習済みの局面で、先攻と後攻での重複数: 0 
  • 学習済みの局面数(先攻+後攻): 4,227

6.学習済みマシン同士の対戦

6-1.学習済み先攻マシン vs 学習済み後攻マシン

先攻、後攻のマシンがそれぞれ強くなったので、対戦させてみましょう。対戦成績(100セット)は、以下の通りです。

引き分けばかりになりましたね。

6-2.学習済み先攻/後攻マシンをさらに学習させる

続いて、このように強くなった各マシンを対戦させながら、さらに100セット学習させてみました。対戦成績は、以下の通りです。

さらに、引き分けばかりになりましたね。まだ、学習の余地があったようです。再学習前後の局面数を比較すると、再学習前の局面数が「4,227」だったのに対し、再学習後は、「4,313」に少しだけですが増加していました。

6-3.先攻/後攻マシンを同時に最初から学習させる

これまで、先攻と後攻を別に学習させましたが、同時に学習しても同じような結果になるのでしょうか。これまで同様に100セット学習させました。以下がその対戦成績になります。

はじめは、やはり先攻の「cross」(×)が勝ち越していましたが、次第に低下し、引き分けばかりになりました。学習状況を確認してみましょう。

■学習済み局面数の推移:

これまでの学習と同様の推移ですね。

■各局面において、重みが「0」となった局面の数:

「pattern-1」が「先攻と後攻を個別に学習したもの」で、「pattern-2」が「先攻と後攻を同時に学習したもの」です。どちらも似たようなものですが、先攻と後攻を同時に学習した方が、「重み「0」を数多く持つ局面」の数が多いようです。お互い鋭い指し手をするようになって、勝敗が付くケースが多かったのかもしれません。

■初手から7手目までの、各手数毎の「重み「0」を持つ局面の数」:

「pattern-1」が「先攻と後攻を個別に学習したもの」で、「pattern-2」が「先攻と後攻を同時に学習したもの」です。どちらも似たようなものですが、先攻と後攻を同時に学習した方が、早い段階(4手目)で、
重み「0」を持つ局面の数が多いです。早い段階で指し手の選択肢を絞り込めています。これも、先程と同様に、お互い鋭い指し手をするようになってきた効果なのかもしれません。

7.最後に

ここまでの内容を見てみて、いかがでしょうか。暗記をするということだけですが、効果はありますよね。また、この実装は、全く普通のパソコンで動きますし、処理時間も大してかかりませんでした。今回のように、暗記すべきパターンが少なくないと適用できませんが、そのような場合は結構使えるのではないでしょうか。

8.おまけ

せっかく学習したので、皆さんの参考に、学習により得られた推奨となる指し手を共有します。

■1手目:

 
先攻と後攻を個別に学習
先攻と後攻を同時に学習
重み [1282, 48, 16, 46, 4948, 82, 154, 369, 922] [284, 140, 362, 112, 573, 251, 268, 38, 387]
可視化

中央がいいようです。ちなみに、Wikipedia( https://ja.wikipedia.org/wiki/%E4%B8%89%E7%9B%AE%E4%B8%A6%E3%81%B9 )によると、次のように書かれていました。

前述の通り9カ所のどこに打っても、相手も最善を尽くしてきた場合には引き分けになってしまう。
しかし、もし相手のミスを狙うなら、角に打つのが得策だろう。

■2手目:

先攻が中央にくるので、後攻はどこがいいのでしょうか。

 
先攻と後攻を個別に学習
先攻と後攻を同時に学習
重み [19, 3, 20, 17, 1, 0, 387, 12, 80] [42, 0, 73, 0, 1, 0, 39, 0, 35]
可視化

後攻は、四隅がいいようですね。これは、Wipipedia( https://ja.wikipedia.org/wiki/%E4%B8%89%E7%9B%AE%E4%B8%A6%E3%81%B9 )とも意見が合いました。

先手が中心、角、辺のどれに打ってきたかによって変わる。
ここでは先手が○、後手が×である。後手は×で示した位置以外に打つと、負けが決定してしまう。

お問い合わせ先

執筆者プロフィール

takos
takostdi デジタルイノベーション技術部
入社以来、C/S型の業務システム開発に従事してきました。ここ数年は、SalesforceやOutSystemsなどの製品や、スクラム開発手法に取り組み、現在のテーマは、DeepLearning/機械学習です。
Pocket

関連記事