リバーシ（オセロ）のプログラムを最初に作ったのは5年以上前なのですが、解説したことがなかったのでメモがてら書いてみます。ただし、自分のプログラムではbitboardを使っていません。やや初心者向けの記事になるので、本格派を目指す方はご容赦ください。
なお、「オセロ」と言えば超有名なボードゲームですが、オセロという語句は株式会社メガハウスの商標です。という訳で今から扱うゲームは、ルール的にはオセロなのですが、名称としては「リバーシ」と統一して呼ぶことにします。
これまでに作ったプログラム
Processingという言語でリバーシのプログラムを作っていました。対戦相手も実装していて、以下のOpenProcessingというサイトで対戦できます。プレイするだけでなくコードも全文見られます。過去に色んな人と戦ってもらいましたが、人間相手なら大体勝てるくらいには強いと自負しています。
Reversi P5 (20180224)
また、人対人のプレイができるだけの、最低限のルールを実装したプログラムもあります。こちらはコメントや空白を除けば、全部で150行くらいでしょうか。今回はこの単純なプログラムを軸にして、リバーシのプログラミングを考えていきます。
Simple reversi (2 player)
人対人用の単純なプログラムは、念のため下にも書いておきます。これでリバーシのルール通りに打つことができます。特にライブラリは使っていないので、Processingはどのバージョンでも動くと思います。
int board[][] = new int[10][10]; //盤面の記録用
int bw; //石の色。先手(黒石)は1、後手(白石)は-1
int pass,side; //パスの回数、1マスの長さ
int num0,numB,numW; //石を打てる所の数、黒石の数、白石の数
void setup(){
size(400, 400); //w=8*side, h=8*side
side=height/8; //1マスの長さ
startPosition(); //初期設定
showBoard(); //盤面を描画
}
void draw(){
passCheck(); //パスの判定（終局判定もする）
}
void mousePressed(){
int i = floor(mouseX/side +1); //各マスの左上の座標を定義
int j = floor(mouseY/side +1); //floor()で小数点以下切り捨て
//クリックしたマスに石を打てる時
if (validMove(i,j)){
movePiece(i,j);
bw = -bw; //石の色を反転
showBoard(); //盤面を描画する関数の呼び出し
}
}
//最初からやり直し
void keyPressed() {
if (key=='r') {
startPosition();
showBoard();
}
}
//初期設定
void startPosition() {
bw=1; //先手(黒石)は1、後手(白石)は-1
//石の初期配置を指定
for (int i=0;i<=9;i++){
for (int j=0;j<=9;j++){
if ((i==4&&j==5) || (i==5&&j==4)) {board[i][j]=1;} //黒は1
else if ((i==4&&j==4) || (i==5&&j==5)) {board[i][j]=-1;} //白は-1
else if (i==0||j==0||i==9||j==9) {board[i][j]=2;} //外縁は2
else {board[i][j]=0;} //空マスは0
}
}
}
//盤面、両者の石を描画
void showBoard(){
//盤面(背景とグリッド)
background(0,160,0);
stroke(0);
for (int i=1;i<=8;i++){
line(i*side,0, i*side,height); //縦線
line(0,i*side, 8*side,i*side); //横線
}
//石を描画、合法手にマーク
noStroke();
num0=numB=numW=0; //打てる所と両者の石数を数える
for (int i=1;i<=8;i++){
for (int j=1;j<=8;j++){
if (board[i][j]==1){ //黒(1)
fill(0);
ellipse((i-1)*side +side/2, (j-1)*side +side/2, 0.9*side, 0.9*side);
numB++;
}
else if (board[i][j]==-1){ //白(-1)
fill(255);
ellipse((i-1)*side +side/2, (j-1)*side +side/2, 0.9*side, 0.9*side);
numW++;
}
else if (validMove(i,j)){ //合法手
pass=0; //パスの回数を元に戻す
num0++; //合法手数を数える
if(bw==-1){fill(255, 255, 255, 200);}
else if(bw==1){fill(0, 0, 0, 200);}
ellipse((i-1)*side +side/2, (j-1)*side +side/2, side/3, side/3);
}
}
}
}
//マスの周囲8方向を調べ、石を打てるか判定
boolean validMove(int i, int j){
if(i<1||8<i || j<1||8<j){return false;} //盤外には打てない
if (board[i][j]!=0) {return false;} //空マスでなければ打てない
//注目するマスの周囲8方向に対し、石を打てるか調べる
int ri, rj; //調べるマスを移動させるのに使う変数
for (int di=-1; di<=1; di++){ //横方向
for (int dj=-1; dj<=1; dj++){ //縦方向
ri=i+di; rj=j+dj; //調べるマスの初期値
//調べるマスが「相手の石」ならループ
while (board[ri][rj]==-bw){
ri+=di; rj+=dj; //次のマスに移動
//同色の石に出会った(打てると分かった)時
if (board[ri][rj]==bw){return true;} //打てると判定
}
}
}
return false; //打てないと判定
}
//石を打ち、マスの周囲8方向の返せる石を反転
void movePiece(int i, int j){
board[i][j] = bw; //石を打つ
int ri, rj; //調べるマスを移動させるのに使う変数
for (int di=-1; di<=1; di++){ //横方向
for (int dj=-1; dj<=1; dj++){ //縦方向
ri=i+di; rj=j+dj; //調べるマスの初期値を与える
//調べるマスが「相手の石」ならループ
while (board[ri][rj]==-bw){
ri+=di; rj+=dj; //次のマスに移動
//同色の石に出会った時、打った石まで戻りつつ間の石を反転
if (board[ri][rj]==bw){
ri-=di; rj-=dj; //1マス戻る
while (!(i==ri&&j==rj)){ //元のマスに戻るまで
board[ri][rj] = bw; //自分の石にする(石を返す)
ri-=di; rj-=dj; //また1マス戻る
}
}
}
}
}
}
//パスの判定
void passCheck(){
//打てる所が無ければ自動でパス
if (num0==0 && pass<=1){
pass++; //パスの回数を数える
bw = -bw; //石の色を反転
showBoard(); //盤面、両者の石、次の手番が置ける所を描画
}
//2回パスしたら勝敗を判定
if (pass==2){
fill(255,0,0);
textSize(1.0*side); //文字の大きさ
textAlign(CENTER);
if (numW<numB){text("Black win", width/2,height/2);} //黒が多い時
else if (numB<numW){text("White win", width/2,height/2);} //白が多い時
else {text("Draw", width/2,height/2);} //引き分け
}
}
リバーシのルールを確認する
リバーシのプログラムを作るには、当然ながらリバーシのルールを正確に把握する必要があります。競技者向けのルール解説はたくさんありますが、プログラムを組む上では情報が足りないことも多いので、何かしらの方法でルールを確かめる必要があります。自分はリバーシの他に、チェッカーやチェスのプログラムも作りましたが、プログラムに落とし込む上での最初の壁は「正確なルールの把握」ではないかと思っています。
ちなみに、オセロとリバーシには一応違いがあります。オセロは「初期状態で石をクロスに配置する（かつ左下に黒石が来るようにする）」「先手は黒から打つ」といった細かい決まりがあるのに対し、リバーシはその辺が特に決まっていないようです。なので純粋にルールだけを比べると、リバーシのルールを精緻化したものがオセロであると言えそうです。
今回は日本オセロ連盟やOthello! JAPANなどを参考に、プログラムに必要そうなリバーシのルールを書き出してみます。
基本条件
・8×8マスの盤を使う。マスに対しては、左から右の行方向にa～f、上から下の列方向に1～8の番号が付いている。
→盤面を表現するための配列が必要そう。2次元配列を使うと簡単そう。
・初期状態で、d5とe4のマスには黒石、d4とe5のマスには白石が置かれている。その他は空きマス。
→盤面を表現する配列に、石の初期配置を設定する必要がありそう。
・プレイヤーは2人（先手が黒、後手が白）で、盤上に石を交互に打つ。
→手番を表現するための変数が必要そう。
ゲームの進行
・プレイヤーは、盤上の空きマスのうち、自分の石で相手の石を挟める位置だけに石を打てる。
→石を打とうとしているマスが空きマスで、かつ自分の石で相手の石を挟めるかを確認する関数が必要そう。
・プレイヤーが石を打ったら、自分の石で挟んだ相手の石は、全て自分の石の色になる。
→石を打った後、挟んだ相手の石を自分の石に変える関数が必要そう。
・自分の合法手（石を打てる場所）がない時にはパスをして、相手が続けて石を打つことができる。
→合法手が無かったらパスの処理をする関数が必要そう。
終局
・2人のプレイヤーが互いに打つ場所が無くなったら終局する。この時に、盤上にある石の枚数が多い方を勝ちとする。
→終局判定と勝敗判定をする関数が必要そう。
人対人用プログラムの解説
複数の関数から呼び出せるグローバル変数
まずは、複数の関数から呼び出せるグローバル変数たちです。
int board[][] = new int[10][10]; //盤面の記録用
int bw; //石の色。先手(黒石)は1、後手(白石)は-1
int pass,side; //パスの回数、1マスの長さ
int num0,numB,numW; //石を打てる所の数、黒石の数、白石の数
流儀は色々ありますが、自分は盤面の情報を保存するのに、board[][]という10×10の2次元配列を使っています。「盤面は8×8なのに、10×10の配列を使ってるのは何故？」となると思いますが、合法手の判定で便利だったり、マスの番号を数えやすかったりするので、個人的にそうしています。
また、手番の情報はbwという変数で表し、先手(黒石)は1、後手(白石)は-1と定義しています。黒が0で白が1とかでも良いのですが、手番を変える時に「bw = -bw;」と1行で書けたり、盤面の情報と関連付けやすかったりするので、1と-1で手番を表しています。
また、変数passはパスの回数を数えるのに使っています。ある局面でパスと判定されたらpass=1になり、手番を交代してもパスであればpass=2となり、終局と判定されます。また、ある局面で合法手があればpass=0にリセットする必要があります。
setup()関数で初期状態を設定
setup()関数では主に、startPosition()関数を呼んでゲームの初期設定をした後、showBoard()関数で盤面を描画しています。
void setup(){
size(400, 400); //8*side, h=8*side
side=height/8; //1マスの長さ
startPosition(); //初期設定
showBoard(); //盤面を描画
}
startPosition()では、まず「bw=1;」と書いて、手番が先手の黒（1）から始まることを宣言しています。
次に、board[][]に盤面の初期配置を定義しています。まず、d5とe4のマスには黒石（1）、d4とe5のマスには白石（-1）を置きます。そしてこのプログラムでは、8×8マスの盤面の外縁領域（2）も作っています。この領域は必ずしも必要ではないと思いますが、盤面の「壁」に当る領域を作っておくと、着手処理などをする際に便利だと思います。そして、その他のマスは空きマス（0）と定義しています。
//初期設定
void startPosition() {
bw=1; //先手(黒石)は1、後手(白石)は-1
//石の初期配置を指定
for (int i=0;i<=9;i++){
for (int j=0;j<=9;j++){
if ((i==4&&j==5) || (i==5&&j==4)) {board[i][j]=1;} //黒は1
else if ((i==4&&j==4) || (i==5&&j==5)) {board[i][j]=-1;} //白は-1
else if (i==0||j==0||i==9||j==9) {board[i][j]=2;} //外縁は2
else {board[i][j]=0;} //空マスは0
}
}
}
showBoard()は、基本的には地道に盤面を描いてるだけです。ただ、石を描くついでに両者の石の枚数（numB、numW）と、手番のプレーヤーの合法手数（num0）を数えているのが重要です。合法手数は手番が来るたびに数えておかないと、パスと終局の判定をすることができません。また、石の枚数も数えておかないと、勝敗の判定をすることができません。合法手かどうかの判定でvalidMove(i,j)という関数を作ってますが、これは後で解説します。
//盤面、両者の石を描画
void showBoard(){
//盤面(背景とグリッド)
background(0,160,0);
stroke(0);
for (int i=1;i<=8;i++){
line(i*side,0, i*side,height); //縦線
line(0,i*side, 8*side,i*side); //横線
}
//石を描画、合法手にマーク
noStroke();
num0=numB=numW=0; //打てる所と両者の石数を数える
for (int i=1;i<=8;i++){
for (int j=1;j<=8;j++){
if (board[i][j]==1){ //黒(1)
fill(0);
ellipse((i-1)*side +side/2, (j-1)*side +side/2, 0.9*side, 0.9*side);
numB++;
}
else if (board[i][j]==-1){ //白(-1)
fill(255);
ellipse((i-1)*side +side/2, (j-1)*side +side/2, 0.9*side, 0.9*side);
numW++;
}
else if (validMove(i,j)){ //合法手
pass=0; //パスの回数を元に戻す
num0++; //合法手数を数える
if(bw==-1){fill(255, 255, 255, 200);}
else if(bw==1){fill(0, 0, 0, 200);}
ellipse((i-1)*side +side/2, (j-1)*side +side/2, side/3, side/3);
}
}
}
}
mousePressed()で石を打つ
mousePressed()はウィンドウをクリックした時の動作です。まず、プレイヤーがクリックした画面の位置（mouseX、mouseY）から、盤面上のマスの位置を割り出します（i、j）。そして、クリックしたマスの位置が分かったら、validMove(i,j)という関数でそのマスに石を打てるか判定します。石を打てる場合は、movePiece(i,j)という関数で着手の処理を行い、手番を交代させて（bw = -bw）、盤面を描画し、次の着手を待つ状態にします。
void mousePressed(){
int i = floor(mouseX/side +1); //各マスの左上の座標を定義
int j = floor(mouseY/side +1); //floor()で小数点以下切り捨て
//クリックしたマスに石を打てる時
if (validMove(i,j)){
movePiece(i,j);
bw = -bw; //石の色を反転
showBoard(); //盤面を描画する関数の呼び出し
}
}
validMove(i,j)は受け取ったマスの座標を基に、石を打てるかどうか判定する関数です。まず最初の2行では、石を打てないことが即座に分かる場合の判定を書いています。
重要な部分は次ですが、クリックしたマスの周囲8方向に対して石を辿っていき、相手の石が続いた後に自分の石があるかどうかを調べています。例えば(di,dj)=(0,-1)の場合には、クリックしたマスから上方向に石を辿り、自分の石で相手の石を挟める配置になっているか確認します。
なお、盤面には外縁領域（2）を作っていましたが、この領域があることで下の着手判定が機能しています。もっと上手い方法もありそうですが……。
//マスの周囲8方向を調べ、石を打てるか判定
boolean validMove(int i, int j){
if(i<1||8<i || j<1||8<j){return false;} //盤外には打てない
if (board[i][j]!=0) {return false;} //空マスでなければ打てない
//注目するマスの周囲8方向に対し、石を打てるか調べる
int ri, rj; //調べるマスを移動させるのに使う変数
for (int di=-1; di<=1; di++){ //横方向
for (int dj=-1; dj<=1; dj++){ //縦方向
ri=i+di; rj=j+dj; //調べるマスの初期値
//調べるマスが「相手の石」ならループ
while (board[ri][rj]==-bw){
ri+=di; rj+=dj; //次のマスに移動
//同色の石に出会った(打てると分かった)時
if (board[ri][rj]==bw){return true;} //打てると判定
}
}
}
return false; //打てないと判定
}
movePiece(i,j)は自分の石を置いた後に、自分の石で挟まれた相手の石を自分の色に変える関数です。着手判定の関数validMove()とかなり似た処理をしています。他の方のプログラムでは、着手判定の際にひっくり返す石の位置を保存して、効率的に着手処理をしているものもあった気がします。効率を追い求めるならbitboardを使うべきでしょう。
//石を打ち、マスの周囲8方向の返せる石を反転
void movePiece(int i, int j){
board[i][j] = bw; //石を打つ
int ri, rj; //調べるマスを移動させるのに使う変数
for (int di=-1; di<=1; di++){ //横方向
for (int dj=-1; dj<=1; dj++){ //縦方向
ri=i+di; rj=j+dj; //調べるマスの初期値を与える
//調べるマスが「相手の石」ならループ
while (board[ri][rj]==-bw){
ri+=di; rj+=dj; //次のマスに移動
//同色の石に出会った時、打った石まで戻りつつ間の石を反転
if (board[ri][rj]==bw){
ri-=di; rj-=dj; //1マス戻る
while (!(i==ri&&j==rj)){ //元のマスに戻るまで
board[ri][rj] = bw; //自分の石にする(石を返す)
ri-=di; rj-=dj; //また1マス戻る
}
}
}
}
}
}
draw()でパス判定と終局判定
毎描画時に実行されるdraw()では、現局面におけるパスを判定します。石を打った時にパスの判定をすれば良いようにも思いますが、プレイヤーが互いに打てない場合（終局時）には、パスの判定を自動で進めてほしいので、draw()の中にパスの判定を書いています。
void draw(){
passCheck(); //パスの判定（終局判定もする）
}
まず前提として、合法手が無い（num0==0）場合にパスをして、パスの回数をカウントします（pass++;）。num0は盤面を描画するshowBoard()内で更新してるので、関数の役割をあまりきちんと分離できてないのですが、大目に見てください（誰か直して！）。
pass==2になったら石数の差を数えて試合結果を描画します。
//パスの判定
void passCheck(){
//打てる所が無ければ自動でパス
if (num0==0 && pass<=1){
pass++; //パスの回数を数える
bw = -bw; //石の色を反転
showBoard(); //盤面、両者の石、次の手番が置ける所を描画
}
//2回パスしたら勝敗を判定
if (pass==2){
fill(255,0,0);
textSize(1.0*side); //文字の大きさ
textAlign(CENTER);
if (numW<numB){text("Black win", width/2,height/2);} //黒が多い時
else if (numB<numW){text("White win", width/2,height/2);} //白が多い時
else {text("Draw", width/2,height/2);} //引き分け
}
}
プログラムの解説はひとまず以上です。プログラミングに慣れてきて、少し難しそうなことをやろうしていた当時の自分には丁度よかったです。
リバーシプログラミングのススメ（余談）
ボードゲームのプログラムを作りたい人にはリバーシがお勧めだよという話です。マニアックな話が多いですが、興味ある方はどうぞ。
リバーシの便利な特徴
ゲーム理論において、リバーシは「二人零和有限確定完全情報ゲーム」という分類にくくられます。長い用語が出てきましたが、分解して見ていくとこんな感じ。
・二人： プレイヤーが二人。
・零和： プレイヤーの勝敗を得点付けした時に、プレイヤーの得点の総和がゼロ（勝ちは1、負けは-1）。
・有限： 有限回の着手でゲームが終わる。
・確定： ゲームを進行する上で偶然性が入らない（サイコロを使うバックギャモンは未確定ゲーム）。
・完全情報： プレイヤーがゲームの情報を全て得られる（場札や手札を隠すポーカーは不完全情報ゲーム）。
このリバーシと同じ仲間のゲームとしては、チェッカー、連珠、チェス、将棋、囲碁などがあります。これらはゲーム理論の文脈で一緒くたに話されたりもしますが、リバーシは他のゲームには無い特徴があります。それは「必ず60手以内にゲームが終わる」ということです。リバーシは、一手ごとに盤面を石で埋めていくゲームです。8×8=64マスには初期配置で石が4つ置かれているので、最大でも60手で必ずゲームが終わります。単に「有限」であるよりも強力な特徴を持っている訳です。この点はプログラムを組んでいく上では、ありがたい特徴だと思います。
一方で、チェッカーやチェスは駒が後ろにも進めるため、同じ陣形を繰り替えす「同形反復」が起きてしまいます。そのため、有限回の着手でゲームを終わらせるには、「千日手の引き分け」などのルールが必要になります。「同形反復」を認めるチェッカーやチェスのプログラムも作れますが、それだといつまでもゲームが終わらなくて萎えます（コンピューターが同じ場所を行き来する手を指したら嫌ですよね？）。ボードゲームの有限性については下のブログも面白いです。
将棋は本当に「二人零和有限確定完全情報ゲーム」なのか？ 後編
###チェッカーの場合：派生ルールが多くて少し面倒
チェッカーはあまり馴染みのない人が多いかもしれませんが、情報学的には2007年に完全解析され、最善手で引き分けになると判明したことで有名なゲームです。そんなチェッカーですが、世界的に見ると多くの派生ルールがあります。
ポイントはいくつかありますが、「盤面サイズが8×8か10×10か」「駒を取る時に後ろにも進めるか」「駒を取れる時は最も取る手を指すことを強制されるか」などがあります。自分がチェッカープログラムを作った時はこの辺をどうするかも悩みましたが、個人的に馴染みのあったアメリカ式（イギリス式）チェッカーでプログラムを作りました。でも日本の大会を見ていると、ドラフツ（国際チェッカー）と呼ばれるゲームの方が熱気があるようです。ドラフツも作れるなら作りたいのですが……。なかなか思うようにいってません。
それに引き換え、リバーシのいかに気楽なことか！
チェスの場合：変則ルールが少し面倒
チェスは駒の種類が複数あり、飛び道具的な動き方をするので、その分プログラムは複雑になります。また、チェス初心者を困らせそうなルールで、「キャスリング」や「アンパッサン」などがあります。こういうルールをプログラミングで組み込もうとすると、全然思ったように動かなくて割と死にたくなります。まあ将棋と比べれば簡単だと思いますが……。
それに引き換え、リバーシのいかに気楽なことか！
将棋の場合：取った駒の処理が面倒、未確定のルールが面倒
将棋は、駒の種類が多い上に、取った相手の駒を自分の駒として使えるので、その分プログラムは複雑になります。「それくらいは知ってる」という人も多いと思いますが、では「最後の審判」という詰将棋についてはどうでしょうか。この詰将棋は単なるクイズに留まらず、将棋のルールの欠陥を突いている点で特徴的です。
将棋のルール上、この詰将棋が成立するかどうかはまだ正確な見解が示されていません。これはプログラムを作る上では困る所です。実際の所、「最後の審判」の終局図をどちらの勝ちとみるかは、将棋ソフトの中でも判定が分かれるそうです。しかし、とにもかくにも将棋プログラムを作るのであれば、「最後の審判」に対してどのような判定を与えるかも考慮することになるでしょう。まあ気にしない人も多いでしょうけど（NHK杯とかでこの局面を再現したら、流石にルールが確定すると思いますが、誰か話題集めでやってくれないかなあ）。
それに引き換え、リバーシのいかに気楽なことか！
囲碁の場合：まともに終局させるのが面倒、局面数が多すぎて面倒
囲碁と言えば、DeepMind社のプログラムがトッププロを鮮やかに打ち負かしたニュースもあり、「囲碁も大したことないじゃん」みたいな空気を感じることが時々あります。しかしこのゲーム、遊んだことがある人は分かると思いますが、二眼を作ったりパスも使いこなさないと、ごそっと石を取られてまともに終局しないですよね。人対人のプログラムを作るだけならまだ単純ですが、そこから進んで対戦相手を作ろうと思うと、途方もない感じがします。
そして、19×19の盤面も大きすぎるように感じます。自分が作るなら9路盤しか考えたくないですね……。対戦相手も作るとなると、評価関数が有効でないというのも痛いです。モンテカルロ木探索は評価関数の手法が不要ということで魅力も感じますが、こちとらずっとアルファベータ探索しか知らないのに、今さらモンテカルロ木探索の内容など頭に入らないのですよ、ええ。
それに引き換え、リバーシのいかに気楽なことか！
締め
今回は人対人用の単純なプログラムを解説しましたが、プログラムの中身をただ追うだけの内容になってしまいました。興味ある方がいれば、もう少し丁寧な解説も書いてみたいと思います。あと手厳しい意見もお待ちしています。