将棋AIに関するメモ

.gitignore

a.out

input.cpp

#include <stdio.h>
#include <ctype.h>
#include "shogi.h"

char piece_symbol_of(int n);
extern struct piece pieces[PIECES];

piece_type parse_type(char c)
{
   switch(c) {
      case 'K': return king;
      case 'B': return bishop;
      case 'R': return rook;
      case 'L': return lance;
      case 'N': return knight;
      case 'G': return gold;
      case 'S': return silver;
      case 'P': return pawn;
   }
}

move_s parse_input(const char* s)
{
  move_s m;
  m.x = m.x2 = m.y = m.y2 = NONE_MOVE;
  m.n = pawn;

  while(char c=*(s++))
  {
    if (c >= 'A' && c <= 'Z')
      m.n = parse_type(c);
    else if (c >= '1' && c <= '9')
      if (m.x2 == NONE_MOVE)
        m.x2 = c-'1';
      else {
        m.x  = m.x2;
        m.x2 = c-'1';
      }
    else if (c >= 'a' && c <= 'm')
      if (m.y2 == NONE_MOVE)
        m.y2 = c-'a';
      else {
        m.y  = m.y2;
        m.y2 = c-'a';
      }
  }
  return m;
}

piece* find(char x, char y, int whose = 0)
{
	for(int i=PIECES*whose; i<PIECES*(whose+1); i++)
		if ( pieces[i].x == x && pieces[i].y == y )
			return &pieces[i];
	return NULL;
}
int last_index_of_type(piece_type t) {
	if ( t == king || t == rook || t == bishop ) return king;
	if ( t == pawn ) return PIECE_END;
	return t + 1;
}
piece* find_x(piece_type t, char x, int whose = 0)
{
	for(int i=t + PIECES_S*whose; i<last_index_of_type(t) + PIECES_S*whose; i++)
		if ( pieces[i].x == x )
			return &pieces[i];
	return NULL;
}
piece* find_y(piece_type t, char y, int whose = 0)
{
	for(int i=t + PIECES_S*whose; i<last_index_of_type(t) + PIECES_S*whose; i++)
		if ( pieces[i].y == y )
			return &pieces[i];
	return NULL;
}
piece* find_ex(move_s m, int whose = 0)
{
	int idx_s = PIECES_S*whose;
	if ( m.n == king )
		return &pieces[idx_s + king];
	if ( m.n == pawn )
		return &pieces[idx_s + pawn + m.x2];
}
void move(move_s m, int whose = 0)
{
	piece* p = find_ex(m, whose);
	p->x = m.x2;
	p->y = m.y2;
}

Makefile

all:
	g++ -O3 \
	  shogi.cpp print.cpp input.cpp

print.cpp

#include <stdio.h>
#include <ctype.h>
#include "shogi.h"

extern struct piece pieces[PIECES];

char piece_symbol_of(int n) {
  switch(n % 20) {
    case king:
      return 'K'; break;
    case gold:
    case gold + 1:
      return 'G'; break;
    case silver:
    case silver + 1:
      return 'S'; break;
    case knight:
    case knight + 1:
      return 'N'; break;
    case lance:
    case lance + 1:
      return 'L'; break;
    case rook:
      return 'R'; break;
    case bishop:
      return 'B'; break;
    default:
      return 'P';
  }
}

void print_board()
{
  printf(" 9 8 7 6 5 4 3 2 1 | /\n");
  printf(" ------------------+---+\n");
  for(int y=0; y<=GRID_MAX; y++)
  {
    for(int x=GRID_MAX; x>=0; x--)
    {
      bool found = false;
      for(int i=0; i<PIECES; i++) {
        if ( pieces[i].x == x && pieces[i].y == y)
        {
          char c = piece_symbol_of(i);
          if (pieces[i].whose == 0) c = tolower(c);

          printf("%c%c", pieces[i].promoted ? '+' : ' ', c);
          found = true;
          break;
        }
      }
      if (!found) printf("  ");
    }
    printf(" | %c |\n", y + 'a');
  }
  printf(" ------------------+---+\n");
}

rule.md

将棋のゲームルール

駒の種類と枚数

以下に将棋の駒の種類、及びその枚数を示す。括弧書きで枚数を示しす。枚数は、対局者のうち一人がゲーム開始時に持つ枚数として記述する。

• 王/玉将 (1)
• 飛車 (1)
• 角行 (1)
• 金将 (2)
• 銀将 (2)
• 桂馬 (2)
• 香車 (2)
• 歩兵 (9)

以上9種類、計20枚を双方が持ち、ゲーム内で用いられる駒数は40となる。

これら駒の総数はゲーム開始から終了時まで変化しない(持ち駒としてのものも含む)。

駒の状態(ステート)について

• 駒はそれぞれ、将棋盤 9x9 座標上のいずれかに置かれる。もしくは**「持ち駒」**として座標を持たない
• 王将・玉将を除く全ての駒は”所有者”を持つ。
• 王将・玉将は所有者が変わった時点でゲーム終了となるため（仮想的なステートとして計算上必要でない限りは）もつ必要はない。
• 王将・玉将・金将以外の全ての駒は**「成駒」**かどうかの状態を持つ
• 「成駒」のステータスは、「駒が取られた」際にリセットされる。

駒の移動について

• 歩兵: 自陣方向から相手方に向かって1マスだけ移動する事が出来る
• 王/玉将: 前後・左右及び全ての斜め方向に対し1マスだけ移動することが出来る
• 金将: 前後・左右、及び前方向に向かっての斜めに1マスだけ移動することが出来る
• 銀将: 全ての斜め方向、または前に1マスだけ移動することが出来る
• 桂馬: 特殊な動き。文章で解説が面倒なのでここでは省略
• 香車: 自陣方向から相手方に向かって任意のマスだけ移動する事が出来る
• 飛車: 上下左右に任意マス移動する事が出来る
• 角行: 斜め方向に任意マス移動する事が出来る

補足

• 既に自駒があるマスに駒を移動する事は出来ない
• 既に敵駒があるマスに移動した場合、その駒の所有権を自分の物にし、「持ち駒」として盤上から取り除かれる
• 及び、前述したが「成駒」のステータスがリセットされる
• 香車・飛車・角行のように任意マスを移動する事が出来る駒は、移動先に何もなくても、その間に自・敵駒が在る場合はそれを跨いで移動する事は出来ない

成駒について

駒は、敵陣(敵側3マスのエリア)内に移動した際「成駒」する事が出来る。

• 飛車 → 竜王: 「飛車」の移動範囲に加え、斜め方向に1マス移動する事が出来る
• 角行 → 竜馬: 「角行」の移動範囲に加え、前後左右に1マス移動する事が出来る
• 銀将・桂馬・香車・歩兵 → 成金: (本来それぞれの「成駒」に名前があるが、省略) 金将と同じ移動が出来るようになる

「持ち駒」を盤上に置く場合について

• 自分・相手の駒が既に置かれている場所に「持ち駒」を置くことは出来ない

上記、及び後述の特殊条件に違反しなければ、任意のマス上に、任意の手持ちの駒を配置する事が出来る。

「持ち駒の使用」は自分の手番の時に一度のみ行う事が出来る。

「持ち駒の使用」を行った際、その手番内で「自駒の移動」を行う事は出来ない。

「歩兵」の禁止ルール

「歩兵」の持ち駒を盤上に置く際、以下の特殊条項（禁止事項）が存在する

• 前後方向全てのマスのいずれかに既に「歩兵」が置かれている場合、「持ち駒」の歩兵を置くことは出来ない (二歩の禁止)
• 「と金」の場合は二歩が可能
• 持ち駒の「歩兵」を配置した結果、相手が「詰み」になる場所に置くことは出来ない (打ち歩詰めの禁止)

「歩兵」「香車」「桂馬」の場合

盤面上に置いても以後動かせない場所、すなわち

• 香車/歩兵: 敵陣の一番奥の段
• 桂馬: 敵陣の一番奥の段と一つ手前の段

には持ち駒を置くことは出来ない

shogi.cpp

#include <stdio.h>
#include <ctype.h>
#include "shogi.h"

void print_board();
char piece_symbol_of(int n);
move_s parse_input(const char* s);
void move(move_s m, int whose = 0);

struct piece pieces[PIECES];

void init_pieces() {
  for(int j=0; j<2; j++)
  {
    int top = GRID_MAX*j;
    pieces[j * 20 + king]      = piece(4, top, j);
    pieces[j * 20 + gold]      = piece(3, top, j);
    pieces[j * 20 + silver]    = piece(2, top, j);
    pieces[j * 20 + knight]    = piece(1, top, j);
    pieces[j * 20 + lance]     = piece(0, top, j);
    pieces[j * 20 + gold+1]    = piece(5, top, j);
    pieces[j * 20 + silver+1]  = piece(6, top, j);
    pieces[j * 20 + knight+1]  = piece(7, top, j);
    pieces[j * 20 + lance+1]   = piece(8, top, j);
    pieces[j * 20 + rook]      = piece(7 -j*6, 1+j*6, j);
    pieces[j * 20 + bishop]    = piece(1 +j*6, 1+j*6, j);

    // Pawns
    for(int i=0; i<=GRID_MAX; i++)
      pieces[j * 20 + pawn + i]  = piece(i, 2 + j*4, j);
  }
}

int main()
{
  init_pieces();
  int turn = 0;
  char whose = 0;

  while(1)
  {
    print_board();
    char input[32];
    printf("%d,%d> ", turn, whose);
    fgets(input, 32, stdin);
    move_s m = parse_input(input);
    printf("%c: %d,%d -> %d,%d\n", piece_symbol_of(m.n), m.x, m.y, m.x2, m.y2);
	 move(m, whose);

	 whose = (whose + 1) % 2;
	 turn++;
  }
  return 0;
}

shogi.h

#ifndef __MYUN2_GIST__SHOGI_H__
#define __MYUN2_GIST__SHOGI_H__

const char GRID_MAX = 8;
const char PIECES = 40;
const char PIECES_S = 20;

struct piece {
  char x;
  char y;
  char whose;
  char promoted;

  piece(char _x = 0, char _y = 0, char _whose = 0, bool _promoted = false) {
    x = _x; y = _y; whose = _whose; promoted = _promoted;
  }
};

enum piece_type {
  king = 0,
  gold = 1,
  silver = 3,
  knight = 5,
  lance = 7,
  rook = 9,
  bishop = 10,
  pawn = 11,
  PIECE_END = 19
};

struct move_s {
  char x;
  char y;
  char x2;
  char y2;
  char n;
};
const int NONE_MOVE = 10;

#endif//__MYUN2_GIST__SHOGI_H__