Shannonが1949年に書いた論文に"Programming a computer for playing chess"というChessをコンピュータに実行させるにはというものがある。
http://portal.acm.org/citation.cfm?id=61701.67002
ENIACができたのが1946年で、プログラム内蔵方式のEDVACが1949年から研究所に入ったという話なのでEDVACのテストして書いたプログラムの話かもしれない。
Shannonはこの論文で、MinMax手法、盤面評価、静止探索、機械学習の可能性といった現在でも基本となっている手法をすでに発表している。
彼の書いたプログラムがどんなものであったかは分からないが論文から再現してみるのは面白そうなので書いてみようと思った。
ただし、彼が用いたのがENIACだったとすると配線で、EDVACだったとするとマシン語であったろうが、それはハードルが高すぎるのでC++ではなくCという程度にする。
今回は全体の枠組みをとりあえず書いてみた。
#include
#include
#include
#include
#include
typedefstruct {
int from_x;
int from_y;
int to_x;
int to_y;
int piece;
} Move;
typedefstruct {
int board[8][8];
int side;
// castling is available?
int king_is_moved[2];
int rook_is_moved[2][2];
// last move
Move last_move;
// for 50 moves rule
int moves_after_pawn;
// next moves
Move next_moves[8]; // 8 Pawns
int num_moves;
} Position;
まだlast_moveやcastlingに関する情報は利用していないが、論文には必要だと書いてあったのでエントリーだけでも作っておく。
こういうところをみると実際に作ったなと感じる。
void InitPosition(Position*);
void CopyPosition(Position* dst, constPosition* src);
void PrintPosition(constPosition*);
void PrintMove(constMove*);
void DoMove(constPosition*, constMove*, Position*);
void CalcPawnMoves(Position*, int, int);
void CalcBishopMoves(Position*, int, int);
void CalcKnightMoves(Position*, int, int);
void CalcRookMoves(Position*, int, int);
void CalcQueenMoves(Position*, int, int);
void CalcKingMoves(Position*, int, int);
void CalcMoves(Position*);
void ReadMove(Move*);
int IsValidMove(constPosition*, constMove*);
int a2piece(char);
char piece2a(int);
void ThinkNextMove(Position*, Move*);
conststaticchar* PIECE_MARK = "kqrbnp.PNBRQK";
staticint init_board[] = {
4, 2, 3, 5, 6, 3, 2, 4,
1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
-1, -1, -1, -1, -1, -1, -1, -1,
-4, -2, -3, -5, -6, -3, -2, -4
};
初期レイアウトも論文のままに、この数字が盤面評価のスコアとして使われる。
staticPosition position[200]; // how many is needed?
void InitPosition(Position* pos) {
int x, y;
int i = 0;
for (y = 0; y < 8; ++y) {
for (x = 0; x < 8; ++x) {
pos->board[x][y] = init_board[i];
++i;
}
}
pos->side = 1;
for (int s = 0; s < 2; ++s) {
pos->king_is_moved[s] = 0;
pos->rook_is_moved[s][0] = 0;
pos->rook_is_moved[s][1] = 0;
}
pos->last_move.from_x = -1;
pos->last_move.from_y = -1;
pos->last_move.to_x = -1;
pos->last_move.to_y = -1;
pos->moves_after_pawn = 0;
pos->num_moves = 0;
}
void CopyPosition(Position* dst, constPosition* src) {
memcpy(dst, src, sizeof(Position));
}
void PrintPosition(constPosition* pos) {
for (int y = 7; y >= 0; --y) {
for (int x = 0; x < 8; ++x) {
printf("%c", piece2a(pos->board[x][y]));
}
printf("\n");
}
for (int i = 0; i < pos->num_moves; ++i) {
constMove* m = &(pos->next_moves[i]);
PrintMove(m);
}
printf("\n\n");
}
Cで書いてもC++っぽくなってしまう。
void PrintMove(constMove* move) {
if (move->piece != 0) {
printf("%c%d%c%d%c ", 'a' + move->from_x, move->from_y + 1, 'a' + move->to_x, move->to_y + 1, piece2a(move->piece));
} else {
printf("%c%d%c%d ", 'a' + move->from_x, move->from_y + 1, 'a' + move->to_x, move->to_y + 1);
}
}
void DoMove(constPosition* src, constMove* m, Position* dst) {
assert(m->from_x >= 0 && m->from_x < 8);
assert(m->from_y >= 0 && m->from_y < 8);
CopyPosition(dst, src);
int x = dst->board[m->from_x][m->from_y];
dst->board[m->from_x][m->from_y] = 0;
dst->board[m->to_x][m->to_y] = x;
dst->side = -(dst->side);
}
// Calculates pawn moves.
// Assumes the piece of the given (x, y) is a pawn.
void CalcPawnMoves(Position* pos, int x, int y) {
Move* m = &(pos->next_moves[pos->num_moves]);
int to_y = y + pos->side;
if (to_y >= 0 && to_y < 8) {
if (pos->board[x][to_y] == 0) {
m->from_x = x;
m->from_y = y;
m->to_x = x;
m->to_y = to_y;
++(pos->num_moves);
}
}
}
とりあえずPawnが前に進むだけ。
void CalcBishopMoves(Position* pos, int x, int y) {
}
void CalcKnightMoves(Position* pos, int x, int y) {
}
void CalcRookMoves(Position* pos, int x, int y) {
}
void CalcQueenMoves(Position* pos, int x, int y) {
}
void CalcKingMoves(Position* pos, int x, int y) {
}
void CalcMoves(Position* pos) {
for (int y = 0; y < 8; ++y) {
for (int x = 0; x < 8; ++x) {
switch (pos->board[x][y] * pos->side) {
case1:
CalcPawnMoves(pos, x, y);
break;
case2:
CalcKnightMoves(pos, x, y);
break;
case3:
CalcBishopMoves(pos, x, y);
break;
case4:
CalcRookMoves(pos, x, y);
break;
case5:
CalcQueenMoves(pos, x, y);
break;
case6:
CalcKingMoves(pos, x, y);
break;
default:
// error
break;
}
}
}
}
void ReadMove(Move* move) {
printf("? ");
move->from_x = -1;
char buf[100];
if (fgets(buf, 100, stdin)) {
switch (strlen(buf)) { // fgets includes \n.
case5:
move->from_x = buf[0] - 'a';
move->from_y = buf[1] - '1';
move->to_x = buf[2] - 'a';
move->to_y = buf[3] - '1';
move->piece = 0;
break;
case6:
move->from_x = buf[0] - 'a';
move->from_y = buf[1] - '1';
move->to_x = buf[2] - 'a';
move->to_y = buf[3] - '1';
move->piece = a2piece(buf[4]);
break;
default:
// error!
break;
}
}
}
int IsValidMove(constPosition* pos, constMove* m) {
constMove* next_move = pos->next_moves;
for (int i = 0; i < pos->num_moves; ++i) {
if (next_move->from_x == m->from_x &&
next_move->from_y == m->from_y &&
next_move->to_x == m->to_x &&
next_move->to_y == m->to_y &&
next_move->piece == m->piece) {
return1;
}
++next_move;
}
return0;
}
generateしたmovesに入っていればvalidということにする。
int a2piece(char a) {
switch (a) {
case'p':
return1;
case'n':
return2;
case'b':
return3;
case'r':
return4;
case'q':
return5;
case'k':
return6;
default:
// error!
break;
}
return0;
}
char piece2a(int p) {
if (p >= -6 && p <= 6) {
returnPIECE_MARK[p + 6];
}
return' ';
}
void ThinkNextMove(Position* pos, Move* move) {
int i = rand() % pos->num_moves;
move->from_x = pos->next_moves[i].from_x;
move->from_y = pos->next_moves[i].from_y;
move->to_x = pos->next_moves[i].to_x;
move->to_y = pos->next_moves[i].to_y;
move->piece = pos->next_moves[i].piece;
}
コンピュータはとりあえずランダムに。論文にはランダムはとても弱いと書いてある。まあ、fool's mateが決まるよね、ランダムじゃ。
int main(int argc, char* argv[]) {
srand((unsigned)time(NULL));
InitPosition(&position[0]);
int ply = 0;
while (1) {
Position* pos = &position[ply];
CalcMoves(pos);
PrintPosition(pos);
Move move;
if (ply % 2 == 0) {
// player move
move.from_x = -1;
while (move.from_x == -1) {
ReadMove(&move);
if (!IsValidMove(pos, &move)) {
move.from_x = -1;
}
}
} else {
ThinkNextMove(pos, &move);
printf("-> ");
PrintMove(&move);
printf("\n\n");
}
DoMove(&position[ply], &move, &position[ply+1]);
++ply;
}
return0;
}
