以前は面倒なことをやっていた

　前回の続きです。通常の三目並べアプリでは、強化学習がどの程度進んでいるかを確認する際にツリー構造で保持している局面データの中からリーチが掛かっている局面（あと一手で勝てる局面）を探し出し、その局面の報酬データ（石ころ）の分布を見て判断していました。対戦相手がリーチを掛けた局面でどれぐらい阻止できるかによって学習の進捗度合いを判断して、その値を生物の進化に擬えてアメーバから人間までの画像を表示するという面倒なことをしてました。
　今回の消える三目並べでは、履歴データが必要なのでリーチ局面を探すのも大変なので、αβ法のプログラムとの対戦成績を見て学習の進捗度合いを判断することにしました。

まずはQ-Learning版と対戦

　前回の記事から、既存のモンテカルロ版（MC版）を着手履歴を使用しないようにしてQ-Learning版（QL版）も作り、対戦用スクリプトもChatGPTに作ってもらって対戦させてみました。すると、どちらに先手を持たせても1000戦対戦して1000勝0敗でした。後手を持ったどちらかが偶々勝っても良さそうなものですが、何回試しても先手の1000勝0敗の結果です。その対戦内容を確認してみると、お互いに勝ちを何度も逃していてとても強いとは言えない状態なのですが、それでも結果は先手側が1000勝0敗になります。
　こんなことがあり得るのか？とChatGPTに聞いてみたところ「バグっぽく見えるけど理論的に正しいタイプの現象」とのこと。「勝てるけど下手」は強化学習あるある、消える三目並べは特に起きやすい、勝率 ≠ 強さとのことです。最短勝利を学習していないということが原因のようですが、自分にはなかなか理解し難かったです。もっと学習精度を上げれば違ってくるのでしょうけど、1000勝0敗では強くなってるかどうか判断する指標には使えないので、αβ法のプログラムと対戦させることにしました。

※MC版とQL版を対戦させる時はQL版が先手の時に循環手順に入って対局が終わらないケースがあるようです。その際はMC版のgreedyではない方の学習用のメソッド（choose_actionメソッド）を使ってました（ルーレット選択により着手が変わる）。

対戦相手に使うαβ法プログラムの注意事項

　αβ法のプログラムを強化学習に使うには事前に知っておかないと現象を見誤る可能性があるので書いておきます。

1. 後手番では最強ではない
   対戦相手に使用するαβ法のプログラムは勝ち・負け・引き分け（+9, -9, 0）の三値だけの評価関数なので、先手の時はまさに最強プログラムですが、後手の時は勝てないことを読み切ってしまってどの手を選んでも負けと判断して結局最初に見つけた着手可能な手を選んでしまいます。負けを遅らせる手、粘る手を選べません。だから後手番では最善手を選べないので弱いです。

2. 循環手順を避ける必要がある
   消える三目並べでは、先手側が必勝手順を知らない段階（学習できていない段階）に同じパターンの繰り返しになることがあります。ここで使ってるαβ法のプログラムは循環手順（千日手）を避けるようになってるはずなので、QL版とMC版を対戦させる時は注意が必要です。消える三目並べで循環手順に陥るケースは、先手番が勝てるのに勝ってくれないのが原因です。

※masterブランチで使用しているαβ法のプログラムは上記の後手番時の弱さを補うために特殊な処理をしているのですが、あまりにも場当たり的で良くないと思い、もっと昔に作った消える三目並べが先手必勝であることを確認するためのプログラムを使うことにしました。masterブランチを作った当時は、主役はあくまで強化学習プログラムの方だったので結構いい加減に作ってしまったのですが、今にして思えば教師であるαβ版（後手対策）にもっと力を入れるべきだったのかもしれません。

αβ法との対戦結果

　先手のαβ法には勝てないので後手のαβ法にどの程度勝てるかを学習度合いの指標にしようと思い対戦させた結果、QL版だと100戦して3割ぐらい勝てますが、MC版だと一勝も出来ません。MC版でε減衰方策（ハッシュテーブルの局面キーを増やす）や時間価値付き終局報酬（早く勝つと高報酬、早く負けると厳罰）を取り入れたり、自己対戦の試行回数を１億回まで伸ばしたりしましたが、その学習データを使っても後手番のαβ法に一回も勝てませんでした。αβ法の読みの深さを変えても同じ結果です。MC版を改良するに従って6,7手の短手数で負けてばかりだったのが、だいたい十数手粘るようになり、負けない手、悪手は学習できているようですが、勝ちをもぎ取る一手が選べません。QL版の方はTD誤差で「この一手で価値が跳ね上がる」ことを伝播できるので勝てるようです。また、MC版をルーレット選択（choose_actionメソッド）にすれば当然でしょうけど100局の内6,7局は偶々勝てることがあります。

もう一つの指標

　前回の記事で消える三目並べの学習の進捗度合いを見る簡単な指標として「初手で辺を選ぶ」ことを挙げましたが、もう一つあります。

　上図は先手（×）番で、次に自分の左中断の駒が消えることが分かっていて、自分の着手後に後手（○）に左中断を取られると縦一列揃えられて負けることが分かっていても、先手は自分の駒が邪魔でその場所は選べません。

　しかし先手が着手後に左中断の先手の駒（×）が消えて着手可能になり、後手（○）は勝つことが出来ます。この勝ち方が出来るかどうかが大事です。
　先程QL版はαβ法の後手番に３割勝てていると言いましたが、その勝ち方は前述の後手番αβ法プログラムの評価関数の不備をつく勝ち方ばかりで、この図のような手順を考慮した勝ち方は出来ていません。結局、状態をフラットに見ているだけでは無理なのでしょう。
　しかし、αβ法プログラム相手に学習した自分のアプリはこのタイミングを見計らった勝ち方が出来てます。一般論として言えるかどうか分かりませんが、自己対戦学習より教師データを使う方が強くし易いのかもしれません。

ChatGPTからの衝撃的な言葉

　MC版がαβ法の後手番に勝てないことを愚痴ると、「消える三目並べでは、Hash型MCでは“良い手”までは学べるが、“勝ち切る手”はツリーを持たないと表現できない。」と言われました。次に進むならMCTS（Monte Carlo tree search）がお勧めだそうです。いやいや元々の私の動機は「通常の三目並べなら単純な石ころ法で結構強くなるけど、消える三目並べはそうならない。しかし状態をマルコフ化したら単純な石ころ法で強くなるのでは？」だったので、何じゃそりゃって感じです。「状態をマルコフ化しても、単純な石ころ法（MC）」は本質的には強くならないとも言われました。「もっと早く言ってよ〜」って感じですが、ChatGPTに事前に強くなるかどうかを確認したわけではないので仕方ありません。消える三目並べは「なぜ強くならないかを可視化する題材としては、最高レベル」とも言ってました。
　ハッシュテーブルで学習データを扱うのは楽だなと喜んでいたのですが、結局また昔アプリを作ったときと同じようなこと（学習データをツリー構造で管理）をやる元気はないのでこの辺りで終わりにしようと思います。ChatGPTによると今のプログラムの構造を変えずに最小限で３〜５手の木を足す方法もあるらしいですが、取り敢えずここで終わりにしたいと思います。
　それにしてもChatGPTって何かの営業マンのように次々と提案してくるんですよね

マルコフ化の意義

　以下はChatGPTによるものです。

マルコフ化で得られたもの
    Q-learning が成立した
    初手が学習可能になった
    勝率が明確に改善した
    MCとQLの差が可視化された

つまり：
    「問題は状態ではなく、学習則」

だと切り分けられた。

　上記の言葉に結構納得しました。Q-Learningはマルコフ化必須なんてことも知らなかったし、いろいろ勉強になりました。