オセロ（リバーシ）の作り方 ～評価アルゴリズム～

このサイトでは、C言語でのオセロ（リバーシ）のプログラム開発方法を解りやすく説明しています。初級者、初心者でも作れるオセロ実装のコツが満載です。

もちろん、石の位置だけでは強いプログラムは作れません。強いプログラムを作るには、様々な多くの評価アルゴリズムを導入する必要があります。ここでは一般的なアルゴリズムの説明を行います。

ある盤面で自分の確定石が何個あるのかを調べるアルゴリズム

上の題に対してのプログラムを２ちゃんねるで発見しました。それが下のものです。

汚いですがどうぞ（Ｃ＋＋） 

bool SettledPiece(Piece* map,int mmm[100],int from,int to,int dir,int dir2) 
{ 
　if((mmm[from]|dir2)<255)return false; 
　if(map[from]==map[to]) 
　　mmm[to] |= (dir+dir2) & mmm[from]; 
　else if(map[from]==-map[to]) 
　　mmm[to] |= dir & mmm[from]; 
　else return false; 
　if((mmm[to]|dir2)==255) 
　　return true;//確定および 準確定 
　return false; 
} 

void CountSettledPiece(Piece* map,Piece p,int& mines,int& oppos){ 
　mines=0; 
　oppos=0; 
　static int mmm[100]; 
　int z; 
　for(z=0;z<100;z++){ 
　　mmm[z]=0; 
　} 
　for(z=1;z<9;z++)　{ 
　　mmm[z+10] |=1+2 +8+16+32 +128; 
　　mmm[z+80] |=1+2 +8+16+32 +128; 
　　mmm[z*10+1]|= 2+4+8 +32+64+128; 
　　mmm[z*10+8]|= 2+4+8 +32+64+128; 
　} 
　// 1北 2北東 4東 8南東 16南 32南西 64西 128北西 
　static Array<int> openlist; 
　static Array<int> nextopenlist; 
　if(map[11]!=Space) 
　　openlist.Assertz(11); 
　if(map[18]!=Space) 
　　openlist.Assertz(18); 
　if(map[81]!=Space) 
　　openlist.Assertz(81); 
　if(map[88]!=Space) 
　　openlist.Assertz(88); 
　while(openlist.Len()>0) 
　{ 
　　for(int i=0;i<openlist.Len();i++) 
　　{ 
　　　z=openlist[i]; 
　　　if(mmm[z]==255){ 
　　　　mmm[z]=511; 
　　　　if(map[z]==p)mines++; 
　　　　else if(map[z]==-p)oppos++; 
　　　} 
　　　if(SettledPiece(map,mmm,z,z-10,1,16))nextopenlist.Assertz(z-10); 
　　　if(SettledPiece(map,mmm,z,z+10,16,1))nextopenlist.Assertz(z+10); 
　　　if(SettledPiece(map,mmm,z,z-1,64,4))nextopenlist.Assertz(z-1); 
　　　if(SettledPiece(map,mmm,z,z+1,4,64))nextopenlist.Assertz(z+1); 
　　　if(SettledPiece(map,mmm,z,z-9,2,32))nextopenlist.Assertz(z-9); 
　　　if(SettledPiece(map,mmm,z,z+9,32,2))nextopenlist.Assertz(z+9); 
　　　if(SettledPiece(map,mmm,z,z-11,128,8))nextopenlist.Assertz(z-11); 
　　　if(SettledPiece(map,mmm,z,z+11,8,128))nextopenlist.Assertz(z+11); 
　　} 
　　openlist.Clear(); 
　　openlist.Append(nextopenlist); 
　　nextopenlist.Clear(); 
　} 
} 

void CountSettledPiece(Piece* map,Piece p,int& mines,int& oppos){ 
は確定石の数を数える関数です。局面が複雑になると数え間違いますので悪しからず。 
mapは盤面（点(x,y)はmap[x+y*10]） 
pは色 0無 1黒 -1白 2枠 
minesはpの確定石 
opposは-pの確定石 
英語がおかしいのは昔作ったため。 

Piece型 Space=0,Black=1,White=-1,Border=2 
Array<int> aは自作した一次元配列 
a.Assertz()は末尾に追加 
a.Clear()は全消去 
a.Append()は他の配列を末尾追加 

実際、確定石の実装は難しいようです。また、都度計算するのは時間が掛かる為あまり効率の良いものとは言えません。

確定石の計算は「辺の回り」だけで良いと思います。それだと速く、そして実装が簡単になります。ただ、弱い相手や強い相手と戦うと、悪手を打つことがあるようですが…。

辺の確定石の数計算方法

• まず石が隅に１つでもあるか調べる。（無ければ確定石は無い）
• 隅に石がある＆自分の石であれば、そこから辺の石の連続は確定石。
• 両隅に石＆相手の石の場合、途切れていなければその辺は確定石。

また、このアルゴリズムに、隅に石の無い辺の場合

• 石を数えて、辺に６つ同じ色の石があれば、「山」。
• 石を数えて、辺に５つ同じ色の石があれば、「ウィング」。
• １つしか無い＆その石はＣ打ち＆隣のＢ、Ａが空いている場合は単独Ｃ打ち

などと定義して加えておけば、一度に辺の評価も出来ます。

オススメ書籍

オセロに強くなりたい人は下記を読むことをお勧めします。

オセロ（将棋等）のプログラムを開発したい人・ゲームプログラマーになりたい人は下記は持っていて損はないでしょう。

ページの先頭へ移動