HOME →  懐かしのパソコンネタ

■ポケコン版リバーシ（オセロ）をBASIC＋機械語で作ってみた その3
    〜 MiniMax探索　αβ探索の実装 〜

前回記事 (8月14日）にて「もう少し強くしたい」旨の事を書きました。

（その為の準備として、AIシステムをオール機械語にしたのでした）

※強さの目標としては「ヨウコのリバーシ レベル1」以上

その方法として「評価関数をもっと凝ったものにする」とも書きましたが、評価関数は”後回し”にします。

その前に、MiniMax探索を実装させる事にしました。
その探索結果に誤りが無いかの確認を行うには、評価関数がより単純である方が都合が良い（容易い）と思ったからなのです。

先読み設定の深さ（以降「葉」と書く」）に達していなければ、再帰※を行う事により、MiniMaxを実装させました。

※「再帰処理」なんて、言葉は高校の時には知りませんでした。
「MiniMax」という言葉も知りませんでした。
しかし、”言葉は知らず”とも、再帰処理でMiniMaxを作っていたんですけどね・・・
そう云った、作り（再帰）って「”行儀の悪い”作り方かもしれんなぁ」なんて思っていましたが、普通の事だったんですね。


たかだか、MiniMax程度の事を作るのだけでも、BASICと違いアセンブリ言語だと開発に時間が掛かります。
（慣れていない・・・忘れているというのも理由のひとつ）

「とにかく、MiniMaxは出来ました」

3手先読みで、「ヨウコのリバーシ レベル1」と対戦させてみましょう。

「ポケコンリバーシ」のプアな評価関数な3手読み
（※1  テーブル評価とエセ開放度理論のみ）
　　　　　　ｖｓ
「ヨウコのリバーシ レベル1」のちょっと凝った評価関数1手読み
(※1に確定石、辺の評価、ホワイトライン・ブラックラインの評価）

さて、結果はいかに？？

ポケコン版リバーシ先手

47対17で、ポケコン版リバーシの勝ち

棋譜は以下の通り

E6f6F5d6C6e3F3b6E7e8D7c5C4c3G6f7F8g3D8c8C7g8F4b8D3g4G5e2H3h6
H4h5H7g7H8H2g2A8H1g1F1f2B7a7A6b5A5b4A4b3D1a3D2e1A2c2C1b2B1a1

34手に白番(ヨウコのリバーシ)にG7を打たせています。
それに至る内容も「ポケコン版リバーシ」がリードしているように見えます。

（私がオセロに詳しくないので、自信がありません。しかし、とにかく黒に指定打ちを”させました”）

ポケコン版リバーシ後手

25対39で、ポケコン版リバーシの勝ち

棋譜は以下の通り

C4e3F3c5C6f4G4c3D3b5B6b3C2d2F6f5D6e6A3b4A5e2A4f7C1e1F1d7D1c7
E8c8G5g6E7h5H4h3H7d8B8h6H2a6A7f2G3g2G8f8H1g1G7h8B7a2A1a8B2b1

48手G2 (ポケコン版リバーシ）は良いと思います。
辺を取って、着手数を稼ごうとする「ヨウコのリバーシ」に対し、辺への執着が一切ない「ポケコン版リバーシ」
周囲を相手（ヨウコのリバーシ）に囲ませる事により、相手の着手位置を限定させる事に成功している・・・ような気がします。
（私がオセロに詳しくないので、自信がありません。←2回目）

先手・後手の共に「ポケコン版リバーシ」の勝利となりました。

僅か2回の勝負だけで、どっちが強いなんて決めるのは早計だとは思います。
ですが、打ち筋は、「ポケコン版リバーシ」の方が良さそうな気がします。

「しかし、3手先読みでも、かなり遅い！！」

29年前は、これで終わり（ヨシ）にしていました。（MiniMaxの実装だけで満足してしまった）

しかし、今は違います。「”αβ探索”を実装してみます！」

（当時、αβの考えまでは、とても思いつきませんでした。いや、今でも自力で発想する事は、無理だろうな）

※クリックで拡大されます。
（もうチョット分かりやすく書けなかったかなぁ）

なお、「葉」の場合の評価は、その時の石色に合わせて常に評価しているので、（”自分に対する評価”では無い）、上段では必ず符号逆転をさせて、Max値を取得するようにしています。

よって、どの深さ（段）であっても、その石色の評価値になっています。
(NegaMaxとはチト違うのかな？常に最大値を選択する事は同じですが）

さて、MiniMaxが作れてしまえば、αβの実装は簡単です。
上図の様に数値を比較して、その条件に合致すれば処理を終了させてしまえば良いだけなのですから。

αβを実装させてみたので、テストです。
再度、ヨウコのリバーシと対戦させてみて、上述と同じ結果になっていれば誤りは無いはずです。
（無事、対戦結果は同じでした）

そして、どの程度、探索速度が速くなったかを”4手先読み”で比較してみました。
（ストップウォッチと云うのが、なんとも原始的ですね）

結果は(MiniMaxと）同じでも、速度も同じでは意味が無いですからね。

MiniMaxでは、1分6秒かかっていた処理がαβにすると13秒で完了しました。(5.06倍)
MiniMaxでは、   42秒かかっていた処理がαβにすると 8秒で完了しました。(5.14倍）

上記の2測定は中盤時の比較的、着手数の多い状態でした。
（何手目かは記録するのを忘れました。いや、しかし4手先読みのMiniMaxなんて、とても待っていられませんね。当時はソレでヨシとしていたのだから感覚の違いと云うか、隔世の感と云うか・・・）

次回（？）予告

�@　浅い手(深さ1か2以下）で、着手位置を（その深さの）評価順に並び替える。
�A　並び替えた順で、再度、深く先読みをする。

　　　�@と�Aによってαカット・βカットが増えて探索速度の向上が期待される。

�B　終盤（空マス 7程度かな？）からの、「必勝読み」を実装させる。

終盤の必勝読みが空きマス何個からが”実用的”なのかが、楽しみだなぁ。