コンピュータ将棋製作記 その2(2015年1月21日)
進捗どうですか?
昨日の課題
- 結局テストを書いていない
- 全ての可能な手を出力するコードを書く
今日進んだ所
- テストを書いた
- 取りうる手をすべて列挙出来るようにした
- ランダム対戦が実装出来た
実装上の課題
手の列挙
思った以上に手の列挙が面倒臭かった。
- bitboardを使えば手の効きは比較的簡単に列挙出来る(らしい)
- 一方、Square-centricの場合は全部forループで書かないといけない
- それが本当に置ける場所かどうかを確認するためには王手チェックが必要
具体的には次のような手順になる
- まず持ち駒をおける場所を(王手等無視して)全て列挙する
- ここで二歩をあらかじめ省いている
- 1段目の歩、香、桂と2段目の桂もここで省く
- 置ける場所に実際に置いた盤面を作り、そこで《盤面チェック》し、問題なければ候補に加える
- 盤上の全マスを走査し、そこに駒があれば、その駒の動ける場所を全部列挙する
- ここで味方の駒の上にはいけないが、敵の駒の上には「1歩だけ」行ける(駒を取るという意味)
- 敵陣に入った時、もしくは敵陣内から外に出た時には成・不成をここで加える
- 歩・香・桂が1段目に行ったら必ず成、桂が2段目に行ったら必ず成という処理もここで入れる
- 実際に駒を動かし、そこで《盤面チェック》し、問題がなければ候補に加える
《盤面チェック》とは、その盤面で自分の王に王手がかかっていないことを確認する(王に王手がかかっているのにそれを防がないことは許されない)。また、この時に歩を打っていて、さらに相手に王手をかけているときは、打ち歩詰めのチェックをする。
打ち歩詰めのチェックは、歩を打った盤面でまた全通りの手を列挙する。その時に手が一つもない場合に「詰み」とみなされるので、もしそうであれば打ち歩詰めと判断し盤面チェックで弾く。
テスト
実装方法
テストはSFENをassertで比較する感じの緩いテストを書いている。ユニットテストを書くべきだったのだろうが、面倒だったのでブラックボックステストを書いている。こんな感じ。
// the maximum
r = read_from_sfen(&board, "R8/2K1S1SSk/4B4/9/9/9/9/9/1L1L1L3 b RBGSNLP3g3n17p 1");
assert(r);
c = make_all_legal_moves(&board);
assert(c == 593);
// 80
r = read_from_sfen(&board, "ln6l/2gsGgk2/p3p2pp/3p1p+B2/2p3p2/1Pr1PP1P1/P+nNP1S2P/2bSK1G2/L1R5L w Sn3p 1");
assert(r);
c = make_all_legal_moves(&board);
assert(c == 80);
// mated
r = read_from_sfen(&board, "l7l/6S1p/1pnp3+S1/p1K4k1/4p2B1/3PPn1G1/1P1G2g1N/9/L1g2+r3 w RB2SNL4P6p 1");
assert(r);
c = make_all_legal_moves(&board);
assert(c == 0);
// only move
r = read_from_sfen(&board, "l7l/5bS2/p1np5/6Sk1/4p2B1/PSpPPn1G1/1P1G2g1N/2+l6/L1KN1+r3 b R3Pgs7p 1");
assert(r);
c = make_all_legal_moves(&board);
assert(c == 1);
// including Uchi-fu-zume
r = read_from_sfen(&board, "6G1k/PPPPPPPP1/8K/9/9/9/9/9/9 b P2r2b3g4s4n4l9p 1");
assert(r);
c = make_all_legal_moves(&board);
assert(c == 18);
// Tsuki-fu-zume including PIN
r = read_from_sfen(&board, "r7k/6K2/7SP/4s2bb/9/9/9/9/9 b r4g2s4n4l17p 1");
assert(r);
c = make_all_legal_moves(&board);
assert(c == 4);
実際に書いた所、2回ほど救われた。テストを書くのは超大事。
局面
昨日挙げた局面は問題なく593通りだった。駒を打つだけで469通りある。
テストの局面(SFEN)を作るのに便利なサイトを2つ紹介する。
- コンピュータ将棋連続対局場所 (floodgate): http://wdoor.c.u-tokyo.ac.jp/shogi/floodgate.html
いつもお世話になりますfloodgate。これの最新の対局から適当に選んで、そこで「USIにエクスポート」を選ぶとSFENが出力される。詰みの局面などが欲しい時に大変便利(ただし強いソフトは詰みの前に投了してしまうので、弱そうなソフトを探すのが良い)。
- クラウド将棋盤ジェネレーター: http://sfenreader.appspot.com/ja/create_board.html
Web上のUIでSFENを編集できる。テスト用の局面を作るのに本当に便利。
ランダム対局
先手も後手もランダムにさせる手を指して詰みまで動かす、というプログラムを作った。思考ルーチンはないけどコンピュータ将棋であるのは間違いない。
これがおもったより早く詰む。100回くらいやってみたところ、最短は128手だった。
後手の持駒: 歩二
9 8 7 6 5 4 3 2 1
+---------------------------+
|v香v桂 ・ ・v玉 ・ ・ 圭 ・|一
|v飛v角 ・ ・ ・v金v銀 飛 ・|二
|v歩 ・ ・v銀 ・ 馬 ・ ・ ・|三
| ・v歩 ・ ・v歩v歩 金 ・ ・|四
|v香 歩 ・v金 ・ ・ ・ ・ ・|五
| ・ ・v桂 ・ ・ ・v歩 ・ 歩|六
| 歩 銀v歩 ・ ・ 歩 ・ 歩 ・|七
| 香vと ・vと 歩 金 銀 ・ 香|八
| 桂 ・ ・ 玉 ・ ・ ・ ・ ・|九
+---------------------------+
先手の持駒: 歩二
最長は3906手。龍、馬、王、飛、角を除いて基本的に駒は前に進みたがるので、ランダムで長引けば長引くほど敵陣に大駒以外の駒が殺到するようになる。
後手の持駒:なし
9 8 7 6 5 4 3 2 1
+---------------------------+
| 全 ・ 杏 ・ ・ 杏 と ・ と|一
| と ・ ・ と と ・ 杏 ・ 歩|二
| ・ ・ ・ ・ ・ ・ ・ ・v玉|三
| ・ ・ ・ ・ と ・ ・ 馬 ・|四
| ・ ・ ・ ・ ・ 金 ・ 馬 ・|五
|vとv桂 玉v桂v香 ・v全 ・v圭|六
| ・vと ・ ・v歩v金 ・ ・ 龍|七
| ・ ・v歩vとv金v歩v歩vと ・|八
|v全vとv金 ・vとv全v圭v龍vと|九
+---------------------------+
先手の持駒:なし
雑感
- for文の数が半端ないので、Square Centricは間違いだったかもしれぬ
- コードが汚い。駒の利きを判断する同じような処理が2箇所入っている
次回予定
TODO
- TCP/IPでfloodgateにつなげるコードを書く
- 余力があればテストをもうちょっと綺麗に書く
短期目標
- 金曜夜(23日夜)までに、floodgateでランダムを走らせる。
floodgate: http://wdoor.c.u-tokyo.ac.jp/shogi/floodgate.html
追記
後手の持駒: 歩三
9 8 7 6 5 4 3 2 1
+---------------------------+
| ・ ・ 金 ・v玉 ・ 金 ・v歩|一
| と ・ 香 ・ ・ 歩 ・ 圭 金|二
|v桂v歩 ・ ・v銀 ・ 歩 龍 ・|三
| ・ ・v馬v銀v歩 ・ ・ ・ ・|四
| ・ ・ ・ 歩 ・ ・ ・ ・ ・|五
|v歩 ・ 歩 ・ 玉 ・ 香 ・ ・|六
| ・ ・ 桂 ・v香 ・v圭vと ・|七
| 香 ・v歩 ・ ・v歩v全 歩 龍|八
| 角 ・ ・vと ・v全vとv金 ・|九
+---------------------------+
先手の持駒:なし
431 ================================================
後手の持駒: 歩三
9 8 7 6 5 4 3 2 1
+---------------------------+
| ・ ・ 金 ・v玉 ・ 金 ・v歩|一
| と ・ 香 ・ ・ 歩 ・ 圭 金|二
|v桂v歩 ・ ・v銀 ・ 歩 龍 ・|三
| ・ ・v馬v銀v歩 ・ ・ ・ ・|四
| ・ ・ ・ 歩 ・ ・ ・ ・ ・|五
|v歩 ・ 歩 ・v杏 ・ 香 ・ ・|六
| ・ ・ 桂 ・ ・ ・v圭vと ・|七
| 香 ・v歩 ・ ・v歩v全 歩 龍|八
| 角 ・ ・vと ・v全vとv金 ・|九
+---------------------------+
先手の持駒:なし
432 ================================================
バグってる。王取ってる。おぅぅ…次回はこれの修正から