4x4 Reversi

去年の話ですが、子供の幼稚園にサンタさんがやってきてくれたおもちゃがこの「ひっくりかえるゲーム」。4x4 reversi ですね。

何度か、遊んでみたところ後手が強すぎるのではないかという気がしたのでプログラムを書いて調べてみたところ、最善手進行は以下のとおりに。

....
.OX.
.XO.
....

score = -8
20
..O.
.OO.
.XO.
....

score = 8
30
..OX
.OX.
.XO.
....

score = -8
31
..OX
.OOO
.XO.
....

score = 8
10
.XXX
.XOO
.XO.
....

score = -8
03
.XXX
.XOO
.OO.
O...

score = 8
32
.XXX
.XXX
.OOX
O...

score = -8
00
OXXX
.OXX
.OOX
O...

score = 8
23
OXXX
.OXX
.OXX
O.X.

score = -8
33
OXXX
.OXX
.OOX
O.XO

score = 8
13
OXXX
.XXX
.XXX
OXXO

score = -8
pass
OXXX
.XXX
.XXX
OXXO

score = 8
pass
OXXX
.XXX
.XXX
OXXO

X win!

予想通り、後手が圧勝。23の手が好手です。しかし、その前の段階でXは確定石が6つなので、Oは厳しいですね。子供には「角を取ると強いよ」と教えたいところなんですが、実際には、角を取らせて容易に勝っているので8x8の準備練習にもなってないし。もちろん、8x8も本当に強くなると角を取るのはいい手ではなくなるんですが。

Forsyth-Edwards Notation

Chessの局面の表現として、Forsyth-Edwards Notation（FEN）という記法がある。これは、19世紀にDavid Forsythによって新聞でチェスの棋譜をコンパクトに記事にするために開発されたもので、コンピュータチェスでは、チェスを含むボードゲームの棋譜を保存するためのPortable Game Notation (PGN)で用いられたり、コンピュータチェスにおいてコンピュータ同士が通信するためのインタフェースであるUniversal Chess Interface (UCI)でも用いられている。

実際のFENは、例えば次のようなものである。

r1bqkbnr/ppp2ppp/2np4/8/2P1P3/4Q3/PP3PPP/RNB1KBNR b KQkq c3 0 5

最初のブロックが駒の配置を表している。/で区切られた文字列が盤面の上（8行目）から順に各行を表している。各行は左（A列）からのコマの配置を表し、数字は連続する空マスの数である。つまり、上の文字列は次の盤面を表している。

r.bqkbnr
ppp..ppp
..np....
........
..P.P...
....Q...
PP...PPP
RNB.KBNR

次のブロックは、次の手が白(w)の番か、黒(b)の番かを表している。

3つ目のブロックは、キャスリングが可能かどうかを表している、KQkqはそれぞれ白のKingサイド、白のQueenサイド、黒のKingサイド、黒のQueenサイドを表す。いずれのキャスリングも不可能なときは、- となる。

4つ目のブロックは少し面白くて、アンパッサンのターゲットとなるマスを表している。つまり、このマスに駒があるとしたらとれるポーンがあるならばアンパッサンできるということを意味している。

5つ目のブロックは50手ルールに関するカウントで、最後にポーンが動くか、駒が取られるかしたあとで経過した手数を表す。

最後の6つ目のブロックは最初からの手数を表している。

このFENを実装したことで盤面の状態を文字列で表せるようになった。これを利用して、すべての駒のすべての配置からの可能な移動と、あるゲームの経過の中での可能な手とある手を打った後での盤面を確認するテストコードを生成した。ユニットテストというよりもレグレッションテストに近いですが、早速、キャスリングの実装にバグを発見した。テスト重要。

テストフレームワークはgoogletest http://code.google.com/p/googletest/ を使い、一部を抜粋すると次のようなコードになっている。これはレグレッションテストの方で5000行程度、駒の動きの方が18000行程度あり、コード本体の10倍以上のコードでテストしていることになっている。

あれ、コードのフォーマットが壊れているな。後で直しておきます。

Evaluating function and min-max search

チェスではカードゲームなどとは異なり、各プレイヤーは次の手を考える上で完全情報 (perfect information)を持っている。 すると、各盤面に対して、次のいずれかがいえる [von Neumann and Morgenstern, 1944]

1. 白が勝ちの盤面であれば、白は黒がどのような手を打とうとも必ず勝つことができる。
2. 引き分けの盤面であれば、白は黒がどのような手を打とうとも少なくとも引き分けることができるし、黒も白がどのような手を打とうとも少なくとも引き分けることができる。しかし、両者が最善手を打ち続ければゲームは引き分けに終わる。
3. 黒が勝ちの盤面であれば、黒は白がどのような手を打とうとも必ず勝つことができる。

そこで、評価関数（evaluating function / evaluation function） f(P) を白が勝ちのとき f(P) = +1、引き分けのとき f(P) = 0、負けのとき f(P) = -1とすると、各盤面 P から次の盤面 P' の評価関数 f(P') が最大となる手を打ち続ければいい。

もっともこれは存在定理のようなもので、実際にチェスの各盤面が与えられたときに、それが上記の3つのどれに属しているかを判定する手法は知られていない。 masterのゲームが引き分けで終わることが多いことからチェスの初期盤面は引き分けではないかとはいわれている。 しかし、それを確認するためには初期盤面からのすべての手を確認する必要がある（後にαβ探索の発明ですべては必要ないことがわかったが）。 チェスの各盤面に対する有効な1 move（白、黒と順に動かした場合を1 moveという。将棋のように片側だけの手を数えるときは1 plyという）はおよそ10³通りある。 典型的なチェスのゲームは40手程度であることから初期状態から終盤まで読み切るには10¹²⁰程度の盤面を評価する必要がある。 1つの盤面を評価するのに1μsとしても計算を終えるには10⁹⁰年かかることになる（と原著でなってますが10¹⁰⁵年かな？まあ人の寿命が10²なので誰も答えを知りえないという意味では同じ）。

一方で、盤面の種類数で考えると 64! / 32!(8!)²(2!)⁶ = 10⁴³ 程度であるが、これも計算可能な数字ではない。 （チェスとは違い、チェッカーが最近解かれたが、チェッカーは10¹⁵程度の盤面数で、それでも解くのに18年かかっている。）

そこで、完全ではないが評価関数の近似を求めることを考える。 評価関数は白黒それぞれの駒に対するスコアと各駒のレイアウトに応じて計算される。 Shannonは次のような項（いまでいうfeature）を提案している。

1. クイーン、ルーク、ビショップ、ナイト、ポーンそれぞれのスコアを9, 5, 3, 3, 1とする。
2. ポーンの陣形
   1. 後ろにいたり、孤立していたり、重なっているポーンは弱い。
   2. センター e4, d4, c4 にいる。
   3. キングのそばのポーンの弱さ。
   4. ビショップと異なる色のマスにいるポーン。
   5. passしたポーン。
3. 駒の位置
   1. 進んだナイト e5, d5, c5, f5, e6, d6, c6, f6 で特にポーンに守られており、敵のポーンに攻められていない。
   2. ルークの前が開いている (open file / semi-open file)。
   3. 7列目のルーク。
   4. 重なったルーク。
4. コミットメント、攻撃など
   1. 守りに必要な駒。
   2. 攻撃している駒。
   3. pin
5. 晒されているキングは弱い。
6. movability （有効な手の数）

Shannonは、この評価関数は中盤で用いられ、序盤と終盤は異なった原則を用いるべきであるといい。また、これらの項の重みは実験に基づいて決められるべきと今で言うところのmachine learningの必要性を示唆している。

重みを決めるのが難しいので、最初の駒得の部分しか実装してないが、プログラムは次のようになる。

そして、この評価関数を用いてminmax探索を行うことを述べている。 minmax探索については以前にもScalaで書いたので詳しいことは省略するが、C++で書くと次のようになる

チェックメイトの判定のあたり、スコアとして帰ってくる値を使って、もうちょっとスマートにできないかなとは思うのだけど。

minmaxはすべての枝を探索するので、max_depthを1つ上げるごとに30倍程度の時間がかかる。 Shannonの論文では3 moves (max_depth = 6) で、10⁹盤面の評価をしなくてはいけなくて、1つあたり1μsとすると16分程度かかると書かれているが、実際に計算してみると1つの盤面評価に13μs程度かかり、盤面数は3×10⁸で70分かかった。 1 game終わらせるのに徹夜でも2日強は最低かかりそう。

論文ではさらに静止探索 (quiescent search）や前向き枝刈り（forward pruning）のアイデアも書かれている。 それらについては、またの機会に実装することにするが、Shannonの先見の明に驚くばかり。

more C vs C++ for Chess

前回に続いて、CとC++でのチェスのプログラムのスピード比較を行った。前回と違い今回はg++でCのコードをコンパイルしただけでなく、コード全体をclassを使って書きなおした。class使ったら遅くなるんじゃないの？という疑問に答えようというわけだ。

まずはCとほぼ同じ処理をするコードをC++らしくclassで書きなおしたものが以下のプログラム。今回の話に関係のない入出力周りとmain周辺は省略してあるが、そこもCと等価なコードになっている。主な違いは

• Move* mやPosition* posが関数の第1引数に必ずのようについていたのが、classとすることでその引数が暗黙のthisとなり不要になった。しかし、これは表面的な差に過ぎず、アセンブル出力をみると this は第1引数の (%rdi) に割り当てられているので実質的には差はない。
• 変数の宣言が最初の使用位置へ。とくにfor loopでscopeが変化している。
• 変数はprivateになり、setter/getterを通してアクセス。ただし、inline化されているので実質は同じと考えられる。

まずはプログラムを見てもらうとして、分析はその後で。

claude.h

claude.cc

前回と同様に random player 同士の対戦を1万回実行の実行時間でベンチマークを行ったところ、C版とほぼ同じ実行時間となった。どちらかというとC++の方がちょっと速いかもしれないが有意とはいえない程度の差。

ただし、どのように書いても同じというわけではなく C と C++ の違いに注意する必要はある。クラス Position のなかで Move next_moves_[200]; としている場所があるが、今度のC++コードでは Move はクラスであるのでコンストラクタが200回呼ばれることになる。このとき Move のコンストラクタとして次のように教科書通りのデフォルトコンストラクタを設定すると実行速度はC版が24秒程度だったのに対して、C++版が35秒程度と大幅に低下した。

実際に new Move[1000000] の実行時間を測ってみると、上記のコンストラクタだと 0.015192 s, 0.014435 s, 0.015185 s と1つあたり0.015 μsかかる。一方、デフォルトコンストラクタ Move::Move() {} だと、0.000804 s, 0.000762 s, 0.000467 s となる。new の数を1桁増やすと上記のコンストラクタの実行時間は1桁増えるが、後者は変わらないので、デフォルトコンストラクタは実際にはなにもせず、この実行時間はメモリ確保のための時間だろう。

そもそも Move next_moves_[200]; という固定配列はよくない。これを STL の vector にする。すると実行時間は27秒前後と3秒程度低下する。このスピード低下を STL を使うからと短絡的に考える前に原因を探ってみよう。DoMoveのなかで、 *dst = *this; としている部分が怪しい。この処理の中でnext_moves_も当然コピーされるが、それは重い。しかし次の盤面では next_moves_.clear() を呼んでいることからも、 next_moves_ のコピーは不要である。is_under_attack_ のコピーも同様に不要。そこでこれらをコピーしないようにプログラムを修正する。

board_ のコピーは memcpyでも出来るがそれほど実行時間に差はでないので、ここでは普通の書き方にしている。実行時間を測定すると 17.166239 s, 16.805014 s, 16.713350 s おお、C++ 速い！ いやいや、同じことが C でもできるよねと、やってみると 18.646168 s, 18.581420 s, 18.566730 s 。

アセンブル出力を見比べてみると、ところどころ微妙な差があるのが分かる。2次元配列にアクセスするコードが違っていて、C では以下の5命令になっている部分が、

C++ では4命令になっている。

is_under_attack の型が int から bool になったので、バイト数が4倍違うせいか。C の方の is_under_attack の型を char にしてみると同じになった。なぜ leaq (%rdi, %rax, 32), %rax とはならないのだろう。32倍はダメなんだっけ？

以上のことから class を使っても、C と C++ では実行時間に差が付かないと結論づけてよさそうである。遠慮無く C++ でコードを書くことにする。 むしろ、C++ の方が速いという計測結果がでているのが不思議。STLを使ってメモリ消費が少なくなった分かな？

あとは virtual 使ったらどうなるのかが残された疑問だけど、今回は使わなかったのでまた次回。

C vs C++ for Chess

チェスプログラムを敢えてCで書いてきた。それの理由のひとつは、Shannonの論文中で関数F1, F2のように書かれていることからも、間違いなくオブジェクト指向では書いてないということがある。そもそもAlgol以前かな？しかしそれ以上に、Cの方がC++より速いという神話は本当か？という疑問を確認したいからという動機があった。

というわけで、単純な実験としてプログラムをCとC++でコンパイルしてみて実行速度を計測してみた。まだ、思考ルーチンは書いていないが、一番、ベースになる駒の動きの部分のスピードは常に効いてくるので、今の段階での比較には意味がある。

計測は、random player vs random playerの対戦（決着がつかないため99手で打ち切り）の1万回の実行をgettimeofdayによるwall clockの計測。 また乱数の引きの影響を受けないために最初にsrand(1)に固定している。

Cによる結果

C++による結果

有意な差はなさそう。むしろ、この結果だけをみたらgccよりg++の方が速い。

というわけでCの方が速いは迷信だろうというのが、ここでの結論。ただし、g++でコンパイルしただけで、C++らしいコードになっていないので、それについては、これから書きなおしてみて、再度、計測することにする。

Castling, checkmate and random player

駒の動きの最後にキャスリングの実装。キャスリングは、キングを隅に移動することで守り、ルークを中央に出すという意味がある。キャスリングがないころのチェスでは1手ずつ順に駒を動かしてキャスリングと同じ事をしていた。しかし、双方とも、キャスリングをすることが多かったため、ゲームのスピードアップのために1手として実行できるようになった。ただし、強力な手のため以下の制約を満たさないと実行できない。

1. キングが以前に動いていない。
2. キャスリングをするサイドのルークが以前に動いていない。
3. キングとルークの間に他の駒がない。
4. キングが移動する経路が敵の駒によって攻撃されていない。

プログラムにすると以下のようになる。 ここで、is_under_attackは駒の動きの計算と同様にして計算される。

is_under_attackを使うと、キングが攻撃されているか、すなわちチェックされているかが判定できる。 チェスでは自分が行動したあとで自分のキングがチェックされる手は無効である。 将棋では負けだけど、チェスだとその手は無効ですよと相手にやり直しを求めることになる。

もし、自分の手の前からチェックされていて、自分の手のあとでチェックにならない盤面になる手がないのであれば、それはチェックメイトといい負けとなる。 一方、自分の手の前にはチェクされていなかったのに、自分の手のあとではチェックになる盤面しかないのであれば、それはステールメイトといい引き分けとなる。

ここまででランダムな手で実行するチェスプログラムができた。全コードをGistにあげておく。どこかにバグがまだ潜んでいてキャスリングできるはずなのにできないことがあったりします。

Shannonの論文では、ランダムプレイヤーは 1. f3 e5 2. g4 Qh4# とfool's mateで負けると書いてあるが、さすがにその手を打ってくれることは滅多になく、最後にチェックだけはかわしてくるので、それなりに楽しめます。

Knight, Bishop, Rook, Queen, King Move

前回のポーンに続いて残りの駒の動き。ポーン以外の駒はキャスリングを除いて状況に応じて動きが変わることもなく、実装は比較的単純。実際、将棋と異なり、どちらを向いているかという白と黒の差もない。
指定された位置へ移動できるかをチェックして可能なら追加するユーティリティ関数を用意。指定された位置が空白なら返り値は1、それ以外なら0。 ナイトの移動はL字型に8方向。 ビショップは斜めに敵の駒にぶつかるまで。 ルークは十字。 クイーンはビショップとルークの両方を合わせた8方向を動ける最強の駒。BIshopのための関数とRookのための関数を呼べばいいよねというのはShannonの論文に書いてあるアイデア。 キングは8方向に1つだけ動ける。キャスリングという特殊な動きがあるけど、いまはまだ実装するための道具が足りないので後回し。