エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

駒の移動できる位置をビット演算で求める

King's Vallery というゲームがあります。

これの駒の移動できる位置をビット演算で求めてみようと思います。

細かくは、一手目は家臣駒を動かさないといけないとか、家臣駒は King's Vallery に入れないとかありますが、今回はそれらは置いておいて。



実装。

#include <iostream>
#include <sstream>
#include <string>

// 番兵
static const unsigned long long SENTINEL_BITS = 0x000007f04104107fLLU;

// 盤の状態を番兵付きのビット列に変換する
unsigned long long cells_to_bits(const int cells[5][5])
{
  unsigned long long cell_bits = SENTINEL_BITS;
  for(int row = 0; row < 5; ++row)
  {
    for(int col = 0; col < 5; ++col)
    {
      if(cells[row][col] != 0)
      {
        cell_bits |= (1LLU << (35 - (row * 6 + col)));
      }
    }
  }
  return cell_bits;
}

// 盤 cells 上の (row, col) の位置の駒が移動できる位置をビット列で取得する
unsigned long long can_move(const int cells[5][5], int row, int col)
{
  if(cells[row][col] == 0)
  {
    return 0;
  }

  static const int DIRECTIONS[] = { 1, 5, 6, 7 };

  unsigned long long cell_bits          = cells_to_bits(cells);
  unsigned long long can_move_cell_bits = 0;
  unsigned long long piece_bit          = 1LLU << (35 - (row * 6 + col));

  // 左、右上、上、左上への移動
  for(int i = 0; i < 4; ++i)
  {
    unsigned long long searching_cell_bit = piece_bit;
    // 他の駒か番兵に当たるまで進む
    while(((searching_cell_bit << DIRECTIONS[i]) & cell_bits) == 0)
    {
      searching_cell_bit <<= DIRECTIONS[i];
    }
    // 最後まで進んだ位置を記録する
    can_move_cell_bits |= searching_cell_bit;
  }

  // 右、左下、下、右下への移動
  for(int i = 0; i < 4; ++i)
  {
    unsigned long long searching_cell_bit = piece_bit;
    // 他の駒か番兵に当たるまで進む
    while(((searching_cell_bit >> DIRECTIONS[i]) & cell_bits) == 0)
    {
      searching_cell_bit >>= DIRECTIONS[i];
    }
    // 最後まで進んだ位置を記録する
    can_move_cell_bits |= searching_cell_bit;
  }

  // 最後まで進んだ位置の重ね合わせから、最初の位置を引いたものを返す
  return can_move_cell_bits & ~piece_bit;
}

// 盤の状態と移動できる位置を文字列にする
std::string bits_to_str(const unsigned long long can_move_cell_bits, const int cells[5][5], int piece_row, int piece_col)
{
  std::ostringstream cell_stream;
  for(int row = 0; row < 5; ++row)
  {
    for(int col = 0; col < 5; ++col)
    {
      if((row == piece_row) && (col == piece_col))
      {
        // 動かしたい駒
        cell_stream << "@ ";
      }
      else if(cells[row][col] != 0)
      {
        // その他の駒
        cell_stream << cells[row][col] << ' ';
      }
      else
      {
        // 移動可能な位置に x を出力
        cell_stream << ((can_move_cell_bits >> (35 - (row * 6 + col)) & 1u) ? "x " : ". ");
      }
    }
    cell_stream << '\n';
  }
  return cell_stream.str();
}

int main(int argc, char *argv[])
{
  // 盤面の様子
  int cells[5][5] =
  {
    { 1, 1, 5, 1, 1 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0 },
    { 2, 2, 6, 2, 2 }
  };

  // 盤上の各駒について移動できる場所を調べる
  for(int row = 0; row < 5; row += 4)
  {
    for(int col = 0; col < 5; ++col)
    {
      std::cout << '\n';
      std::cout << bits_to_str(can_move(cells, row, col), cells, row, col);
    }
  }

  return 0;
}


実行結果。

$ g++ --std=c++11 -o can_move can_move.cpp 
$ ./can_move 

@ 1 5 1 1 
. . . . . 
. . . . . 
x . . x . 
2 2 6 2 2 

1 @ 5 1 1 
x . . . . 
. . . . . 
. x . . x 
2 2 6 2 2 

(中略)

1 1 5 1 1 
x . . x . 
. . . . . 
. . . . x 
2 2 6 @ 2 

1 1 5 1 1 
. x . . x 
. . . . . 
. . . . . 
2 2 6 2 @ 

解説はまた後日…。