Reversi作ってみた

c++ programming reversi

プログラミングの練習ということで、Reversi(Othello)を作ってみました。


とりあえずやったこと

  1. Board
    • ArrayBoard
    • BitBoard
  2. GUI

GUIはおまけです。まあコンソールで入力して動きを見るよりも、マウスでぽちぽちやった方がわかりやすいし楽ですよね。

ArrayBoardの実装

その名の通り、配列で作ったBoardクラスです。
参考にさせていただいたのはここ。ƒŠƒo[ƒVƒvƒƒOƒ‰ƒ€‚̍ì‚è•û ƒTƒ“ƒvƒ‹

/*
 *  ArrayBoard structure (Board Size = 8)
 *
 *  @ : WALL
 *  . : EMPTY
 *  B : BLACK
 *  W : WTHIE
 *
 *  @@@@@@@@@        0  1  2  3  4  5  6  7  8
 *  @........        9 10 11 12 13 14 15 16 17
 *  @........       18 19 20 21 22 23 24 25 26
 *  @........       27 28 29 30 31 32 33 34 35
 *  @........       36 37 38 39 40 41 42 43 44
 *  @........       45 46 47 48 49 50 51 52 53
 *  @........       54 55 56 57 58 59 60 61 62
 *  @........       63 64 65 66 67 68 69 70 71
 *  @........       72 73 74 75 76 77 78 79 80
 *  @@@@@@@@@@      81 82 83 84 85 86 87 88 89 90
 *
 *
 */

91要素の配列で上のように盤面を表現します。右の番兵(WALL)は、左のやつが2つ分働いてくれるので、要りません。

BitBoard

ボードゲームをプログラムしようとした人なら一度は聞いたことがあるでしょう。
盤面って黒があるかないか、白があるかないか、なんだから、ビット列で表せんじゃね？という発想から生まれた実装のやり方です。

ぱっと思いつくだけでも、以下のような利点があると思います。

  • メモリの節約
    • 例えば、ArrayBoardでは、BLACK、WHITE、EMPTY、WALLの2bit情報を少なくとも1Byteで表現することになりますが、BitBoardなら、そのまま2bit分で表せます。
  • レジスタに乗りやすくて速い
    • たくさんの要素を扱う配列よりは間違いなく速いです。
  • ビットレベルの並列処理
    • ビット演算は、各ビットに対して一括で処理をすることが可能です。こういうのをビット並列とか呼ぶらしいです。

実装は、ビットボードを用いた 4x4 オセロ 完全解析やhttp://vivi.dyndns.org/w/bitboard%C8%BF%C5%BE%A5%D1%A5%BF%A1%BC%A5%F3%BC%E8%C6%C0を参考にしました。

速度比較

なぜ2種類のBoardを作ったかというと速度を比較してみたかったからです。
早速実験してみましょう。

  1. Init: Boardの初期化
  2. Cand: 各点(0,0)から(7,7)までについて着手可能か判断
  3. Play: 候補手からランダムに一手打ち、盤面を更新

上のようなランダム打ちにどれだけ時間がかかるか計った結果が以下。
1000局打った合計で、単位はミリ秒です。

ArrayBoard BitBoard
Init 0.45 0.18
Cand 398 261
Play 129 51
Total 528 313

とりあえずBitBoardの方が速い

考察というか言い訳

BitBoardがそれほど速くない。

原因その1

候補手生成では、せっかく使えるビット並列処理をしていない。
加えて、ArrayBoardでは、縦横斜め8方向の1つだけでもひっくり返せるならよしとするが、BitBoardは全方向調べている

原因その2

反転パターンを作るのに、ループを使っている

原因その3

32bitOSなので、64bit整数の演算は効率が悪い？

総合してみると、面倒になってそこまで実装を詰めていないというのが原因でしょう^^;
原因その3だけは、検証してみてみる価値があるかも。

ちょっと工夫したこと

Boardの状態を表す、BLACK、WHITE、EMPTY、WALLを以下のようにすることで、BLACKとWHITEの交換を簡単にした。

C <=> -C & 3
~ +1 &3
EMPTY 00 11 00 00 EMPTY
WALL 10 01 10 10 WALL
BLACK 01 10 11 11 WHITE
WHITE 11 00 01 01 BLACK

i番目のビットの状態を取得するとき、以下のようにできる。

black = (blackBitBoard >> i) & 1
white = (whiteBitBoard >> i) & 1
return (white << 1) | (black ^ white)

分岐はないけど、これは速いのだろうか？