後手でも勝てるケース

　去年の記事の最後に追記しましたが、アプリの設定を「やばい」（＝最強）にしていても後手で人間が勝てるケース（豆４つ）を見つけてしまいました。適当に遊んでいて見つけたぐらいですから、アプリのユーザーの中にも後手で勝てた人はいると思います。でもアプリのAIは完全に読み切っている訳では無いのでこういうことがあっても不思議はないと思っていて、豆４つのケースでは先手必勝の結論に変わりはないと思っています。１１手読みでは必勝手順を間違えてしまうことがあるということだと思います。
　単純な評価関数（勝ちか負けかだけを判断）でも十分強いだろうと思っていましたが、評価関数を工夫した方がいいのかもしれません。

途中の局面からなら読み切れる

　たまたま後手で勝つことが出来た時その手順を再現出来なくて困っていたのですが、記憶を頼りに途中まで局面を進めていって、その途中の局面からプログラムで先読みさせれば勝ち（将棋で言う「詰み」）を読み切れる場合があります。そういうやり方で後手での勝ち手順を確認したので、一例として紹介したいと思います。
　マンカラの棋譜をどのように表現するか、標準的なものは無いと思うので、ここでは以下の表の番号に従って、指し手を表現します。アプリの画面と対比し易いように上側（Upper）を先手、下側（Lower）を後手にして、それぞれUとLの次に場所を表す数字を付加して棋譜を表現しました。

後手勝ちの棋譜の一例（５１手でゲーム終了、後手の勝ち）

※指し手の最後にピッタリなら*、横取りなら!を付加しています。 ※アプリのバージョン 1.2.4

※画像はゲーム開始から、U3*（ピッタリ）,U6と２手進んだ局面です。

　アプリは評価値が同じ場合、乱数選択させているので上記の手順通りにならないケースもありますが、２１手目ぐらいまでは毎回同じようです。そして、そこまでいけば形勢はかなり後手有利なので、序盤を上の手順通りなぞれば後手でAIに勝つことが出来ます。

負ける原因は評価関数？読みの深さ？

　アプリが先手で負ける原因は、序盤の局面評価が単純過ぎる所為と言えますが、勝ち、負けの判定をするには今の評価関数で間違い無いので、読みが浅いのが原因とも言えます。アプリの評価関数はアプリの紹介ページにも書いていますが、
　（先手の貯蔵所に溜まった豆の数 - 後手の貯蔵所に溜まった豆の数）
となっていて、単にその局面でどちらの豆が多いかしか評価していません。１１手先を読んでその時点でどちらの豆が多いかを評価値としています。これは先読みの手数以内にゲームが終了すれば正確なものになりますが、ゲーム途中の局面の形勢判断には向いていません。マンカラカラハのルールではゲーム終了時に自陣に残った豆を全て自分の貯蔵所に入れて数えますが、ゲームが終わっていないのに貯蔵所の豆の数で優劣を判定するのはあまり良くありません。ただ１１手も先を読んでいるので、終盤は十分強いので、そういう仕様にしていました。
　将棋で言えば詰み判定の時に使用する評価関数のようなものなので、序盤の形勢判断に使用すると悪手を選ぶケースがあります。

悪手を特定する

　初手からの必勝手順を読み切るのは今までの記事で書いてきたように時間がかかりますが、上で説明したようにある程度指し手を進めた局面から先読み、ダメなら元に戻して他の手を試すっていう方法を繰り返して徐々に序盤に遡れば、どの手が悪手だったかある程度特定出来ます。将棋と違って一局面で選べる手は最大６手しか無いのでそういうやり方が可能です。
　自分なりに調べたところ以下の局面でAIがU4（上記の棋譜の10手目、豆が７個あるところ）と指す手が悪手のようです。

※上の局面は二人対戦モードにして上記の表の棋譜を再現した途中の画像です。

　上の局面でAIは11手先を読んでU4（豆が７つあるところ）が好手だと判断するのですが、パッと見だとU5やU1を選べば下段のL1の場所にある相手の豆を１個横取り出来るのでその手の方が良さそうに思えます。実際その後の変化を調べてみると、この局面ではU5を選んで相手のL1の豆を一個横取りするのが最善手のようです。
　今の評価関数のまま何手先まで読めばその最善手が選ばれるか調べてみました。

% ./mancala.out                                      
2,5,0,2,7,1,0,6,1,2,8,0,7,7,
=== result = 6, 1, i = 0
=== result = 4, 4, i = 1
=== result = 5, 4, i = 2
=== result = 6, 4, i = 3
=== result = 7, 4, i = 4
=== result = 10, 4, i = 5
=== result = 9, 4, i = 6
=== result = 10, 4, i = 7
=== result = 11, 4, i = 8
=== result = 10, 4, i = 9
=== result = 11, 4, i = 10
=== result = 12, 4, i = 11
=== result = 10, 4, i = 12
=== result = 10, 4, i = 13
=== result = 9, 4, i = 14
=== result = 8, 5, i = 15
=== result = 11, 5, i = 16
=== result = 12, 5, i = 17
=== result = 14, 5, i = 18
=== result = 12, 5, i = 19
=== result = 19, 5, i = 20

　以前の記事に書きましたが、AI（先読みメソッド）の戻り値は、評価値, 指し手となっていてiは読みの深さを表すループカウンターです（i=0は一手読み）。
　一手読み（i=0）だと当然相手の豆を横取り出来る手（U1）を選びますが、U1を選ぶとその直後に相手にU2を指されて豆３個を横取りされます。そのため２手読み以上ではずっとU4を最善手と判定しますが、１６手読みの時（i=15）にU5が最善手と変わります。１６手読んでようやく最善手に辿り着くようです。でもこの辺りの読みの深さは一手読みを深くする毎に消費時間も指数関数的に増大します。２０手先まで読むのにハイスペックPC（Apple M1 Pro搭載のM1 MacBook Pro 14インチ）でも一晩掛かりますし、１６手読みでも２分ぐらいかかりますので、スマホアプリにそのまま適用するわけにはいきません。やはり今より強くするには読みの深さより、評価関数を修正するべきでしょう。
　あるいは時間をかけて全ての手を読んで序盤だけを定石データ化するのがいいと思いますが、今までの記事で書いているように普通のやり方で全ての手を読み切るには何ヶ月あるいは何年も掛かると思います。それか既にどこかにマンカラの定石データがあるのかも知れませんが、どうなんでしょう？

他のアプリにも後手で勝てるか

　「マンカラは後手でも勝てるか？」の記事で対戦成績を紹介したように、マンカラナッツは後手で他のアプリに何度も勝っていますが、先手で他のアプリには負けていませんでした。その時の棋譜を保存しているわけではないのですが、新しいアプリも増えているので改めて確認してみると、「マンカラは後手でも勝てるか？」の記事で対戦させたアプリは最強レベルにすると初手にU3かU6を選ぶものが多く、マンカラナッツが後手で勝っていたのは相手のAIが初手にU6を選んだ場合がほとんどで、初手にU3（ピッタリ）を選ばれた場合には、後手を持って勝つ手順を見つけることは出来ませんでした。

現状は粘りが効かない

　現状のマンカラナッツはもう一つ問題があって、先読みの過程で最善手を続けても負けることが確定すると１個差での負けでも１０個差の負けでも同じ負けと判断して、時間短縮のために先読みを省略していました。その結果もう少し僅差の負けに持ち込める場合でも大差の負けを喫するケースがあります。これは元々マンカラというゲームが先手必勝なのか後手必勝なのかを確認するために作ったアプリだったのでこういう仕様にしていたのですが、この点も改善する必要があると思っていました。
　アプリのユーザーの中には、終盤にアプリが自分の豆を取られる手を選んできて、「このアプリおかしい」、「バグってる」と思った方もいると思いますが、アプリの右上に表示している絵文字による勝ち負けの判定自体は間違っていないはずです。
　でもこのままだと誤解され易いので、探索時に勝ちが確定した時に評価値を最大値（先手勝ち）あるいは最小値（後手勝ち）に置き換えていたのを、評価値と勝ち負け判定の数値は別々に返すように局面の先読みメソッドを修正しました（バージョン1.3.0以降）。これでゲーム終了まで最善を尽くす（最大個数差で勝つ、あるいは最小個数差で負ける）ようになったはずです。

評価関数は今のまま？

　評価関数についてピッタリや横取りが出来る局面をプラス評価（＝相手のピッタリや横取りを防ぐマイナス評価）することなど局面評価の材料をちょっと考えてみましたが、なかなか良い案が思いつきません。「連続して着手出来る手（ピッタリ）がなるべく多い形（自分の貯蔵所から１個、２個、３個…と並ぶ形）を理想として、それとのズレを評価値にしてみてはどうか」なんて考えてみましたが、横取りされることも考慮しなければならないので静的評価のやり方がよく分かりません。こういう時こそ機械学習を使ってみたい気もしますが、将棋ほど複雑じゃないので今の評価関数で十分な気もするので、取り敢えず今の評価関数が
　（先手の貯蔵所に溜まった豆の数 - 後手の貯蔵所に溜まった豆の数）
となっているところを、
　（先手の自陣の全ての豆の数 - 後手の自陣の全ての豆の数）
に変更して試してみました。
　既に書きましたが、マンカラカラハのルールではゲーム終了時に自陣に残った豆を全て自分の貯蔵所に入れて数えますので、評価関数内で貯蔵所に溜まった豆の数だけを数えるのではなく、ゲーム終了時と同じように自陣の豆全てを数えてその数が勝っている方を有利と考えてみれば何か変化があるかもと思ってやってみました。
　そうすると上で紹介した局面にはなりませんが、すぐに人間が後手で勝てる他の手順を見つけることが出来ました。将棋の駒得だけを考慮する評価関数のように、自陣に豆を溜め込んで中盤で相手に豆を大量に横取りされる感じです。ということでこれはすぐにボツにしましたが、序盤だけこの評価関数を使って終盤は今使用している評価関数を使う方法もアリかもしれません。

読みを一手深くしてみる

　今度は「やばい」モードの時だけ試しに読みを一手深くしてみました（バージョン1.3.0以降）。古いスマホだとちょっと待たされる感じにはなりましたが、上で説明した悪手を指す局面になる前に着手を変えてきました。しばらくこれで様子を見ようと思います。
　当面はバージョン1.3.0をベータ版のまま公開しておきますので違いを試すことも出来ます。スマホからの場合はアプリのページからダウンロード可能です。