« Swingでオセロを作成中 | メイン | Mac間のデータ移行 »

 αβ探索だけのオセロの思考ルーチン作成

前回作りかけだったオセロの思考ルーチンの核として、とりあえず、最も基本的なゲーム木の探索アルゴリズムであるαβ探索を実装してみた。
正確に書くと、前回もαβ探索をしていたつもりだったのだが、バグが取れず、うまく動かなかった。

今日、このページのコードのような形に書き直したら、一発できちんと動いた。
すると、それだけで、特にオセロが得意でない筆者は全くコンピューターに勝てなくなってしまった。

Swingオセロの起動ページ

ソースコード
OthelloApplet.java
State.java
GameTreeNode.java
Evaluator.java


単純なゲーム木の探索ではまともな結果は得られないと思っていたので、局面の良し悪しを決める評価関数をうまく作る取り組みが次に必要だと覚悟していたのだが、今回の目的は強いプログラムを作ることではなくきちんと動く思考ルーチンを作ることであり、筆者にはこれ以上コンピューターの手の良し悪しが分からないので、これで良しとする。

一応、この後評価関数の改良として取り組む予定だった内容をメモしておく。今は隅が取れてたら点数が高いだけの評価関数である。


  • 辺の評価
    "□□●●●●□□"や"□●●●●●●□"は良くて"□●●●●●□□"や"□□□○□□●□"は良くない(最後のは黒の左側に白を置かれると必ず隅を取られる)とかいうやつである。
    辺の攻防で優勢になることを狙う思考ルーチンにしたかったので、辺の状態について細かく評価値を設定したかったが、計算式で書くと結構複雑なので、今回は見送った。
    辺の状態は3^8=6561種類しかないので、事前にテーブル化しておくことが可能であり、計算するのに時間がかからないのである。
  • 序盤と終盤とで思考ルーチンを分ける
    終盤は勝ち負けを読み切ればいいだけなので、細かい評価は要らないのである。
  • 着手可能な選択肢が少なければ評価を下げる
    強い人は相手にパスさせようとすると聞いたような気がする。
  • 「偶数理論」
    よく調べてないが、最後の石を打てると有利という発想によるもので、自分の手番で残りマス数が偶数だったら評価を下げるとか、連続する空きスペースが偶数だったら評価を下げるとかいうことではないかと推測している。
  • 「開放度理論」
    周囲に空きスペースが多い石は、ひっくり返される確率が高いので、評価を下げるという考え方だったと思う。
  • 乱数を加える
    どうせそんなに強くならないだろうから、たまたまいい手を打つ確率が0でないように、おまじないを掛けようと思った。
  • コンピューター同士の対戦
    評価関数の良し悪しを決める方法は、2つの評価関数を対戦させることしか思い付かない。
    乱数の要素も加えて、いくつかの変化可能なパラメーターを用意して、何通りかのパラメーターのセットを用意して、総当たりで何回か(先後入れ替え含め)対戦させて、弱かったセットを捨てて、強かったセットに乱数を少し加えたものを新たな候補として用意し、また総当たりさせる、というのを繰り返していいパラメーターを探す、GA的な方法を考えた。
  • 展開しながらの探索中に全てのノードを残さない
    あまり探索木を広げるとメモリ不足で落ちるので、今はノード数がある程度に達したら計算を打ち切っているが、全体的に評価の悪い部分木は取り払うとか、途中のノードは評価値だけ残して盤面は消すとかして、メモリを節約する方が良い。
  • 未評価の盤面の扱い
    今は評価値の初期値を0にしてるので、評価した局面の評価値が全て負の値だと、反復深化で読み直す時に未評価の手を優先してしまう、怪しい動作になっている。

先々月の話だが、米長永世棋聖が将棋ソフトに負けてしまった。
このブログでも以前に書いたが、6年以上前には既に将棋連盟から警戒されていたし、そのちょっと後に、渡辺竜王がボナンザといい勝負をしたとか、女流棋士が負けたとか、将棋倶楽部24でレート3300(過去にR3000に達したdcsyhiというハンドルは実は羽生さんなんじゃないかと噂されていた)とかいう話も聞いていたので、それから何年か経った今年の正月、米長さんは勝てないだろうなとは思っており、驚きはしなかった。
来年、現役棋士数人が対決するそうだが、何せもはやコンピューターは終盤が完璧で、序中盤でも米長さん相手に大きくし損ねなかったのだから、もう勝てないと思う。将棋ソフトの癖というのも、複数のソフトの多数決を取るシステムによって、大方解消されてしまった。人間が勝つには、序中盤で完封するしか無いが、中盤は本番一発勝負でミスをすると負けるので、作戦としては、誰にも知られずに、将棋ソフトに確実に搭載されている有名な定跡を必敗にする順を開発するしかないのではないか。定跡は日々進歩していると言っても、将棋の歴史を考えると、たった1年ではその可能性は低いし、もしそれで勝っても、誰もそのやり方が長続きするとは思わないだろう。
大体、こういう結果が定量的にはっきりしている計算はコンピューターの得意分野なのである。計算機と暗算の競争をしているようなものであり、計算機の性能はまだ物理的にもアルゴリズム的にも向上する余地があるのだから、人間がいつか負けるのは当然である。詰将棋では既にパソコンが検算に使われている。初期の将棋ソフトが弱かったから、コンピューターは人間に勝てないという錯覚をしてしまっただけである。

米長さんが負けたという記事を読んで、筆者がJavaを勉強し始めた時に最初に作ろうとしたのがオセロで、作りかけて放置していたのを思い出したのである。上記のように、強い思考ルーチンを作るには相当アルゴリズムを工夫する必要があるだろうと思っていたのだが、作ってみたら計算速度の威力だけでも強かった。やっぱりこういうのは人間は勝てないのである。人間がアルゴリズムを作って、コンピューターが計算すればいいのである。いくら何でも、コンピューターが自動的にアルゴリズムを作ることができるようになることは、あと100年くらいは起こらないだろう。

将棋ファンとして心配なのは、人間がコンピューターに勝てなくなることにより、将棋が廃れてしまうかどうかである。オセロやチェスは既に人間がコンピューターに勝てなくなったが、やる人が全くいなくなってはいない。コンピューターと対決しない限りは、面白さは変わらないということだろう。むしろ、対局後にコンピューターを使って分析できる手段を得たので、何が悪かったのかと悩んで嫌になることが減り、より楽しめるようになったのではないか。
問題は、この先、定跡の研究までコンピューターがやるようになったら、プロの仕事はコンピューターの計算結果を覚えるだけになってしまうことである。円周率の記憶競争のような対局を、お金を払って見たい人はいないだろう。将棋の全手順の解析は場合の数が多過ぎて半永久的に不可能と言われるが、人間が記憶可能な分量の枝分かれで、相手にどう指されても有利に持ち込める90%必勝手順のようなものは、これから数十年の内にコンピューターによって検索されてしまうような気がする。最強を競うことに意味が無くなるので、プロ棋士は居なくなり、将棋大会も無くなるだろう。筆者のような、ろくに定跡も覚えずに道場で3段くらいで指してる人同士なら関係ないような気もするが、ちょっと上の階級がそんな状態だと、やっぱり自然にやる気を失ってしまうような気がする。

トラックバック

このエントリーのトラックバックURL:
http://ynomura.dip.jp/cgi-bin/mt/mt-tb.cgi/186

コメント投稿フォーム

※投稿されたコメントはオーナーが承認するまで表示されません。


Powered by Movable Type 3.35