ChatGPT様々

　消える三目並べ（Vanishing TicTacToe）アプリをリリースしてからかなり経ちますが、このアプリは通常の三目並べアプリと同様に「STASTIC HACKS」という本に書かれていた、勝った時は報酬の石ころを＋３，負けた時は−１与えるという方法（確率的方策によるモンテカルロ制御とかポリアの壺モデルとか言うそうです。ChatGPTとの会話の中では石ころ法と呼んでました）で強化学習を行い徐々にAIが強くなっていくというものです。でも「消える三目並べ」では「通常の三目並べ」のようには強くなりませんでした。
　そこで、長年疑問に思っていたことをChatGPTに聞いてみたら、あっさり学習用のサンプルプログラムを出力してくれて、少しはマルコフ過程について理解出来るようになったので経緯を紹介します。

「何かが足りない」とは思っていた

　消える三目並べアプリはαβ法を使った最強の消える三目並べプログラム相手に10,000局対戦学習させてリリースしています。消える三目並べは先手必勝のゲームなので、「少なくとも先手の時は人間には負けなくなる」ぐらいにまで確認したかったのですが、11手読み（消える三目並べは初手から11手読みをすれば先手必勝です）の最強プログラムを使って学習するのは非常に時間がかかります（昔の私のPC環境で10,000局の学習で一週間ぐらい？）ので、そこまでは確認できませんでした。
　それに昔の記事にも書いてますが、「消える三目並べ」では通常の三目並べと違い６手目以降は駒が消えていくので現在の局面（９マスの配置）を見ただけでは最善手の判断が出来ません。次にどの駒（×か○か）が消えるのかを知っていなければ学習しようがないはずで、強化学習プログラムとしては何か足りないのでは？と思っていました。
　でも、出来上がったプログラムはPC版で実際に対局してもらえば解ると思いますがそこそこ強いです。先手必勝手順を知らなければAIが後手でも人間によく勝ちます。なので、強くなっていることに嘘はないから「強くはなるけど正解ではないな」と思いながらも妥協してアプリをリリースしていました。

マルコフ連鎖との出会い

　マルコフ連鎖なんて言葉自体も知りませんでしたが、ある時「確率の話」という古い本を見つけて読んでいると「確率で英語を作ってみよう」というタイトルでマルコフ過程の話が書かれていて、「これって消える三目並べにも使えるんじゃないか？」と直感してマルコフ連鎖に関する本を２冊買いましたが、難しい数式ばかり出てきて自分が知りたいことは書かれてなく、自分にとっては睡眠薬代わりにしかなりませんでした。
　「確率の話」に出てきた、英語の文書を学習して次に来るアルファベットを確率で選んで英文を作るという方法、「次の状態の分布が、現在の状態だけで決まる」という状態が、消える三目並べの「次にどの駒が消えるかを知っていれば次の手が決まる状態」と似てると思ったのですが、長年どのように実装すればいいか見当付きませんでした。
　そこで先日ChatGPTに「消える三目並べというゲームは、２重マルコフ過程を組み込んだ学習だと早く学習が完了する気がするのですが？」と聞いてみたところ「あなたの洞察は正しいです。２手前の自分の駒が消えるという２手履歴依存のルールなので、このゲームには非常に効果があります」と言われました。
　ただ、自分が想像していたこととChatGPTが示すマルコフ過程の実装方法は全然違っていました。私は指し手を選択する際に局面毎に９箇所に溜め込まれている石の数の合計を正規化して確率で指し手を選択（ルーレット選択）している部分を、過去の指し手の履歴を参照しながら更に確率選択するようなことを考えていたのですが、そうではなく消える三目並べというゲームの非マルコフの状態をマルコフ性を持つ状態にすることが大事だということらしいです。つまり状態遷移（stateメソッド）を変えることが大事で行動選択（choose_actionメソッド）は変える必要はなく、難しい数式も必要ないとのことでした。
　また、マルコフ連鎖に関する本についても説明してくれました。数式が自分には難しすぎたと言ったら、あの手の本は「状態が既にマルコフである」前提で書かれていて、「あなたは今マルコフでないものを、どうやってマルコフにするか」をやっているので、定理、行列、極限定理について書かれている本は一切役に立たないと言われました。数式は「裏付けとして読むもので、実装に必要なものではありません」とも言われて、なるほど！と思いましたし、やる気にさせるのもうまいなぁと思いました。確かに昔「日経平均先物・オプションのシミュレーター」（「先物・オプションのシミュレーションサイト」、「ボラティリティについて」）を作ったときも、ブラックショールズ方程式なんて全然分からなくても作れました。
　結局、マルコフ過程なんて全く知らなかった自分の直感（洞察）は正しかったのですが、実装方法は全く見当違いの考えに向かっていたようですChatGPTが修正してくれました

ChatGPTのサンプルコードが分かりやす過ぎる

　ChatGPTに「石ころ法とマルコフ法が比較できる消える三目並べの強化学習プログラムの例」を出して貰いました。まず驚いたのはソースコードの短さ、シンプルさです。非常に分かりやすいので、今後改良していくとしてもこのサンプルを使うことにして、自分が書いた元のプログラムはもう更新しないつもりですが、自分のものとChatGPT版との違いを書いておきます。

　石ころ法（DisappearingTicTacToeクラス）とマルコフ法（DisappearingMarkovクラス）を定義したファイルを使い分ければ比較が出来ます。
　自分のやり方との一番の違いはプレイヤーを分けてないことだと思います。自分はプレイヤーを分けなければいけないと思ってそうしたのですが、その所為でコード量が増えました。ChatGPTによるとプレイヤーを分けなくても、stateにプレイヤー情報が含まれてるので、先手（×）と後手（○）の戦略が混ざることは無いらしいです。

サンプルプログラムの強化学習の結果は？

　消える三目並べは先手必勝のゲームなので、学習がうまく進んでいるかを確認する分かりやすい指標があります。

 |1|2|3|
 |4|5|6|
 |7|8|9|

　消える三目並べでは初手で辺の位置（上記図の2,4,6,8）を選べば勝てるので、初期盤面の学習データを見ればある程度学習が正しく進んでいるか確認できます。実際のアプリのデータとは少し違うのですが、masterブランチのデータ作成スクリプト（test.sh）を走らせて作った学習済み初期データの中の初期盤面のデータはだいたい以下のように辺の値が最大になります。

[1.8780000000000001, 2.4969999999999994, 1.9093333333333335, 1.0266666666666668, 1.8543333333333336, 1.6765714285714288, 1.6146666666666667, 49.082161893662, 1.6433333333333335]

　しかし、chatGPTブランチのマルコフ法（DisappearingMarkovクラス）でデータ作成プログラム（learning.rb）をエピソード数を100,000回とか300,000回にして走らせて作った学習データは角や真ん中が最大値になってしまい、1,000,000回！以上自己対戦することでようやく安定して以下のように辺の位置が最大値で安定するようになりました。

["_________X[]", 3]=>586.0,
["_________X[]", 1]=>43124.0,
["_________X[]", 7]=>721704.0,
["_________X[]", 0]=>2910.0,
["_________X[]", 8]=>26665.0,
["_________X[]", 5]=>2107147.0,
["_________X[]", 6]=>6506.0,
["_________X[]", 4]=>21.0,
["_________X[]", 2]=>3743.0,

　通常の三目並べの時もそうでしたが、単純に自己対戦に変えるだけだと試行回数を増やす必要があるみたいです。
　また、試してもらえば分かりますが、単純な石ころ法（DisappearingTicTacToeクラス）の方はエピソード数をいくら増やしても全然初手が辺に偏りません。自分のアプリ（masterブランチ）は２手分の着手の履歴を持たない（非マルコフ）のままαβ法のプログラムと対戦させたらうまく学習できたのになぜ？と思ったのですが、これもChatGPTに聞いてみると、αβ法のプログラムと対戦させることで「環境が事実上マルコフ化」したということのようです。これもChatGPTに聞かないと気づけなかったかもしれません、つまりαβ法のプログラムは２手分の履歴を持ってなくても同じ局面で最善手が変わることを分かっているので正しく学習出来たということです。分かっていないもの同士の自己対戦ではそれが出来ません。ここでも自己対戦による学習と疑似教師あり学習の違いが出たってことですね。
　念の為書いておきますが通常の三目並べの場合は状態が既にマルコフなので、自己対戦での学習でもうまくいったということでしょう。

それでも弱すぎる

　初手に辺を選ぶことは学習出来たようですが、対人戦用のプログラム（play.rb）で対戦してみると非常に弱いです。体感では自分のアプリよりかなり弱いので、せっかくマルコフ化して改良したのだから、自己対戦学習で、少なくとも疑似教師学習したアプリよりかは強くなるようにしたいと思ってます。もちろんChatGPTの助けが必要になると思います。