梅花碁とは
梅花碁は、碁盤と碁石であそぶ連珠の一種です。「うめはなご」と読むのかと思ったら、「ばいかご」なんですね。
黒、白交互に打ち進めて、十字の勝ちパターンを作ったほうが勝ちというゲームです。
十字の大きさは問いませんが、辺の方向は水平、垂直、４５度の角度に限ります。
たとえば、以下のようなパターンができれば、白の勝ちとなります。
作成したプログラム
梅花碁の対戦ゲームを作成しようかとも思ったのですが、その前段階として、梅花碁のある局面で白黒どちらが勝ったかどうか（上記の十字形ができたかどうか）を調べるプログラムを書いてみました。
勝ちパターンがあるかどうかを調べる方法は、注目している石を梅花の中心とみなして、十字の勝ちパターンになっているかを地道に一点一点確認するという当たり前の方法を採用しました。
盤面の状態はファイルから読み込むようにしています。
C#のソースコード
※ ソースコードは、GitHubでも公開しています。
Program.cs
Mainメソッドのあるクラスです。Solverクラスを使って勝ちパターンがあるかどうかを調べ、勝ちパターンがあれば、それを表示しています。
どこで勝ちパターンが作られたかを色を変えることで示すようにしています。
盤面のデータファイル名は、"board.txt"と固定にしています。
using System;
using System.IO;
using System.Linq;
namespace BaikagoApp {
class Program {
private static Board board;
static void Main(string[] args) {
board = new Board(15);
string[] lines = File.ReadAllLines("board.txt");
board.Initialize(lines);
var solver = new Solver(board);
var (stone, pattern) = solver.WhichWon();
if (stone == null) {
Console.WriteLine("見つかりません。");
return;
} else if (stone == Stone.White) {
Console.WriteLine("White");
} else {
Console.WriteLine("Black");
}
Print(pattern);
}
public static void Print(int[] winPattern) {
var currColor = Console.ForegroundColor;
for (int y = 1; y <= board.YSize; y++) {
for (int x = 1; x <= board.XSize; x++) {
if (winPattern.Contains(board.ToIndex(x, y))) {
Console.ForegroundColor = ConsoleColor.Red;
Console.Write($"{board[x, y].Value} ");
Console.ForegroundColor = ConsoleColor.White;
} else {
Console.ForegroundColor = currColor;
Console.Write($"{board[x, y].Value} ");
}
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
Solver.cs
勝ちパターンがあるかを調べるクラスです。
効率面やクラス設計ではまだまだ改良のよりがありそうですが、正しく動作することを優先してこの形に落ち着きました。
タプルを使いましたが、outキーワードの引数で勝ちパターンの石の配置を返した方が良かったかもしれません。
主なメソッドは以下の通りです。
IsWinPattern
ある点を与えると、その点を中心とした十字パターンがあるかどうかを調べるメソッド。
bool値とその勝ちパターンの石の配置をタプルで返します。
なお、中心点と十字のサイズを与えると、その勝ちパターンの位置コレクションを返すメソッド CreateWinPattern1, CreateWinPattern2を作成して、このメソッドからそれを呼び出しています。こうすることでIsWinPatternがすっきりとしたと思います。
IsWin
IsWinPatternメソッドをすべての地点に対して調べて行き、一つでもIsWinPatternが trueを返せば、勝ちパターンがあると判定。
IsWinPatternと同様に、bool値とその勝ちパターンの石の配置をタプルで返します。
WhichWon
どちらの石が勝ったのかを判定するメソッド。石の種類と勝ちパターンの石の配置をタプルで返します。
IsWinを白石と黒石に対して呼び出すことで実現しています。
using System;
using System.Linq;
using System.Text;
namespace BaikagoApp {
class Solver {
private Board _board;
public Solver(Board board) {
_board = board;
}
// どちらが勝ったかを判定
public (Stone, int[]) WhichWon() {
(var isWin, var pattern) = IsWin(Stone.White);
if (isWin)
return (Stone.White, pattern);
(isWin, pattern) = IsWin(Stone.Black);
if (isWin)
return (Stone.Black, pattern);
return (null, null);
}
// pieceが勝ったかを判定
public (bool, int[]) IsWin(Stone piece) {
foreach (var loc in _board.GetAllIndexes()) {
(var isWin, var pattern) = IsWinPattern(loc, piece);
if (isWin)
return (isWin, pattern);
}
return (false, null);
}
// 指定した位置で指定したPieceが勝ちパターンを作ったかを調べる
public (bool, int[]) IsWinPattern(int pos, Stone piece) {
if (_board[pos] != piece)
return (false, null);
var (x, y) = _board.ToLocation(pos);
int maxsize = Math.Min(_board.XSize, _board.YSize);
for (int size = 1; size <= (maxsize - 1) / 2; size++) {
if (!((size < x && x <= _board.XSize - size) &&
(size < y && y <= _board.YSize - size)))
continue;
// パターン1
var wp1 = CreateWinPattern1(pos, size);
if (wp1.All(loc => _board[loc] == piece)) {
return (true, wp1);
}
var wp2 = CreateWinPattern2(pos, size);
if (wp2.All(loc => _board[loc] == piece)) {
return (true, wp2);
}
}
return (false, null);
}
// posを中心点とし、sizeの大きさの勝ちパターン（＋）を作成
private int[] CreateWinPattern1(int pos, int size) {
int[] wp = new int[5];
var (x, y) = _board.ToLocation(pos);
wp[0] = pos;
wp[1] = _board.ToIndex(x - size, y);
wp[2] = _board.ToIndex(x + size, y);
wp[3] = _board.ToIndex(x, y - size);
wp[4] = _board.ToIndex(x, y + size);
return wp;
}
// posを中心点とし、sizeの大きさの勝ちパターン（Ⅹ）を作成
private int[] CreateWinPattern2(int pos, int size) {
int[] wp = new int[5];
var (x, y) = _board.ToLocation(pos);
wp[0] = pos;
wp[1] = _board.ToIndex(x - size, y - size);
wp[2] = _board.ToIndex(x - size, y + size);
wp[3] = _board.ToIndex(x + size, y - size);
wp[4] = _board.ToIndex(x + size, y + size);
return wp;
}
}
}
Board.cs
盤面を表すクラス(Board)と石クラス(Stone)。
Stone.Emptyは何も置いていないことを示す仮のStoneオブジェクト。
盤面を表すBoardクラスは、Boardbase<T>(後述)を継承しています。このプログラムでは、初期化以外は、Boardbase<T>で定義されている基本機能だけを使っています。
using Puzzle;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BaikagoApp {
public class Stone {
public static readonly Stone Black = new Stone { Value = 'X' };
public static readonly Stone White = new Stone { Value = 'O' };
public static readonly Stone Empty = new Stone { Value = '.' };
public char Value { get; set; }
}
public class Board : BoardBase<Stone> {
public Board(int size) : base(size, size) {
foreach (var index in GetAllIndexes()) {
this[index] = Stone.Empty;
}
}
// 初期状態の表示
public void Initialize(string[] lines) {
int y = 1;
foreach (var line in lines) {
int x = 1;
foreach (var c in line) {
if (c == 'X')
this[x, y] = Stone.Black;
else if (c == 'O')
this[x, y] = Stone.White;
x++;
}
y++;
}
}
}
}
実行例
入力ファイルの例
O
O OX
X X X
X OX
O OX X X
O X
X OX O X
X O OOO O
X
XO O X
O
O X O X
O X
スクリーンショット
勝ちパターンの石の色を赤で示しています。
C# + .NET Coreで作成し、Macで動かしていますが、ソースコードの修正なしで、Windowsでも動作するはずです。
BoardBase<T>クラス
このBoardBaseクラスは、「騎士巡回問題」「ナイト(騎士)の最適配置問題」「協力最短詰めオセロ」などで利用したものと同じものです。
前述のBoardクラスの基底クラスです。X × Y の盤面を表し、基本的な操作を定義しています。これは似たようなパズルでも再利用できるような汎用的な機能に絞っています。このBoardBaseクラスは、コンソールアプリに依存しない作りにしています。UWP、WinFormsでもそのまま使えると思います。
このBoardBaseを継承して、当パズル専用のBoardクラスを定義します。
内部では1次元配列を使っていますが、インデクサを定義して、1次元配列、2次元配列としても扱えるようにしています。
ただし、すべてのメソッドで１次元対応と２次元対応のものを用意するのは面倒なので、どちらか一方にしています。まあこれは好み以外の何物でもありません。
１次元のインデックスによるアクセスができるようにしている理由は、一重ループで処理が書けるので、コードが簡潔になるからです。LINQのコードも書きやすくなります。
2次元配列として見た場合の、X座標、Y座標は、0 からではなく、1から始まります。
つまり、board[1,1] は、いちばん左上を示し、8×8の盤ならば、board[8,8]が右下を示すことになります。
なお、盤の周りには番兵用の領域を用意しています。これにより範囲外かどうかの判断を簡単に出来るようにしています。チェスのナイト(騎士)の動きにも対応できるよう、番兵は二重にしています。
上の図は 4×4の盤を表していますが、グレー部分が番兵が置いてある盤の周囲で、水色部分が実際の盤です。
盤面上の数値は、１次元配列のインデックスを表しています。
なお、派生クラスや派生クラスを利用するクラスが、この番兵の存在に依存しないように、ToDirectionという関数を定義し、X方向、Y方向のペアで表す移動方向(ベクトル)をインデックスで表す方向に変換するようにしています。
BoardBaseクラスはジェネリッククラスにしていて、そのパラメータの型は、盤面上に置けるクラスの型です。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Puzzle {
// 汎用の盤面クラス
// Tは、盤面に置けるオブジェクトの型。参照型でnew()ができれば何でも良い。
public abstract class BoardBase<T> where T : class, new() {
private T[] _pieces;
// 盤の行数（縦方向）
public int YSize { get; private set; }
// 盤のカラム数（横方向）
public int XSize { get; private set; }
// 番兵も含めた幅のサイズ
private int OuterWidth => XSize + 4;
private int OuterHeight => XSize + 4;
// コンストラクタ
public BoardBase(int xsize, int ysize) {
this.YSize = ysize;
this.XSize = xsize;
_pieces = new T[OuterWidth * OuterHeight];
// 盤データの初期化 - 盤の周りはnull(番兵)をセットしておく
ClearAll();
}
// コピー用コンストラクタ
public BoardBase(BoardBase<T> board) {
XSize = board.XSize;
YSize = board.YSize;
this._pieces = board._pieces.ToArray();
}
// 番兵も含めたボード配列の長さ
public int BoardLength => _pieces.Length;
// インデクサ (x,y)の位置の要素へアクセスする
public T this[int index] {
get { return _pieces[index]; }
set { _pieces[index] = value; }
}
// インデクサ (x,y)の位置の要素へアクセスする
public T this[int x, int y] {
get { return this[ToIndex(x, y)]; }
set { this[ToIndex(x, y)] = value; }
}
// Location から _coinのIndexを求める
public int ToIndex(int x, int y) => x + 1 + (y + 1) * OuterWidth;
// IndexからLocationを求める (ToIndexの逆演算)
public (int, int) ToLocation(int index)
=> (index % OuterWidth - 1, index / OuterWidth - 1);
public int ToDirection(int dx, int dy) => dy * OuterWidth + dx;
// 本来のボード上の位置(index)かどうかを調べる
public virtual bool IsOnBoard(int index) => this[index] != null;
// 全てのPieceをクリアする
public virtual void ClearAll() {
for (int index = 0; index < BoardLength; index++)
this[index] = null; // 番兵
foreach (var index in GetAllIndexes())
this[index] = new T(); // 初期値
}
// 盤上のすべての位置(index)を列挙する
public virtual IEnumerable<int> GetAllIndexes() {
for (int y = 1; y <= this.YSize; y++) {
for (int x = 1; x <= this.XSize; x++) {
yield return ToIndex(x, y);
}
}
}
// (x,y)からdirection方向の位置を列挙する (x,y)含む
public virtual IEnumerable<int> EnumerateIndexes(int x, int y, int direction) {
for (int index = ToIndex(x, y); IsOnBoard(index); index += direction)
yield return index;
}
// (x,y)から右(水平)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> Horizontal(int x, int y)
=> EnumerateIndexes(x, y, ToDirection(1, 0));
// (x,y)から下(垂直)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> Virtical(int x, int y)
=> EnumerateIndexes(x, y, ToDirection(0, 1));
// (x,y)から右斜め下(45度)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> SlantR(int x, int y)
=> EnumerateIndexes(x, y, ToDirection(1, 1));
// (x,y)から左斜め下(45度)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> SlantL(int x, int y)
=> EnumerateIndexes(x, y, ToDirection(-1, 1));
}
}