温故知新(ProbCut)

温故知新シリーズを期待している人が居るとは思いませんでした。

この分野個人的にはかなり後発なので遅れて勉強する自分の学習メモ程度に考えていましたし,先に始めた人には当たり前のことばかりなんだろうと思ってました。

また,私より後発の新参者は古典への興味は薄いと想像していました。

 

  

まぁ,休日に諸事情で拘束されましたので印刷したpdfをじっくり読む機会を得ました。

今年は色々大変ですが愚痴っても仕方ないので別視点で好機と捉えます。

ひとつベタですが紹介しておきます。

 

読んでたのはBuroさんのProbCutの原著です。Buroさん現在アルバータ大学の教授だそうです。

1994年の学位論文(ドイツ語らしい)の後にICCA Journalに英語で投稿されたもので以下のリンク先に詳しく書かれています。pdfへのリンクもあります。

ProbCut - Chessprogramming wiki

Michael Buro's Homepage

 

恐らくLOGISTELLO(ロジステロ)と言うとピンと来る人が多いと思います。

ICCAに投稿されていますがチェスではなくオセロのプログラムです。アルゴリズム自体が汎用であるために問題ないのだろうと個人的に解釈してますが,ICCA自体も2000年からICGA(Computer ChessからComputer Game)と変貌しているくらいに他のゲームも取り上げられるようになったみたいです。

 

ProbCutはαβ探索に前向き枝狩りを入れる手法のひとつで,浅い探索と深い探索に強い線形相関と統計的分布があることを前提に浅い探索値で枝狩りを行うものです。同論文中には前提として置いたモデルからオセロを題材として計測し調整したパラメータなどが解説してあります。もちろん例によって疑似コードによるアルゴリズム解説もあります。(上記Wikiにも)

あー,論文に合わせて線形と上記に書きましたが多くの予想通り傾き1切片0ですので実は実装は非常に簡単な数式です。

 

今となっては昔話ですがオセロも当時劇的に強くなったんだろうと思います。

もちろん,直後からチェスや将棋にすぐ応用され,今や当然の技術のひとつとして馴染んでいるわけです。Multi–ProbCutと言うのが発展した今の実装です。

統計データとって真面目に分析する論文のお手本としては一読していいと思います。