p20181020

[bug#0001] オセロのバグとの闘いの記録

• (by K, 2018.10.20)

(0)

• どんなバグが出て、それをどうやって解決したかをメモしておけば、きっと何かの役に立つ日が来るかもしれない。
• ということでこのシリーズを始めてみる。

(1)

• blaライブラリ（→p20181024a）にマウスイベントを取得する拡張を付けた。そのサンプルとしてオセロゲームを作ってみた。最初のバージョンのAIはランダム打ちだった。まあどうしようもなく弱かったけど、とりあえず当初の目的は達せられた。
• そののち、ランダム版だけではあまりにつまらないと思い、また川合はその程度のオセロしか作れないとか思われるのもいやだったので、すこしAIを賢くした。とはいえ1手も読まないが、隅などにおける時はそこを優先するようにした程度である。
• ここまでは順調だった。
• それができてみると、やっぱりオセロの醍醐味は終盤の完全読み切りルーチンだよなということになり（註：誰もそんなことは言っていないが、自分で勝手にそう思った）、それでどうやって作ろうかなと思っていたらビットボードというデータ構造を発見し、おおなるほどこれはおもしろそうだし速くなりそうだと思った。ということでビットボードでネガマックス法を使って実装してみたところ・・・動くには動くのだけど、なんだか挙動が微妙だ。おそらくバグっている。
• そしてこのバグが全然取れない。もうこの件で数時間は悩んでいる気がする。我ながら情けない。

(2)

• 状況を整理しよう。まずなぜバグっていると思ったか。
• それはAIのスコアが、第44手目で-30なのに、第46手目では-34とかになったからだ。これはおかしい。全局面を読み切って相手が最良の手を打ってもこれだけの点数にはなる、ということで自分の手を選んでいるはずなのに、手が進むにつれてスコアが後退するとは何事か？（まあ「全局面」とはいってもネガマックス法で枝刈りはしているが、結果は変わらないはず）。
• じゃあどこが疑わしいか。・・・正直ほとんどが疑わしい。だってビットボードでオセロAIを書いてみたのは今回が初めてだし、ネガアルファ法も初めて使った（今まではアルファベータ法だった）。
• そして実験として、ネガアルファ法でアルファもベータも使わずに、常に-99から+99の範囲で全局面を枝刈りせずに探索させると、バグと思われる上記の挙動は示さなくなった。ということは、ビットボードなどのコア部分は間違ってはいないということなんだろうか。そうかもしれないし、そうじゃないかもしれない。まだわからない。

(3)

• とりあえず現時点で言える教訓としては、AIのスコアを面白半分でデバッグ表示してみたのは良かった（これが上昇すると、自分が最善手を打っていないことがわかるので、面白半分で表示してみた）。もし表示させていなかったら、外見としては結構それっぽく動いているのでバグに気づかなかっただろう。
• そういえば、プログラムの内部状態を確認のためにちょろっと表示すると、思わぬバグを発見することが最近何件か続いている気がする。今の自分の実力からすれば、バグはその存在さえ確認できれば最終的には全部直せているので、だからこのようなデバッグ表示はとても有益であろう。今後も心掛けていきたい。

(4)

• さっきはビットボードがうまく動いていないせいなのではないかと思って簡単なテストを書いて試してみたけど、怪しい挙動は見つけられなかった。・・・うーん、こういうテストはかなりつまらないなあ。正しそうなところを確認するのではなく、明らかに間違っているところがどういう過程で間違えたのかをどんどん攻めるべきだ。

(5)

#0:0033300020233000223333302332333023322223232222222233332222222222:c=3
[i=01 sc=-34(-34)] [i=09 sc=-34(-36)] [i=31 sc=-32(-32)] i=31

#1:0033320020232000223233302322333322322233232223222233332222222222:c=3
[i=01 sc=-32(-32)] [i=06 sc=-32(-32)] [i=09 sc=-26(-26)] [i=13 sc=-26(-34)] i=13

#2:0033320020233300223222222322332222322232232223222233332222222222:c=3
[i=01 sc=-24(-24)] [i=06 sc=-20(-20)] [i=09 sc=-18(-18)] [i=14 sc=-18(-36)] [i=15 sc=-18(-22)] i=14

#3:0033320220233320223222322322233222322232232223222233332222222222:c=3
[i=06 sc=-42(-42)] [i=09 sc=-30(-30)] [i=15 sc=-30(-36)] i=09

• scの値はバグっているネガアルファ法ルーチンが出したもの。カッコ内はalphaやbetaをあえて使わない改造ネガアルファで出した参考値。
  • バグっているsc値を見ると、#2で-18の手を選んだのだから、#3以降では-18以上の手が必ず1つはあるべきなのに、#3はそのようになってない。

• [脱線] ビットボードではないボードの値は、0,2,3ではなく0,1,2のほうが自然だった。もし0,1,2方式なら、自分のビットボードはボードのbit0を取り出して並べるだけでいいし、相手のビットボードはbit1を取り出して並べるだけでいいのだから（もしくはその逆）。

(6)

• ベータによる枝刈りはするけど、alphaは渡された値を無視して-99に初期化することにする。アルゴリズムから考えたら、alphaの初期値が-infではないことが良くわからなかったし。

  #0:0033333300333323033333330222322300233323003333330322223333333333:c=2
  [i=08 sc=-28(-28)] [i=09 sc=-30(-30)] [i=33 sc=-26(-26)] [i=48 sc=-30(-34)] i=33
  #1:0033333300333323333333330322322302333323002333330322223333333333:c=2
  [i=08 sc=-34(-34)] [i=09 sc=-34(-38)] [i=24 sc=-26(-26)] [i=41 sc=-30(-30)] [i=48 sc=-28(-30)] i=24
  #2:0033333300333323333333332322322303333323033333330332223333333333:c=2
  [i=08 sc=-16(-16)] [i=09 sc=-18(-26)] [i=32 sc=-04(-04)] [i=40 sc=-22(-22)] [i=48 sc=-28(-28)] i=32
  #3:0033333300333323333333333332322333222223333333330332223333333333:c=2
  [i=01 sc=-04(-04)] [i=08 sc=-14(-16)] [i=09 sc=-12(-20)] [i=48 sc=-18(-18)] i=01
  #4:3333333300233323333233333332222333222223333333330332223333333333:c=2
  [i=08 sc=-16(-16)] [i=09 sc=-26(-26)] [i=48 sc=-04(-04)] i=48

• おお、これはまあまあいいんじゃないか？もちろん枝刈り無しの改造ネガアルファとは違う値もあるが、それは興味のない値にしか出ないから問題ないと思う。
• そうするとこのネガアルファでは、アルファを引数に渡す必要がよくわからない。そんなものはいらないんじゃないかな？
• ということは、wikipediaに載っているやつはバグ？（以下はwikipedia版）
  • https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%82%BF%E6%B3%95 より

    function alphabeta(node, depth, α, β)
        if node が終端ノード or depth = 0
            return node の評価値
        foreach child of node
            α := max(α, -alphabeta(child, depth-1, -β, -α))
            if α >= β
                return α // カット
        return α

• よし、バグは解決！
  • 結局10/19(金)の19時くらいにおかしいと思いだして、10/20(土)の23時くらいまでかかったので、28時間も悩まされたことになる（もちろんその間ずっとデバッグをしていたわけではないけど、きっと頭の片隅では脳内デバッグがバックグラウンドで走っていたと思われる）。

(7)

• 今回の教訓。
• 権威（この場合はwikipedia）を信じない。書いてあることをよく読んで理解して考えてみる。
• どこが正しくてどこが正しくないかわからないとき、あちこちテストをして「よしここは正しい」を積み上げていく方法は結構しんどい。間違いを突き詰めるほうが私にはしんどくない。
• なんでも試しに表示させてみるのはいい。正確なテストを書くのは大変だけど、表示させてみるくらいなら簡単だから。・・・なんにせよ、バグに気づかなければ始まらない。

こめんと欄