コンピュータ囲碁 〜 モンテカルロ法の理論と実践 〜 実践編のサンプル一覧

コンピュータ囲碁 モンテカルロ法の理論と実践 コンピュータ囲碁 モンテカルロ法の理論と実践
松原 仁編・美添 一樹・山下 宏著
発売 2012年11月10日
http://www.kyoritsu-pub.co.jp/bookdetail/9784320123274 共立出版の本の紹介ページ
http://www.amazon.co.jp/dp/4320123271 Amazonの本のページ

サンプルソース

puremc20161107.zip 原始モンテカルロ囲碁、およびUCT探索のソース
20161107dentsu.zip 2015年の電通大での講習会のサンプル集(RAVEを使ったサンプルあり)
aya_pipe.cpp pipe経由でGNU Goなどを動かすサンプルソース
majority20110728.zip LAN上のマシンで楽観合議で2台のマシンをssh経由で走らせるサンプル
cluster20120306.zip LAN上のマシンで複数台でroot並列を行うサンプル

NNGSにGTPで接続するrubyスクリプト。CGFのページに GTP2NNGS_20150629.zip があります。
twogtp.zip goguiのツールを使ってGTPで2つのソフトを対戦させるバッチファイル集
lock.cpp Lockをかける関数
aya_uct.cpp 彩のUCT部分のソース
send_gtp.cpp GTPで通信するだけのサンプル

正誤表

出版後に気づいたミス、分かりにくい表現です。

p.152 5路盤のどこを中心に$3\times 3$を取るか -> 5路盤のどこを中心に3x3を取るか
p.181 別個に二つ走らせる． -> 別個に複数走らせる．
p.189 これを次回のコミ(14.5目)とする． -> これを2手後の探索のコミ(14.5目)とする．1回の探索中に変更はしない．

役に立つオープンソースプログラム

GNU Go 代表的な古典的囲碁プログラム。対戦データを取るのによく使われる。ソースは巨大で読むのは厄介。5kの棋力。
Pachi 最強レベルのMCプログラム。ソースもシンプルで読みやすい。4コアマシンで2d、64台*20=1280コアで4dの棋力。作者はチェコのPetr Baudis。
Fuego 最強レベルのMCプログラム。ソースはやや複雑。カナダのアルバータ大で開発されている。棋力は1d?。
GoGui 碁盤のGUIプログラム。GTPに対応。機能、ツールも充実。


参考文献

(*1) Remi Coulom : Computing Elo Ratings of Move Patterns in the Game of Go, ICGA Journal (2007) Vol.30 pp.198-208.
http://remi.coulom.free.fr/Amsterdam2007/ Crazy Stoneが19路版でGnuGoを超えた手法の解説。

(*2) Sylvain Gelly, Wang, Y. , Munos, R. , and Teytaud, O. : 
Modification of UCT with Patterns in Monte-Carlo Go, Technical Report PR-6062, INRIA (2006).
http://hal.inria.fr/inria-00117266 9路でUCTを利用、3x3の手作りパターンの成功。MoGo

(*3) Sylvain Gelly, David Silver. : Combining Online and Offline Knowledge in UCT, 
ICML '07: Proceedings of the 24th international conference on Machine learning New York, (2007), pp.273-280.
http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf RAVEでレーティングが300点ぐらい9路で上昇。
加藤英樹氏による日本語訳
http://www.geocities.jp/hideki_katoh/

(*4) R. Coulom. Efficient selectivity and backup operators in monte-carlo tree search.
 InP. Ciancarini and H. J. van den Herik, editors, Proceedings of the 5th International
Conference on Computers and Games, Turin, Italy, 2006.
http://remi.coulom.free.fr/CG2006/

(*5) Markus Enzenberger, Martin Muller. 
Fuego - An Open-source Framework for Board Games and Go Engine Based on Monte-Carlo Tree Search. (2009).
https://www.cs.ualberta.ca/research/theses-publications/technical-reports/2009/tr09-08

(*6) Remi Coulom. Efficiently selecting a point to play in a random playout. (2007).
http://www.mail-archive.com/computer-go@computer-go.org/msg03139.html

(*7) 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社，1991年，ISBN4-87408-414-1
http://oku.edu.mie-u.ac.jp/~okumura/algo/  圧縮ファイル(algo.lzh)の中の mrnd.c

(*8) Mersenne Twister, 
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html

(*9) George Marsaglia, Xorshift RNGs, 
http://www.jstatsoft.org/v08/i14/paper

(*10) GoGui, 
http://gogui.sourceforge.net/

(*11) GTP - Go Text Protocol, 
http://www.lysator.liu.se/~gunnar/gtp/

(*12) GNU Go, 
http://www.gnu.org/s/gnugo/

(*13) 矢野洋平, 村松正和. : 碁盤上の連数最大化問題について, Game Programming Workshop, (2006). pp.107-113.

(*14) Shih-Chieh Huang, New Heuristics for Monte Carlo Tree Search Applied to the Game of Go, (2011).
http://www.grappa.univ-lille3.fr/~coulom/Aja_PhD_Thesis.pdf

(*15) R. Coulom. : Lockless hash table and other parallel search ideas, (2008).
http://www.mail-archive.com/computer-goxcomputer-go.org/msg07611.html

(*16) Lukasz Lew, libgo, (2006).
http://www.mimuw.edu.pl/~lew

(*17) Parallel Monte-Carlo Tree Search. 
Guillaume M.J-B. Chaslot, Mark H.M. Winands, and H. Jaap van den Herik,
6th International Conference on Computer and Games, (2008).
http://www.personeel.unimaas.nl/m-winands/documents/multithreadedMCTS2.pdf

(*18) R. Coulom. Criticality: a monte-carlo heuristic for Go programs, 2009. Invited talk
at the University of Electro-Communications, Tokyo, Japan.
http://remi.coulom.free.fr/Criticality/Criticality.pdf

(*19) Scalability and Parallelization of Monte-Carlo Tree Search
Amine Bourki, Guillaume Chaslot, Matthieu Coulm, Vincent Danjean, Hassen
Doghmen, Jean-Baptiste Hoock, Thomas H´erault, Arpad Rimmel, Fabien
Teytaud, Olivier Teytaud, Paul Vayssi`ere, and Ziqin Yu
Conference on Computers and Games, Kanazawa, Japan, 2010
http://hal.archives-ouvertes.fr/docs/00/51/28/54/PDF/newcluster.pdf

(*20) 副島佑介, 岸本章宏, 渡辺治. : モンテカルロ木探索のRoot並列化とコンピュータ囲碁での有効性について.
  Fuegoを使った合議実験。ゲームプログラミングワークショップ, (2009), pp.27-33.
http://www.is.titech.ac.jp/~kishi/pdf_file/soejima_kishimoto_watanabe_gpw2009.pdf

(*21) Progressive Strategies for Monte-Carlo Tree Search
G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk and H.J. van den Herik
New Mathematics and Natural Computation, 4(3), 2008

(*22) Baier, H. and Drake, P. (2010). : The Power of Forgetting: Improving the Last-Good-Reply Policy in Monte-Carlo Go.
 IEEE Transactions on Computational Intelligence and AI in Games 2:4, pp.303-309.

(*23) Petr Baudis. MCTS with Information Sharing. 修士論文. (2011).
http://pasky.or.cz/go/prace.pdf

(*24) 近藤嘉雪「Ｃプログラマのためのアルゴリズムとデータ構造」ソフトバンク 1992

(*25) David Fotland. Progressive widening vs unpruning. (2009). 09/30
http://www.mail-archive.com/computer-go@computer-go.org/msg12628.html

(*26) David Silver.  New UCT-RAVE formula. (2008).  February 09,

(*27) David Fotland. Exploration formulas for UCT. (2011). 01/02
http://www.mail-archive.com/computer-go@dvandva.org/msg02143.html

(*28) 清愼一, 山下宏, 佐々木宣介. 『コンピュータ囲碁の入門』, 共立出版, 2005.

(*29) 河 龍一,「HARUKAのプログラム構造」, CGFジャーナル 第5号, 2003. 
http://www.computer-go.jp/journal/vol5/vol5-4.pdf

(*30) Christopher Rosin. greenpeep. (2007).
http://www.mail-archive.com/computer-go@computer-go.org/msg04944.html

(*31) R. Coulom. MM法を計算するサンプルソース. (2009).
http://remi.coulom.free.fr/Amsterdam2007/mm.tar.bz2