2012/07/20 (Fri) 一手の価値の計算

昨日行われた、第67期本因坊戦挑戦手合1日目のニコニコ生放送の中で、解説の大矢九段が出題したクイズ。

問題： A は何目の手か？

問題図は黒から打って本コウになる形。ここから変化して起こりうる図は、次の4通り。

状態1: 白が解消した形











状態2: 問題図。黒から打って本コウ











状態3: 白から打って本コウ











状態4: 黒が解消した形












このうち、状態1が白2目の地、状態4が黒13目の地（7目＋アゲハマ6)であることは数えれば分かる。そこで、黒の立場から考えて、
 V1 = -2
 V4 = 13
と書く。問題は状態2と3の価値はいくらか、ということだ。


結論から言うと、次のように素朴に考える。すなわち、状態1, 2, 3, 4 は等間隔である、と。すると、
 V2 = 3
 V3 = 8
でなくてはならない。
問題図のAの価値は、黒が打つならV2からV3への変化、白が打つなら V2からV1への変化であるから、いずれにしろ5目というのが答えになる（これは見合い計算の場合。出入り計算では10目と数える)。



さて、状態1〜4 はなぜ等間隔であると言えるのだろうか。これが、長い間の疑問だった。V2とV3の価値は、コウ材の具合に寄るではないのか。状態1〜4の価値が等間隔であるという考え方の裏には、どういう仮定が隠れているのか。次の命題がこの問いに答える。


命題：V1, V2, V3, V4が等間隔であるということと、状態2から状態1へ推移する確率が1/2であり、かつ状態3から状態4へ推移する確率が1/2である、ということは同値である。

証明：状態iから状態jへの推移確率をp(i, j)と書く。すると、次の連立方程式を得る。
V2 = p(2,1) * V1 + p(2,3) * V3
V3 = p(3,2) * V2 + p(3,4) * V4
ただし、確率の定義より、p(2,3) = 1 - p(2,1), p(3,2) = 1 - p(3,4)

もし、p(2,1) = 1/2, p(3,4) = 1/2であるなら、全ての推移確率は1/2になるので、上の方程式は
V2 = 2/3 * V1 + 1/3 * V4
V3 = 1/3 * V1 + 2/3 * V4
を導く。すなわち、V1, V2, V3, V4は等間隔である。

逆に、V1, V2, V3, V4が等間隔であるなら、方程式を解くことにより、
p(2,1) = 1/2
p(3,4) = 1/2
を得る。
【証明終】


というわけで、V1, V2, V3, V4が等間隔であるという考えの背後には、問題図においてAと打つのが黒になる確率と白になる確率が等しく、また状態3において、次にQ19に打つのが黒になる確率と白になる確率も等しい、という暗黙の仮定が隠れている。つまり、手番がランダムに巡ってくるという想定が、価値判断の核を構成している。


さて、本コウの場合、一般に、コウ争いにおける状態は4つある（白が解消、白がコウ取り、黒がコウ取り、黒が解消)。したがって、一手の価値を計算するには、白が解消した図と黒が解消した図の差を比べて、3で割ればいい（植木算。4点あれば、その間隔は3つ)。半コウを取る手が1/3目というのも同じ考え方による。


２段コウなら、状態が5つになるから、4で割って計算する。例えば下図は典型的な２段コウの形。ここから、白はT19, R19と2つ抜いて生き。一方黒は、S17, T14と抜いて取りきることができる。


















コウを解消した形は以下。左図では、白地が・・・5目くらい（黒Q19にはS19, 白T14には黒T12と決まるとすれば、白地3目＋アゲハマ3つ)？　一方、右図の黒地は・・・22目かな。計算方法が分かっても地を数えることができないんじゃ仕方がないな。まぁ大体そんなところだとして、解消形の差は27目。それを4で割って、一手の価値は7目弱、ということか（出入り計算で言えば14目弱)。合ってるのかな、これ。

2012/07/18 (Wed) 大矢先生の問題

今日も、大矢先生の本因坊戦解説が楽しかった。解説の合間に出題された問題を転載。ヨセ・一手の価値もまだまださっぱりだ。


Q1. 白Aの価値は？ （出入り計算で）

















Q2. 白Bの価値は？

2012/07/18 (Wed) R: 無理矢理pythonと連携しても、そこそこ速い

以前、RをCと連携させることで、特にループ処理の速度を改善させることができることを書いた（記事へのリンク）。しかし、やっぱりCは難しい。さらに、RからCへ渡すことのできる引数の型に制限があるなど、書き方の工夫もそれなりに手強い。

そこで、手っ取り早くループ処理の速度を改善する方法として、pythonと連携させてはどうかと考え、やってみた。pythonとの連携については特別なメソッドが用意されているというわけではない。以下の手順で、強引に連携させる。

1. 特定の計算を行うpythonのスクリプトを書き、結果はファイルに出力させる。
2. Rにおいて、system() 関数を使ってそのpythonスクリプトを走らせ、結果をファイルから読み取る。

system() 関数は、外部プログラムを呼び出すための関数で、引数としてコマンド（文字列）を受け取る。例えば、

system("ls")
とすれば、作業中のディレクトリのファイルリストを出力する（windowsなら system("dir") だろうか）。

したがって、
system("python file.py arg1 arg2")
とすれば、R上からpythonスクリプトを走らせることができる。もちろん好きなだけ引数を渡すことができる。ただし、戻り値を受け取ることはできないので、結果の受け渡しにはファイルを経由する。人に仕事頼むのだが事情があって結果を直接会って話すことができないのに似ている。結果を記したメモを壁に貼っておいてもらうのだ。


処理内容は以前と同じくN*N回の加減の計算。R, Cと連携, pythonと連携の3パターンの計算速度を比較する。
処理に用いたファイル一式はこちら。


下のグラフでは、横軸にNを、縦軸に処理にかかる時間をプロットしている（両対数軸）。やはりCとの連携が圧倒的に速い。pythonも健闘していて、Rにやらせるよりはかなり速い。

具体的には、N=10000の場合（つまり、1億回の計算）、R では145秒かかるところを、pythonでは15秒、Cではなんと0.1秒未満で終わらせている。























回帰分析の結果：

* C *
log(time) = -20.30163 + 1.93688 * log(N)  

* python *
log(time) = -14.66641 + 1.88273 * log(N)  

* R *
log(time) = -13.99015 + 2.06207 * log(N)  

 

Wald testを行うと、切片についてはすべての組み合わせについて、「等しい」という仮説は5％の有意水準で棄却された（Rとpythonの差はp値0.04くらいで、ぎりぎりだが）。
 

傾きについては、pythonとCの間には有意な差は見られなかった（p=0.156）。
一方、Rと比較したとき、python, Cはそれぞれ傾きが有意に小さい（それぞれp=0.002, 0.000）。



結論：Cほどではないがpythonとの連携もループ処理の速度改善に役立つ。

 

2012/07/17 (Tue) Ubuntu: デフォルトアプリケーションを設定

Ubuntuを11.10に更新したところ、QuarryがSGFファイルのデフォルトアプリじゃなくなってしまった。ファイルをダブルクリックするとGeditで開かれてしまうようになったのだ。


普通。デフォルトアプリの変更は、ファイルを右クリック→Prpperty→Open With　から行うことができるが、Quarryもmugoもアプリケーションリストに含まれていなかったので、弱ってしまった。


調べてみたら、同じ悩みを持った人がいたらしく、コマンドラインから解決する方法が見つかった。ソース


xdg-mime query default application/x-go-sgf
で、現状のデフォルトアプリが何かがわかる。


xdg-mime default /usr/share/applications/Quarry.desktop application/x-go-sgf
で、Quarryをデフォルトアプリに設定できる。.desktopはなぜかは知らないけど必要らしい。

2012/07/17 (Tue) Linux用の囲碁ソフト

棋譜の閲覧・編集を行うソフトウェアの中で、最も優秀なのはMultiGoだろう。特に、棋譜を画像変換する機能が強い。コウ争いや、抜き後に打ち欠く場合など、すでに石の置かれた地点に再び着手があるときには、その旨を盤外に記述することになるが、MultiGoはそれを自動的に処理してくれる優れモノだ。
三村九段もブログ記事を書くときに使っているようだ。



残念ながら、MultiGoはWindows用なので、Linuxでは他を当たらなくてはいけない。

MugoはMultiGoのクローンのようなソフト。上で触れたような画像変換機能ではMultiGoに劣るが、逆にそれ以外の機能については遜色がない。インストールは、公式ページからdebファイルをダウンロードして開けば良い。




















Quarryは、Ubuntuのソフトウェアセンターから手に入る。GNU Goを同時にダウンロードして、コンピュータと対局することもできる。オセロもできる。画像変換機能はついていないが、棋譜の閲覧に関しては操作性が抜群に良いので気に入っている。