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つだけ動ける。キャスリングという特殊な動きがあるけど、いまはまだ実装するための道具が足りないので後回し。

Pawn move

まずはポーンから動きを実装していく。まずはというものの実際にはポーンがもっとも複雑な動きをする駒で実装も複雑。

1. 1つ前に進む。ただし、1つ前に敵味方関係なく他の駒があるときは進めない。ポーン以外の他の駒は敵の駒を取りつつ進めるがポーンだけは敵の駒を取るときの動きが異なる。

...
...
.P.

...
.P.
...

AddPawnMovesはあとで解説。

2. 最初の位置(白だと2列目、黒だと7列目）からだと2つ一度に進める。これはゲームの序盤で同じポーンを2手連続で前に進めることがよくあるので、ゲームの進行を早めるために導入された。したがって1つ前の駒を飛び越えれるわけではなく、1つ前と2つ前が共に開いていることが条件。

....P...
........
PPPP.PPP
RNBQKBNR

3. 斜め前に敵の駒があるときは、それを取って進むことができる。このときポーンの前に他の駒があっても構わない。

...
.pq
.P.

...
.pP
...

4. ポーンは最初の位置からだと2つ進めるけど、そのときに斜め前に敵のポーンがいたら2つ進む前に敵は取ることができるよねというわけで、その取り方をアンパッサンという。これはポーンが2つ前進した直後の手でしか有効ではないので最後の手を見て判断。

..p..
.....
PPPPP
QKBNR

.Pp..
.....
P.PPP
QKBNR

.....
.p...
P.PPP
QKBNR

Pawnは前にしか進めないので、盤の端に到達すると、そのままだと動けなくなってしまう。端まで到達したポーンは必ずポーンとキング以外の他の種類の駒つまり、ナイト、ルーク、ビショップ、クイーンにpromoteしないといけない。「必ず」というのはステールメイトが関わっていて、ポーンが動ける限りステールメイトにならないところが、端のポーンがpromoteしないとステールメイトになりやすくなってしまう。また、クイーン以外にpromoteするというのも、ごくごく稀にクイーンにpromteするとステールメイトという盤面がある程度。普通はpromoteはクイーンにと思ってもいい。

Blogger parts: Chess Board (cont.)

暗い背景の上に白いチェスの駒を表示すると、駒の本体のあたりが透けて白く見えない問題があったが、「黒の駒を白く表示した上に、白の駒を表示すればいいんだよ」というすごいアイデアを見つけた。 さっそくやってみる。

おお！ついでに、黒の駒の後ろにも白で描画された白の駒を置いてあります。分かりにくいけどbishopの十字がちゃんと白くなっていたりね。

JavaScript / CSS は次のようになった。

こうなると、盤面は違う色でも構わないので変更。さらにマスが正方形になっていないのでサイズを調整。

r.bqkbnr
pppp.ppp
..n.....
.B..p...
....P...
.....N..
PPPP.PPP
RNBQK..R

Blogger parts: Chess Board

これまでチェス盤の表示はプログラムの出力のASCII出力のチェス盤をpreで貼っただけだった。こんな感じ。

r. bqkbnr
pppp. ppp
. . n. . . . .
. B. . p. . .
. . . . P. . .
. . . . . N. .
PPPP. PPP
RNBQK. . R

しかし、これだとみづらいので、これをclass="chessboard"をつけるだけで下図に変換するJavaScriptを書いた。 (2012/4/12 追記: スクリプトの変更前の画像に差し替え）

JavaScriptは次の通り。文字列をスキャンしてKとかnとかをチェスの駒へと変換し（unicodeにチェスの駒がある！）、全体をtableとして構成し、もとのエレメントと入れ替える。 Closure compilerにかけてscriptタグで囲んだものを、Bloggerのレイアウト > HTML/JavaScriptガジェットとして登録する。 次にCSSを設定。CSSはCSS3 Chess Boardを参考にさせてもらった。以下のCSSをテンプレート > アドバンス > CSSを追加 から設定。 unicodeに含まれるチェスの駒を使うと白い駒の白い部分が白くならないという問題があって（フォントは黒い部分を定義するものなので）、オリジナルのCSSだと市松模様にグラデーションをかけて白く見せている。どちらがいいかなと思ったんだけどグラデーションはなしにしている。