今回はパズルではありませんが、簡単な思考ゲームを作ってみましょう。8 行 8 列の盤面に配置された数字を取り合って、合計点が多い方が勝ちというゲームです。名前はたしか MiniMax だったと思いますが、ちょっと記憶があやふやです。
ルールは簡単です。盤面には 1 から 9 までの + と - の数字がランダムに配置されています。最初、先手は 0 行目の中から数字を選びます。次の図を見てください。
5 -4 9 [6]-5 -3 -6 -9 ← 先手はこの行から選ぶ
2 -1 5 -1 8 3 -4 -6
9 8 -6 -5 2 7 -7 -1
3 3 9 5 -6 -1 3 -2
-2 1 -4 1 -9 -5 -6 -8
-9 -4 8 4 7 -2 -9 2
-8 -4 8 -5 1 -5 -5 1
1 2 5 -9 -5 -8 -7 -8
↑
└─────── 後手はこの列から選ぶ
図：MiniMax ゲーム進行(1)
盤面の行と列は、プログラムに合わせて 0 から数えることにします。先手は 0 行 3 列目 (0, 3) の 6 を選びました。後手が数字を選ぶ場合は、相手が選んだ数字と同じ列の中から選ばなければいけません。この場合は 3 列目から選ぶことになります。つまり、先手は相手が選んだ数字と同じ行から、後手は同じ列から数字を選ぶのです。あとはこれを交互に繰り返します。そして、行または列の数字が無くなったらゲーム終了です。次の図を見てください。
先手 7 点 : 後手 2 点
** ** ** ** ** -3 ** **
** ** ** ** ** 3 -4 **
** ** -6 -5 ** ** ** **
3 3 9 5 -6 -1 3 -2
-2 ** -4 ** -9 -5 -6 -8
-9 [4] 8 4 ** -2 -9 ** ← 先手は 4 を選ぶ
-8 ** ** ** ** -5 ** **
** ** ** -9 ** -8 ** **
↑
└─────── 後手は 3 を選びゲーム終了
図：MiniMax ゲーム進行(2)
先手が 7 : 2 で勝っている状況です。ここで、5 行目から数字を選びますが、1 列目の 4 を選ぶと、その列には数字が 3 のひとつしか残りませんね。したがって、後手は 3 を選ぶしかなく、ここでゲームが終了します。11 : 5 で先手の勝ちとなります。
このゲームは単純なので、思考ルーチンも簡単に作ることができます。思考ルーチンの基本アルゴリズム ミニマックス法 を使って数手先読みするだけで、ほとんどの人は勝てなくなるでしょう。
とりあえず、DOS 窓で動作するプログラムをＣ言語で作りました。GUI ではないので、操作は面倒だとは思いますが、興味のある方は遊んでみてください。そのうちに Tcl/Tk 版でも作りましょう。思考ルーチンの強さはレベル 1 から 6 までの 6 段階あり、オプションスイッチ -L で指定することができます。デフォルトではレベル 3 です。
それではプログラムを説明しましょう。最初に盤面を表すデータ構造を定義します。リバーシなどのボードゲームの場合、1 次元配列を使って盤面を表した方が便利なのですが、今回は簡単に 2 次元配列を使います。そして、この配列をグローバル変数として定義します。
リスト：グローバル変数の定義 int board[SIZE][SIZE]; /* ８行８列 */ int first_value = 0; int last_value = 0; int depth = 3; /* 先読みの手数(default) */
この方法では、先読みするときに盤面を直接書き換えるため、先読みした局面から前の局面に戻す処理が必要になります。このほかに、盤面を局所変数として表す方法もあります。この場合、先読みするたびに局面をコピーしなければいけません。そのかわり、元に戻す処理は不要になります。
たとえば「ＫＡＬＡＨ（カラー）」のように、1 手指すたびに盤面の大部分が変化するようなゲームでは、盤面を局所変数として定義すればいいでしょう。また、今回のゲームのように、盤面の一部分しか変化しないゲームでは、グローバル変数として定義するのがふつうです。
あと、先手と後手の点数を first_value と last_value で表します。これらの値も先読みするときに書き換えらるので、元の値に戻す処理が必要になります。depth が先読みの手数を表します。たとえば、デフォルトの 3 であれば「自分−相手−自分」の 3 手分先読みします。
次は、指し手を選ぶ処理を作りましょう。この処理は、ゲームの木を深さ優先で探索して、ミニマックス法で指し手を選びます。
リスト：先手の選択
int select_first( int his, int prev_move, int *move )
{
if( his == depth ){
return first_value - last_value; /* 先読み終了 */
} else {
int x;
int py = GET_Y( prev_move );
int value = NO_VALUE;
for( x = 0; x < SIZE; x++ ){ /* 先手は横方向 */
if( board[x][py] != NO_VALUE ){
int v, m;
int save_board = board[x][py];
int save_value = first_value;
first_value += board[x][py];
board[x][py] = NO_VALUE;
if( check_finish( x, py ) ){
v = finish_value(); /* 終了 */
} else {
v = select_last( his + 1, MAKE_XY( x, py ), &m );
}
/* 単純なミニマックス -- 大きい方を選ぶ */
if( value == NO_VALUE || v > value ){
value = v;
*move = MAKE_XY( x, py );
}
board[x][py] = save_board; /* 盤面を元に戻す */
first_value = save_value;
}
}
return value;
}
}
select_first は先手の指し手を選択します。後手の指し手を選択する関数が select_last です。選んだ指し手は引数 *move に格納し、そのときの評価値を返します。引数 his が先読みの深さを表し、prev_move は相手の指し手を表します。下位 8 ビットが行 ( y ) の位置、上位 8 ビットが列 ( x ) の位置を表しています。この値を取り出すためマクロ GET_X, GET_Y を、また値を生成するためマクロ MAKE_XY を定義して使っています。
his が depth に達したら先読みは終了です。そのときの局面を評価します。評価関数はとても簡単で、first_value と last_value の差を求めるだけです。したがって、値がプラスであれば先手が有利、マイナスになれば後手が有利となります。こんな単純な評価関数だからといって、甘く見てはいけません。先読みの手数を増やすだけで、思考ルーチンはぐっと強くなります。
探索の途中であれば、盤面から数字を選んで後手側の選択処理を呼び出します。数字を取り除いた場所には NO_VALUE が格納されているので、それ以外の場所から数字を取り出します。このとき、盤面の値を元に戻すため、取り出した数字と先手の値 first_value を保存しておきます。関数 check_finish はゲームの終了をチェックします。そのときの評価値は finish_value で計算します。ゲームが終了していなければ、後手の選択処理 select_last を呼び出します。どちらの評価値も変数 v に格納します。
次の処理がミニマックス法の心臓部です。先手は評価値の大きい方が有利なわけですから、いちばん大きな評価値（マックス）の指し手を選びます。選んだ指し手は *move に格納し、その評価値は value に格納しておきます。評価値 v が value よりも大きい値であれば、その指し手を選べばいいわけです。あとは、すべての指し手を調べるだけです。後手側の選択処理ならば、逆にいちばん小さな評価値（ミニマム）の指し手を選択すればいいのです。ミニマックス法の処理はたったこれだけです。とても簡単ですね。
まだ指し手を選んでいない場合、value は NO_VALUE に初期化されているので、最初に調べた指し手がセットされます。この処理は value の初期値を工夫すると省略することができます。これはαβ枝刈りを実装するときに改良することにしましょう。それから、次の指し手を調べる前に、盤面の状態を元に戻すことをお忘れなく。
ゲーム終了のチェックは簡単です。取った数字の位置の行と列をチェックするだけです。
リスト：終了のチェック
int check_finish( int x, int y )
{
int i, xf = 0, yf = 0;
/* 縦、横で数字が無くなったか */
for( i = 0; i < SIZE; i++ ){
if( board[x][i] != NO_VALUE ) xf = 1;
if( board[i][y] != NO_VALUE ) yf = 1;
}
if( xf == 0 || yf == 0 ) return TRUE;
return FALSE;
}
とくに難しいところはないですね。終了時の評価値は、通常の評価値よりも大きな値を返します。
リスト：終了時の評価値
int finish_value( void )
{
if( first_value > last_value ){
/* 先手の勝ち */
return MAX_VALUE + first_value - last_value;
} else if( first_value < last_value ){
/* 後手の勝ち */
return MIN_VALUE + first_value - last_value;
} else {
/* 引き分け */
return 0;
}
}
先手が勝ちの場合は MAX_VALUE(1000) より大きな値、後手が勝ちの場合は MIN_VALUE(-1000) よりも小さな値を返します。通常の評価値 first_value - last_value を返すと、勝負がついていない局面の評価値の方を選択する場合があり、ズルズルとゲームが続いてしまうのです。特別な値を返すことにより、ミニマックス法の中で勝敗がつく指し手を選ぶことができます。
あとはゲームを進める処理を作るだけです。プログラムは次のようになります。
リスト：ゲームの進行
void play( void )
{
int prev_move = 0;
int turn = 1;
while( TRUE ){
int move, x, y;
if( turn & 0x01 ){ /* 先手 */
y = GET_Y( prev_move );
print_board( y );
move = input_number( y );
x = GET_X( move );
printf( "先手 (%d,%d) %d を選びます：", x, y, board[x][y] );
first_value += board[x][y];
} else { /* 後手(COM) */
select_last( 0, prev_move, &move );
x = GET_X( move );
y = GET_Y( move );
printf( "後手 (%d,%d) %d を選びます：", x, y, board[x][y] );
last_value += board[x][y];
}
board[x][y] = NO_VALUE;
prev_move = move;
printf("先手 %3d 点 : 後手 %3d 点 \n", first_value, last_value );
turn++;
if( check_finish( x, y ) ){
printf("試合終了\n");
break;
}
}
}
変数 turn で手番を表します。奇数のときは先手、偶数のときは後手となります。先手のときは人間側の入力を受け付けます。後手のときは select_last を呼び出して、ミニマックス法により指し手を選びます。この場合、指し手だけが必要なので評価値は使っていません。あとは指定された位置から数字を取り除き、ゲームの終了をチェックします。
ゲームの骨格となるプログラムを説明しました。詳細は プログラムリスト を読んでください。ミニマックス法はあまりに簡単だったので、拍子抜けされた方もいるでしょう。次回はαβ枝刈りを実装して、その効果を確認してみたいと思います。
/*
* minimax.c : 数字を取り合うゲーム
*
* Copyright (C) 2000 by Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <time.h>
/* 定数定義 */
#define TRUE 1
#define FALSE 0
#define SIZE 8
#define FIRST 0
#define LAST 1
#define RSIZE 256 /* リードバッファサイズ */
#define NO_LINE (-1)
#define NO_VALUE 10000
#define MAX_VALUE 1000
#define MIN_VALUE (-1000)
/* マクロ */
#define GET_X( c ) ((c)>> 8)
#define GET_Y( c ) ((c) & 0xff)
#define MAKE_XY( x, y ) (((x) << 8) + (y))
/* 関数宣言 */
int select_last( int his, int prev_move, int *move );
/* グローバル変数定義 */
int board[SIZE][SIZE]; /* ８行８列 */
int first_value = 0;
int last_value = 0;
int depth = 3; /* 先読みの手数(default) */
/* 盤面の初期化 */
void init_board( void )
{
int x, y;
for( x = 0; x < SIZE; x++ ){
for( y = 0; y < SIZE; y++ ){
int n = rand();
if( n > RAND_MAX / 2 ){
board[x][y] = - (n % 9 + 1);
} else {
board[x][y] = n % 9 + 1;
}
}
}
}
/* 盤面の出力 */
void print_board( int line )
{
int x, y;
printf(" ");
for( x = 0; x < SIZE; x++ ){
printf("%3d", x );
}
printf("\n --------------------------\n");
for( y = 0; y < SIZE; y++ ){
printf("%c ", ( line == y ? '[' : ' ' ) );
for( x = 0; x < SIZE; x++ ){
if( board[x][y] == NO_VALUE ){
printf( " **" );
} else {
printf( "%3d", board[x][y] );
}
}
printf(" %c", ( line == y ? ']' : ' ' ) );
printf("\n");
}
}
/****** 思考ルーチン ******/
/* 終了時の評価値 */
int finish_value( void )
{
if( first_value > last_value ){
/* 先手の勝ち */
return MAX_VALUE + first_value - last_value;
} else if( first_value < last_value ){
/* 後手の勝ち */
return MIN_VALUE + first_value - last_value;
} else {
/* 引き分け */
return 0;
}
}
/* 終了のチェック */
int check_finish( int x, int y )
{
int i, xf = 0, yf = 0;
/* 縦、横で数字が無くなったか */
for( i = 0; i < SIZE; i++ ){
if( board[x][i] != NO_VALUE ) xf = 1;
if( board[i][y] != NO_VALUE ) yf = 1;
}
if( xf == 0 || yf == 0 ) return TRUE;
return FALSE;
}
/* 先手の選択 */
int select_first( int his, int prev_move, int *move )
{
if( his == depth ){
/* 先読み終了 */
return first_value - last_value;
} else {
int x;
int py = GET_Y( prev_move );
int value = NO_VALUE;
/* 先手は横方向 */
for( x = 0; x < SIZE; x++ ){
if( board[x][py] != NO_VALUE ){
int v;
int m;
int save_board = board[x][py];
int save_value = first_value;
first_value += board[x][py];
board[x][py] = NO_VALUE;
if( check_finish( x, py ) ){
/* 終了 */
v = finish_value();
} else {
/* 後手番 */
v = select_last( his + 1, MAKE_XY( x, py ), &m );
}
/* 単純なミニマックス -- 大きい方を選ぶ */
if( value == NO_VALUE || v > value ){
value = v;
*move = MAKE_XY( x, py );
}
/* 盤面を元に戻す */
board[x][py] = save_board;
first_value = save_value;
}
}
return value;
}
}
/* 後手の選択 */
int select_last( int his, int prev_move, int *move )
{
if( his == depth ){
/* 先読み終了 */
return first_value - last_value;
} else {
int y;
int px = GET_X( prev_move );
int value = NO_VALUE;
/* 後手は縦方向 */
for( y = 0; y < SIZE; y++ ){
if( board[px][y] != NO_VALUE ){
int v;
int m;
int save_board = board[px][y];
int save_value = last_value;
last_value += board[px][y];
board[px][y] = NO_VALUE;
if( check_finish( px, y ) ){
/* 終了 */
v = finish_value();
} else {
/* 先手番 */
v = select_first( his + 1, MAKE_XY( px, y ), &m );
}
/* 単純なミニマックス -- 小さいを選ぶ */
if( value == NO_VALUE || v < value ){
value = v;
*move = MAKE_XY( px, y );
}
/* 盤面を元に戻す */
board[px][y] = save_board;
last_value = save_value;
}
}
return value;
}
}
/* 数値入力 */
int input_number( int y )
{
int pos;
char buffer[RSIZE];
printf("0 - 7 の数値を入力してください ");
for(;;){
if( fgets( buffer, RSIZE, stdin ) != NULL ){
if( sscanf( buffer, "%d", &pos ) == 1 ){
if( 0 <= pos && pos <= 7 ){
if( board[pos][y] == NO_VALUE ){
printf("%d には数字がありません\n", pos );
continue;
}
break;
}
}
}
printf("\n入力エラー：0 - 7 の数値を入力してください\n");
}
return MAKE_XY(pos, y);
}
/* ゲームの実行 */
void play( void )
{
int prev_move = 0;
int turn = 1;
while( TRUE ){
int move, x, y;
if( turn & 0x01 ){
/* 先手 */
y = GET_Y( prev_move );
print_board( y );
move = input_number( y );
x = GET_X( move );
printf( "先手 (%d,%d) %d を選びます：", x, y, board[x][y] );
first_value += board[x][y];
} else {
/* 後手(COM) */
select_last( 0, prev_move, &move );
x = GET_X( move );
y = GET_Y( move );
printf( "後手 (%d,%d) %d を選びます：", x, y, board[x][y] );
last_value += board[x][y];
}
board[x][y] = NO_VALUE;
prev_move = move;
printf("先手 %3d 点 : 後手 %3d 点 \n", first_value, last_value );
turn++;
if( check_finish( x, y ) ){
printf("試合終了\n");
break;
}
}
}
/* 引数解析 */
void getargs( int argc, char *argv[] )
{
int i;
for( i = 1; i < argc && argv[i][0] == '-'; i++ ){
int opt = toupper( argv[i][1] );
if( opt == 'L' ){
int lv = atoi( &argv[i][2] );
if( lv < 1 || lv > 6 ){
fprintf( stderr, "レベルは 1 - 6 を指定してください\n");
exit( EXIT_FAILURE );
}
depth = lv;
} else {
fprintf( stderr, "不正なオプションスイッチです\n" );
exit( EXIT_FAILURE );
}
}
}
int main( int argc, char *argv[] )
{
srand( time( NULL ) );
getargs( argc, argv );
init_board();
play();
return 0;
}