2014/10/09

10手全滅手順

偶然見つけた

F5D6C4G5E6D3C5B5C6D7
\ABCDEFGH
1++++++++
2++++++++
3+++○++++
4++○○○+++
5+○○○○○○+
6++○○○+++
7+++◇++++
8++++++++

形としても申し分のない満足の一品でございます

2011/02/26

一周年記念

一周年記念ということで閉鎖します。

2010/08/13

13 描かれる軌跡

playok では対戦した全棋譜が掲載されている。そこで、その棋譜から各ユーザーがよく打つ進行を解析するスクリプトを作成した。
http://othello.xrea.jp/playok/
3日間くらいで作った相当な手抜きの状態で、一応動くというレベルの代物なんだが。 JavaScript を多用しているので IE では動かない。IEを使っている人はそろそろ卒業して Chrome や Safari を使うべき。

簡単にサイトの使い方の説明をする。
1. 追加したいユーザーIDを TOPページの Enter the added user id で入力する。ここでは、 http で playok のサイトにアクセスし、指定したユーザーのプロフィールと zip file を取得し、似非データベースに登録している。このため登録処理には多少時間がかかる。
2. 登録できたらユーザー名をクリックすれば序盤進行の統計が見れる。統計の対象としたのは、取得したZIPファイルに記載された序盤20手までの分岐進行で、黒持ちの場合と白持ちの場合で分けて登録している。オセロの盤面と連動して次の一手の統計を表示するようにした。

ここから、各ユーザーに対する序盤対策を練ることができる。打つ可能性が高く、勝率の低い進行を選択することで勝てる可能性が高くなるはずだ。例えば、 iwata というIDの人を相手にする場合は、打つ進行にも依ると思うが、白持ちで縦取りを行うのが最も勝率が高くなることが分かる。(この情報を元に対策しているという可能性はないことにして。)というか、大抵の人に対しては、白持ちで縦取りをするのが最も勝率が高い事が分かる分けだが。強豪プレーヤーに対しては、これで対策を行なっておくと有利にできる可能性が高くなるかもしれない。

現状の制限事項として、登録される棋譜は全て初手をF5からに書き換えている。また、手順前後の盤面や回転して一致する盤面も別局面扱いとしている。

謝辞
オセロの盤面表示のソースは、ニコニコ動画の「オセロを1時間で作ってみた」で公開されていたものから大部分を拝借させて頂いた。
http://www.nicovideo.jp/watch/sm8391299
多分、自分でこの処理部分を作っていたら、丸1日位かかっていたはずなので非常に助かった。

2010/07/19

序盤研究 第三回

2ヶ月ぶりの更新となる今回は、できるだけ不利にならずに相手の暗記範囲から外す手順を検討しようと思う。

まず、不利にならないように暗記範囲から外れる確率の高い手順とはどのような手順であるかだが、やはりそれは引分分岐数の多い手順になると思う。有名な引分手順でない限りは、普通に引分進行を打っていても暗記切れを起こすと思うが、分岐数が多い場合には尚更暗記切れを起こし易くなる。引分形勢で相手の暗記範囲外にできれば御の字だ。オセロには序盤の引分分岐だけでも人間には覚えきれない程の数が存在している。

そんな分けで今回は Zebra 先生の Book (終盤24~28手読み) に登録されている中から引分分岐数の最も多い手順(序盤20手まで)を紹介する。


初手 F5 から始めた2手目。序盤研究 第一回 で紹介したように斜め取りの方が引分分岐数が多くなる。


斜め取りで E6 D6 と進んだ5手目。飛び出しの進行よりも、牛定石の方が引分分岐数は多い。


6手目は F4 の大量取りよりも E3 進行の方が引分分岐数が多くなる。


7手目はF3になる。D3よりもF3の方が2倍以上引分分岐が多い。


8手目は C4 が最も多くなる。 大会等の実戦の対局では F4 を好む人が多いかもしれない。以前は F4 は白2石勝ちと思われていたが、比較的最近に引分進行が見つかり、引分に収束している。


9手目はC3。実戦譜ではC6を打つ人が多いかもしれない。ここで漸く縦取りの引分分岐数よりも少なくなった。


10手目。引分分岐は3箇所あるが B6 が圧倒的に多い。


11手目は C6 一択で進み12手目。F4が引分分岐数が最も多くなる。


13手目。黒に有力な変化が3個あるが引分分岐数はD7が最も多い。


14手目は一択でB4に進む。
15手目は引分進行は4箇所あるが A3が圧倒的に分岐数が多い。

余程の暗記マニアでない限り、普通はこの辺りで既に暗記切れになっていると思う。この進行ならここ位まで暗記していれば十分かもしれない。

一応20手まで進めてみる。16手目は一択でB5と置いて下記局面。17手目はG3を選択する。


18手目。引分分岐が6箇所あるので暗記するのが涙目になる。引分分岐数はA4が最も多い。

19手目。黒からの引分分岐は3箇所。G5が最も多い。

20手目。引分分岐がさらに5箇所。G6が最も多くなる。


21手目。黒からの引分分岐が4箇所。D2が最も多い。



ということで、一応21手まで紹介したが、実戦でこのような引分分岐数の多い進行を打った場合には、序盤十数手程度で、双方の暗記が切れるような展開になるはずだ。

一般的には、引分分岐が多い=暗記が大変、となるかもしれないが、必要な暗記量=相手の暗記量と同程度と仮定するならば、実は、引分分岐数の多い進行は、相手も暗記できていないために、逆に暗記量を減らせれる可能性がある。(たとえ、暗記の絶対量は減らせなかったとしても、その分、より序盤で暗記切れにはなる。)


そんな分けで、暗記に頼らず、読み勝負に持っていきたい場合には、引分分岐数の多い手順は有効かもしれない。


今回公開した情報は2010年7月時点のものであり、解析が進みむとこのようにならない可能性があることも注意して欲しい。Zebra は中盤の精度が悪いために、解析不足の状態では、引分進行が不正確な状態にある。(引分でない進行が引分に見えたり、逆もありえる。)
最近進めた Edax による解析では Zebra の引分進行が崩れたりするケースが幾つかあった。

2010/05/22

カンケル

今回は単なる月記的なもの。

これまでに、用途に合わせた2系統のEdax用の簡易自動学習ツールを作成し、PC2台(計8CPU)を稼動させることで、一ヶ月で約20万局を学習させることができた。ただ、学習開始初期はツールの機能不足や学習効率の関係で、CPU に相当の pending 期間が存在していた。今ではそれなりにpending 期間を減らして自動学習の効率を上げてきており、今の環境でも月間30~40万回程度は学習できるポテンシャルはあるように感じる。これなら(電気代と引換えに)年間300万局程度は学習可能であるので、現在所有の Zebra Book を3年以内に追い越せるし、実戦に使う進行だけなら1年かからない。オセロを続けるなら Edax の方が得策だと判断し、学習環境を Zebra から Edax へ移行することにした。

先月4.0がリリースされたものの、学習の際に気をつけなければならないのは Edax の使用バージョンだ。今日まで Bug Fix のために、こまめにバージョンアップがされている。恐らく、Edax 4.0.0 ~ 4.0.3 まではバグが存在し、Bookに不正確な評価値が書き込まれることがあるようだ。実際に、Wzebra で +2 になった進行が、Edax では +0 になったりとバグが顕在化している。この Book に不正な値が書き込まれるバグは、バージョン 4.0.4 では修正されているように見える。

また、5/15 時点では、Edax の最新バージョンである 4.1 がソースコードのみ公開されていた。実際に、インテルC++コンパイラでコンパイルを行い、Edax 4.1 の処理速度を評価してみたところ、同コンパイラでコンパイルした Edax 4.0.4 よりも明らかに処理速度が劣る結果となってしまった。そんな分けで、現時点では、4.0.4 が最善のバージョンであると感じる。(4.1が正式リリースされても速度が改善されない場合を考慮して、4.0.4のソースコードは大事に保存しておくべきかもしれない)

と、ここまでが前置きで、今回は、Ubuntu の事を書いて欲しい、というリクエストがあったので、オセロプレイヤが Ubuntu を使う際に必要になりそうなソフトを少しだけ紹介しようと思う。Ubuntu を知らない人は、まずは Google 検索から。
もし、Edax を使用するのに 32bit 版の Windows を使ってるなら、64bit 版の Ubuntu を使う方が幸せになれると思う。

下記は普通にオセロプレイヤでなくても必須のソフトしか書いてないし、詳細についてはここで説明するより Google 検索の方が有効な情報が得られる。

(1) Wine のインストール
Wine は Windows バイナリを Linux 上で動かすのに必要なプログラム。Windows 環境と同程度の速度で Windows アプリケーションが動作する。Linux 環境で動作可能なオセロソフトとしては、Zebra の Linux 版である LZebra が存在しているが、リリースされているLZebra のバージョンは古く、LZebra 使用している GTK ライブラリも古いので、動作環境を揃えるのに少々難がある。それよりは、Wine で WZebra を使用した方が遥かに手っ取り早いし性能もいい。また、Wine で Nborad + Ntest や Runoth 等も動かせる。

(2) インテル C++ コンパイラ Linux 版 のインストール
インテル C++ コンパイラ の Linux 版は無料で使用することができる。Edax はソースコードが公開されているため、インテル C++ コンパイラでコンパイルしてバイナリを生成できる。標準付属の lEdax は恐らく GCC でコンパイルされており、それよりも 3割程度の処理速度の向上が見込める。
動作速度向上以外にも、Edax を Nboard の GUI 操作で学習させる際には、デフォルト動作の学習パラメータを変更させるためにソースコードの編集&コンパイルは必須だと思う。

(3) SSHサーバーのインストール
Edax は CUI が基本なので SSH でも操作できる。SSHクライアント等をインストールした携帯電話を使えば、携帯電話からいつでもどこでも(大会の試合の合間とかでも) Edax の操作が可能になる。ただし、携帯電話で F5 とかを入力していくのはしんどいので、何か専用のGUIソフトが欲しい(時間に余裕があったらそのうち作ろうかと思う)。また、メインのPC環境が Windows の人は、Cygwin の X Window から SSH サーバー(Ubuntu)にログインして、Windows のディスプレイに Linux の GUIアプリを表示させる形がいいかもしれない。VNC でのリモート操作は無駄に動作が重い。

以上、オセロ関係で思いついたのは、これくらいしかなかった。

2010/04/16

終末の過ごし方

名人戦も終わった2010年4月、全世界のオセロマニア達(=数人)の間で激震が走った。 Edax 4.0 が遂に正式リリースされたためだ。実に約5年ぶりのメジャーリリースとなった本バージョンでは、64bit化、マルチコア対応など、近年のCPUの進化の方向性に合わせた非常に強力なソフトへと進化していた。
http://abulmo.perso.neuf.fr/edax/4.0/index.htm

勿論、オープンソースとなっている WZebra も一部のプログラマ達の手によってマルチスレッドやSSE対応等の改良が行われ、密かに進化は続けてはいる。しかし、現時点でフリーで一般公開されているオセロプログラムとしては Edax は比類なき最強のソフトになったと言える。(もしかしたら全てのオセロソフトの中でも最強かもしれない。)

そんな分けで、今更ながら今回は Edax の紹介をしてみようと思う。
とはいえ、自分自身はコンピュータオセロにはそれ程詳しくはないので、今回の記事は、コンピュータオセロマニアの方にとってはためになるような内容な何も書いていない。

で、 Edax に関してだが、周知の通り、オセロソフトの中では最高レベルの精度の中盤の評価関数を持っている。これは、MasterReversi との対戦結果からも如実に現れていることだと思う。
http://homepage2.nifty.com/t_ishii/mr/gameresult.html

敢えて、フリーのオセロソフトのBook無効時の強さに優劣を付けるならば、
Edax > Herakles > Ntest > WZebra
であると思う。
(正し、係数値を変更しなかった場合。WZebra なんかは coeffs2.bin を良質なものに入れ替えてやると中盤が強くなる。ちなみに CEZebra に標準付属の coeffs2.bin を WZebra 付属のに入れ替えても CEZebra の中盤の能力が WZebra と同じなり強くなる。)

ただ、Edax で唯一ネックだったのは、解析速度がそれほど速くなかった点にあったと思う。しかし、今回のバージョンアップでは、アルゴリズムの改良のよって大幅に解析速度が向上している。それに加えて、64bitアプリケーション化とマルチスレッド対応により、さらに数倍の高速動作が可能になっている。つまり、今回の更新によって、これまでネックだった点が完全に払拭され、(というよりも既存のソフトを遥かに上回る状態になり)非の打ち所のないソフトとなった。

また、edax は CUI ベースで動作するプログラムであるため扱いにくく感じる人も多かったと思うが、いつの間にか Nboard に対応していたことで、視覚的にも容易に扱えるようになった。Linux 用の GUI としては Quarry が使用可能だが、Quarry では評価値が表示できないので、Linux ユーザーの人は Wine で Nboard を使うのがいいかもしれない。

Edax の操作が CUI ベースであることをデメリットのように言う人も居ると思うが、実はCUIベースであることによる非常に大きなメリットがある。それは、外部のプロセスから容易に制御可能である点だ。例えば、プログラミングの知識が全くなくても、操作コマンドを書いたテキストを用意しておけば、単方向のパイプを利用することで、シェル上で下記のようなコマンドで容易に自動学習を行うことができる。
$ cat script.txt | edax.exe
もっとも、このような単純なことがしたいのであれば、わざわざパイプを使う必要はなく、
#! /usr/bin/edax
として、操作コマンドを記述したスクリプトで起動した方が良いかもしれない。実はコマンドを手動入力しても、数行で自動学習は可能なんだが。
もう少し凝った制御がしたい人は、適当なプログラミング言語で双方向のプロセス間通信をすればいい。そんな感じで普段は自動学習させておき、評価値を確かめたいときだけ Nboard を使うようにすれば、大抵のやりたい事は実現できる。

Edax の Book は過剰学習でも評価値が狂うことがなく正確に表示され、また終盤の進行は追加されない(深さを指定可能)ために無駄に容量が大きくなることはない。このため、自作のBook編集ツール等を作成するスキルがない人でも、非常に質の高いBookを作成することが可能だ。

そんな分けで、これからは Edax を使いこなせる人が強くなる時代が到来しそうな気がする。多分。

記事の内容でなんか間違ってたら指摘 kudasai。

2010/03/22

Преступление и наказание

名人戦決勝の高梨名人の打ちまわしには正直驚愕した。WZebraを使えば簡単に再現できてしまう程に全て最善だった。
f5d6c3d3c4f4c5b3c2e6c6b4b5d2e3a6c1d7e7f6a4e2a5d1f7b6c8d8a7b8e8f8c7a2e1b1f1f2f3b2g3g4h5h4h3g5h6g1g6g7a3a8a1b7h1h7g2h2h8g8



これは、勝つための理想的な打ち方であり、最善暗記が功を奏した好例といえる。

当然だが、そもそも、最善暗記が有効となるのは、最善進行を外れた場合にそれを咎めて勝ちきることができる場合である。そのため、相手がミスさえすれば、決して引分の最善進行を暗記する必要はない。そして、暗記する最善進行として引分進行を選択する場合、相手に先に変化されて相手の暗記範囲に嵌るリスクを伴う。そのため、素人にはオススメできない。

一般的には、引分進行は深く暗記されている場合が多いため、相手の暗記範囲外の展開に誘導するためには、2石差や4石差の進行が望ましい。自分の暗記範囲内にさえ持っていければ、人間の感覚で最善進行を打ち続けるのは困難であるため、互角か優位になる可能性は高い。(勿論そのためには、相手が最善を外しそうな手順までも覚えておく必要がある)

しかし、高梨名人は相手に変化されても、ある程度それに追従して優勢を保てる暗記量と棋力を持つ。生半可な暗記の変化を打っても、それが敗着にされる場合がある。従って、高梨名人に対して最善進行で追従していくのは、本来ならば常套手段のように思える。

今回、高梨名人が選択した進行は、先日の記事で紹介した勝率が最も高くなるという最善の引分進行である。(18手目D7引分分岐進行。実際に、この記事で書いた情報が高梨名人まで伝わり、この進行を打ってみたそうで。)この進行は、ただでさえ、引分進行から外れやすい。そして、対峙した明石準名人にとって不運だったのは、恐らくこの進行の対策を行っていなかったことだ。常套手段の筈が、不利な状況を招いてしまった。高梨名人にとっては、最善進行で石損することもなく、ノーリスクで自分の暗記範囲内に持ち込めたことになる。

刮目すべきなのは、高梨名人が最善でない手順、相手がミスしそうな展開も対策していた点だ。実際に明石準名人が最善進行から外してしまった盤面に注目してみよう。まず、25手目、Book を無効にした状態での WZebra の評価値(24手読)の結果が下記になる。この評価値を見る限りでは、F7が唯一の最善進行に見える。


しかし、学習を積み重ねたBOOKでは、F7 の負けが確定しており、D8だけが唯一の引分進行となる。人間の感覚ではD8は打ち辛く、何よりF7という一見すると良手順が見えているため、D8に置くには暗記なしでは非常に難しい。村上九段は、決勝対局終了後、読みが重要ということを力説されていた。個人的にもそれは正しいと思う。しかし、この盤面に限っては、WZebraの24手読みでもF7が悪手であることを判断するのが不可能であったように、人間の能力の限界を超えてしまっている。そのため、ここは予め暗記が必須であり、暗記でないと最善手順が打てない盤面だったと言える。



理不尽に思えてくるような羽目手順だが、それだけにこの盤面でF7に置くことは想定しやすい。高梨名人は用意周到にも、ここで黒がF7に打つことも想定して研究していたのだろう。この後、石損を咎めてそのまま勝ち切ることができている。

そんな分けで、18手目D7進行が思いの外、黒が最善進行を打ちにくいという白にとっては理想的な優良進行であることが発覚したので、ここで紹介して少なからず広めたのは正直勿体なかったかもしれない。(半分冗談のつもりで書いた記事だったのに。。)

以前の情報操作という副題が示していたように、双方にとって勝率が高いというわざと語弊のある言い方でこの進行を紹介していた。本来、この進行は白にとって勝率の高い進行である。何故ならば、タメノリでは、白からの分岐が多く存在する。つまり、黒持ちの場合、タメノリを引分にするためには500通り以上覚えないといけないのに対し、白持ちの場合は、18手目D7からのたった12通りの分岐を暗記すればいい。そのため、白持ちの方がより深い暗記進行に持ち込め、優位に立てる可能性が高い。

しかし、敢えて進行を公開することによって、白にD7に打たせる確率を上げることができる。皆が皆、D7に打つようになれば、黒も12通りだけ暗記すれば良いことになり、情報を公開することによって黒の勝率を上げることができる。そう思っていた時期が私にもありました。

黒の引分分岐が少なくなれば、黒は劣勢ではなくなる。そんな白優勢説へのАнтитезаだったりする。