C言語リバーシ ビットボード

シェアする

  • このエントリーをはてなブックマークに追加

おひさしぶりです。長らく更新が滞っていました。

いろいろと忙しいのと趣味に精を出していたのとでブログを放置してしまいました。

趣味というのはもちろん音楽的なこと(作曲とかボカロ調声とか)もあるのですが、最近はプログラミングをよくやっています。

その中でも特に楽しくやっているのがC言語でのリバーシプログラミングです。(リバーシとはいわゆるオセロのことで、オセロは株式会社メガハウスの登録商標なのでリバーシと呼びます)

ということで、リバーシプログラムの作成についてブログで書いていこうと思ってます。

(このブログは音楽と動画制作だけにしようと思っていましたが、プログラミングも立派な創作活動だ、ということで、まあいいでしょう。)

ちなみにプログラミングは音楽関係のこと(C言語でのWAVファイルの読み書き・解析、C++でのVSTプラグイン作成など)もやっているので、そっちのこともいつか書こうと思います。

ビットボード

僕はもともとコンピュータ将棋に興味があってゲームプログラミングを始めたのですが、現在はコンピュータ将棋でも「ビットボード」というものを用いるのが主流になっています。

リバーシで説明します。

リバーシの盤は8×8の64マスで、各マスは必ず「何もない」「白石がある」「黒石がある」のいずれかの状態です。(リバーシの駒は「石」と呼びます)

プログラミング初心者ならば、この盤の表現に8×8の二次元配列を用いると考えると思います。

もちろんそれでも実装できますが、データ容量の問題や実行時間の問題があり、現状はオススメできないようです。

そこで、データ容量の削減、並列計算による高速化などの目的を果たせる「ビットボード」という概念を利用します。

ビットボードとは、全てのマスを「有」か「無」かの2通りで表現し、それを1と0で置きかえて、2進数の1つの数字として表現する方法です。

詳しくはビットボードを用いた 4x4 オセロ 完全解析オセロにおけるビットボードで説明されています。

リバーシでは「黒石の有無を表すビットボード」と「白石の有無を表すビットボード」をそれぞれ「64ビット変数」で用意して、盤面の状態を表現します。

たとえば、

・・○○●●○●・(・は何もないマス)

という配置を、

黒:000011010(2進数)=16+8+2=26(10進数)

白:001100100(2進数)=64+32+4=100(10進数)

の二つの数字で表現します。「黒26, 白100」が上の配置です。

上の例は8マスですが、実際は64マスなので、最上段左上→最上段右上→次の段左上→……という順番で、64桁の二進数で盤面を表現します。

64ビット変数は環境によって変わるかもしれませんが、僕の環境(cygwinでgccコンパイル)ではuint64_tという型が64ビット変数として使えるので、それを使っています。

とりあえず盤面を表現する構造体Boardの定義は以下のようになります。(宣言のたびにstructを書くのが面倒なのでtypedefしています。_Boardのアンダーバーは定義後のBoardと名前が被らないようにするために付けているだけです。)

#include <stdio.h>

typedef struct _Board{
	uint64_t black, white;	// 黒石・白石のビットボード
}Board;

実際は、局面の情報は盤面だけでなく「現在どちらの手番か」という情報が必要なので、それも構造体の定義に含めることになります。

また、「現在何手進んだか」という情報もあると便利です。主にAIについて。

それは次回にします。

今回は、ビットボードという考え方を用いて、オセロの盤面を64ビット変数2つで表現しました。

次回は局面の構造体に手番と手数の情報を導入して、ひとまず局面の表現を完成させます。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする