#include #include #include #include #include "mt.h" // 中身はMersenne Twisterのmain以外 // 盤面の状態などを表す定数。 #define NONE 0 // 空いてる状態 #define BLACK 1 // 黒石, 黒番 #define WHITE 2 // 白石, 白番 #define BORD 3 // 枠外 #define N 8 // 1辺Nの盤面を考える #define NN ((N + 1) * (N + 2) + 1) // 用意する配列の範囲 #define TTIMES 100000 // 後述 /* ........................................................ board[] の形で出てくる char 配列が盤面のどこを指すかを 示す。一般形を示すのは辛いので N=8 の場合。四角く囲った 内側が盤面の 8x8 の範囲。 枠外↓ ←盤面がある横の範囲 → ↓枠外 0 1 2 3 4 5 6 7 8 9 ←枠外 _________________________ 9|10 11 12 13 14 15 16 17|18 ↑ 18|19 20 21 22 23 24 25 26|27 盤 27|28 29 30 31 32 33 34 35|36 面 36|37 38 39 40 41 42 43 44|45 縦が 45|46 47 48 49 50 51 52 53|54 のあ 54|55 56 57 58 59 60 61 62|63 範る 63|64 65 66 67 68 69 70 71|72 囲 72|73 74 75 76 77 78 79 80|81 ↓ ~~~~~~~~~~~~~~~~~~~~~~~~~ 81 82 83 84 85 86 87 88 89 90 ←枠外 [9の倍数]には1マスで左右の枠外を両方とも担って貰ってる。 どうせ右も左も関係ないので。 .......................................................... */ // -------------------------------------------------------------- // グローバル変数(引数にするのが面倒だった変数) // -------------------------------------------------------------- double branch; // 分岐数の積 // -------------------------------------------------------------- // プロトタイプ宣言 // 中身で何をやってるかは実体で書くのでここでは省略 // -------------------------------------------------------------- void printboard(char[]); void search(char[],char); void turn(char[],int,char); void init(char[]); int putalbe(char[],int,char); // ============================================================== // turn : 現在の盤面に石を打つ。返せる石が無い場合には打たないまま // 終わる。board[place] が空きマスであることを前提としてる。 // char board[] : Input/Output : 盤面の状態 // int place : Input : 次に石を打つ所 // char color : Input : 次に打つ石の色 // ============================================================== void turn(char board[], int place, char color) { static int move[] = {-N-2,-N-1,-N,-1,1,N,N+1,N+2}; // 動く差分 int i, p, flag; char enemy; enemy = BLACK + WHITE - color; // 相手の色 flag = 0; // 結局返せるのかどうかのフラグ for( i = 0 ; i < 8 ; i++ ) { p = place + move[i]; if( board[p] != enemy ) continue; // 隣接セルが相手でなければダメ for( p += move[i] ; board[p] == enemy ; p += move[i] ) ; if( board[p] == color ) { // 挟める for( p -= move[i] ; board[p] == enemy ; p -= move[i] ) // 石を返す board[p] = color; flag = 1; // 返したという証拠 } } // 石を返せた場合だけ、指定箇所に石を打つ if( flag ) board[place] = color; } // ============================================================== // putable : 現在の盤面の指定箇所石を打てるかどうか判定 // char board[] : Input : 盤面の状態 // int place : Input : 石を打ちたい所 // char color : Input : 打つ石の色 // return value : Output : 打てる場合は1, 打てない場合は0 // ============================================================== int putable(char board[], int place, char color) { static int move[] = {-N-2,-N-1,-N,-1,1,N,N+1,N+2}; // 動く差分 int i, p; char enemy; if( board[place] != NONE ) return 0; // 空きマスでなければ打てない enemy = BLACK + WHITE - color; for( i = 0 ; i < 8 ; i++ ) { p = place + move[i]; if( board[p] != enemy ) continue; // 隣接セルが相手でなければダメ for( p += move[i] ; board[p] == enemy ; p += move[i] ) ; // 相手の石を辿った先に自分の石があれば返せる if( board[p] == color ) return 1; } return 0; // どの方向も返せない場合は打てない } // ============================================================== // search : (1)打てる箇所を数え、積を取る (2)ランダムに打つ // char board[] : Input : 盤面の状態 // char color : Input : 打つ石の色 // ============================================================== void search(char board[], char color) { int numPut, i, pass, pPut[N*N-4]; char enemy; numPut = 0; // 置ける場所の数 // パスの場合には再起せずにループ for( pass = 0 ; pass < 2 ; pass++, color = enemy ) { enemy = BLACK + WHITE - color; for( i = N + 2 ; i < (N + 1) * (N + 1) ; i++ ) { // 取りあえず全探索 if( putable(board, i, color) ) // 置ける位置だけ記録 pPut[numPut++] = i; } if( numPut ) break; // 1箇所でも置ければパスではない } // 終わってない場合は次の手を計算 if( pass != 2 ) { branch *= numPut; // 今回の分岐数を掛ける turn(board, pPut[genrand_int32() % numPut], color); // ランダムに石を打つ search(board, enemy); // 次の手を数える } } // ============================================================== // init : いろんな変数の初期化 // char board[] : Output : 盤面の状態 // ============================================================== void init(char board[]) { int i; // 盤面の初期化 for( i = 0 ; i < N + 2 ; i++ ) board[i] = BORD; // 上枠外 for( i = N + 2 ; i < (N + 1) * (N + 1) ; i++ ) board[i] = NONE; // 空きマス for( i = (N+1)*(N+1) ; i < NN ; i++ ) board[i] = BORD; // 下枠外 for( i = 0 ; i <= (N+1)*(N+1) ; i += N+1 ) board[i] = BORD; // 左右枠外 board[(N+2)*N/2] = board[(N+2)*(N/2+1)] = BLACK; // 黒石 board[(N+2)*N/2+1] = board[(N+2)*(N/2+1)-1] = WHITE; // 白石 // グローバル変数の初期化 branch = 1.0; } // ============================================================== // printboard : 盤面の状態を表示し、Enterキー入力まで待つ // デバグ用の関数なので実は呼び出されてない。 // char board[] : Input : 盤面の状態 // ============================================================== void printboard(char board[]) { int i; for( i = N + 2 ; i <= (N+1)*(N+1) ; i++ ) { putchar(".@O\n"[(int)board[i]]); // .は空きマス, @は黒, Oは白のつもり } puts(""); // 改行(盤面と盤面の間に隙間を加えるため) getchar(); // キー入力待ち。この行が無ければ盤面が流れる。 } int main(void) { int i, j; char board[NN]; double sum, dsum; init_genrand(time(NULL)); // 乱数の準備 sum = 0.0; for( i = 1 ; ; i++ ) { // 有限回にするときは適当に条件を。 // ここから実験 TTIMES 回分 dsum = 0.0; // 分岐数の積の和 for( j = 0 ; j < TTIMES ; j++ ) { // ここから実験1回分 init(board); // 状況を初期化 search(board, BLACK); // 探索する dsum += branch; // 分岐数の積を加える // ここまで実験1回分 } dsum *= (1.0 / TTIMES); // 平均値を出す sum += dsum; // ↑の平均値を出す。詳細は下に。 // TTIMES 回分の実験結果を出力 fprintf(stdout, "%9d %.0f %.0f\n", i * TTIMES, dsum, sum / i); // 指数(X.XXXXe+YY形式)での出力がいい方はこちら //fprintf(stdout, "%9d %.10e %.10e\n", i * TTIMES, dsum, sum / i); fflush(stdout); } return 0; } /* ................................................................... 見直しているとちょっと妙な平均の出し方をしている気がして、一応解説。 TTIMES 回の平均結果を1回の実験結果と見て、その平均を取っているわけ です。一応、素直に足して全体の実験回数で割ってもいいけど、この方法 だと32bitの範囲を超える回数も可能。 ..................................................................... */