８クィーン・ゲームとは
８×８のチェス盤に２人で交互にクィーンを置いていき、自分の手番のときに置き場所が無いほうが負けというゲームです。すでに置かれているクィーン（自分が置いたものも含め）の利き筋に新しいクィーンを置くことはできません。
いわゆる８クィーンパズルのゲーム版というところです。
クィーンは、縦横斜めの何処へでも移動できます。将棋の飛車と角を合わせた動きになります。
出典である「ナノピコ教室1」では、先手必勝かどうかを調べるという問題でしたが、ここでは、実際に人との対戦が出来るようにしてみました。
ちなみにあなたが後手の場合は、絶対に勝てません。先手でもちゃんと考えないとなかなか勝てません。
.NET Coreのコンソールアプリケーションとして作成していますので、MacでもWindowsでもそのまま動くはずです。
どうやって解くか
実際のこの手のゲームプログラムでは、序盤戦は定石を用いたルーチンになっていると思われますが、８クイーンゲームでは、探索手の数が少ないので、愚直に全探索をしています。枝刈りなどは行っていません。
最初の一手目はすこし時間がかかりますが、それ以降は、すぐに探索が終了します。
プログラムを単純化するために、黒石(×)をコンピュータ、白石(○)を人間に固定していますが、実際の探索をするSearchメソッドは、石の色に関係なく探索が出来るようにしてあります。
Searchメソッドでは、
- 自分の石をある位置に置いてみる
- 相手の石で Searchを呼び出す （再帰処理）つまり「ここにおいたら、次に相手はどう打つかな」を考える
- 結果が自分の石の勝ちならば、ここで終了（戻る）
- 自分の石が勝てなかったら、1に戻り別の場所を試してみる
- どこに置いても勝てなかったら、相手の勝ちとして戻る。
という動きになっていて、2手先、３手先を読むのではなく、勝敗がきまるまで、ずーっと先読みを続けています。
思考型の対戦ゲームとしての基本構造を示せるという点で、８クィーンゲームはなかなか良い題材だと思います。
ソースコードにはコメントを付加していますので、詳しくはソースコードを見てください。
実行例
以下に、実行例を示します。
これは、ゲームの途中の状態。人間のプレイヤーは、2桁の数字（行と列）を入力しクィーンをの置く場所を指定します。
盤面の _ は、利き筋になってもうクィーンが置けない場所を示しています。.は、クィーンを置ける場所を示しています。
次のは、ゲームが終わった状態。僕は先手(o)でしたが、負けてしまいました(T T)
主要なクラス
Controllerクラス
このゲームを制御する実質的なメインクラスです。1回の対戦だけを扱います。基本、表示はこのクラスが受け持っています、
Gameクラス
1回の対戦を扱うクラスです。2つのプレイヤーを交互に呼び出し、ゲームを進めます。
HumanPlayer クラス
人間のプレイヤーを表すクラスです。
ComputerPlayer クラス
コンピュータープレイヤーを表すクラスです。この中に思考ルーチンが組み込まれています。
Boardクラス
盤面を表すクラスです。
このBoardクラスは他のプログラムでも利用しているBoardBase<T>から派生させていますので、すこしオーバースペックかもしれません。
BoardBase<T>を利用している他のプログラム
などなど。
IOberver<T>, IOvervable<T>
UIとロジックを分離するために、IOberver<T>, IOvervable<T>を実装しています。
GameクラスがIObservable<Board>を実装し、盤面の変化を購読者に通知しています。
購読者クラスは、Controllerクラスで、IObserver<Board>を実装しています。
C#のコード
Program.cs
using System;
namespace EightQueensGame
{
class Program
{
static void Main(string[] args)
{
var controller = new Controller();
while (true)
{
controller.Run();
if (!Controller.Confirm("Try Again?"))
break;
}
}
}
}
Controller.cs
C#のコードは、GitHubでも公開しています。
using System;
namespace EightQueensGame
{
class Controller : IObserver<Board>
{
private IPlayer _player1;
private IPlayer _player2;
private IPlayer _winner;
private Board _board;
// 試合の開始
public void Run()
{
DecideFirstPlayer();
_board = new Board();
var game = new Game(_player1, _player2, _board);
// 購読者は自分自身
game.Subscribe(this);
_winner = game.Start();
}
// 先手を決める
private void DecideFirstPlayer()
{
var b = Confirm("Are you first?");
if (b)
{
_player1 = new HumanPlayer();
_player2 = new ComputerPlayer();
}
else
{
_player1 = new ComputerPlayer();
_player2 = new HumanPlayer();
}
}
private IPlayer GetHumanPlayer() =>
_player1 is HumanPlayer ? _player1 : _player2;
// 盤面を表示
private void Print(Board board)
{
Console.Clear();
Console.WriteLine(" 1 2 3 4 5 6 7 8 ");
Console.WriteLine(" ----------------");
for (int y = 1; y <= 8; y++)
{
Console.Write($"{y}|");
for (int x = 1; x <= 8; x++)
{
var val = board[x, y].Value;
if (val == '_')
val = '.';
Console.Write(val + " ");
}
Console.WriteLine();
}
}
// 終了した
public void OnCompleted()
{
var winner = _player1.IsWin ? _player1 : _player2;
//var human = GetHumanPlayer();
// このゲームには引き分けはない
if (_winner is HumanPlayer)
Console.WriteLine("You Win");
else
Console.WriteLine("You Lose");
}
// エラー発生
public void OnError(Exception error)
{
Console.WriteLine(error.Message);
}
// 状況変化
public void OnNext(Board value)
{
Print(value);
}
// (y/n)の確認
public static bool Confirm(string message)
{
Console.Write(message);
var left = Console.CursorLeft;
var top = Console.CursorTop;
try
{
while (true)
{
var key = Console.ReadKey();
if (key.KeyChar == 'y')
return true;
if (key.KeyChar == 'n')
return false;
Console.CursorLeft = left;
Console.CursorTop = top;
}
}
finally
{
Console.WriteLine();
}
}
}
}
Game.cs
using System;
using System.Collections.Generic;
namespace EightQueensGame
{
public class Game : IObservable<Board>
{
private Board _board;
private IPlayer _player1;
private IPlayer _player2;
// コンストラクタ
public Game(IPlayer player1, IPlayer player2, Board board)
{
_player1 = player1;
_player2 = player2;
_board = board;
}
// Game開始
public IPlayer Start()
{
IPlayer player = _player1;
IPlayer winner = null;
Publish(_board);
while (true)
{
var index = player.GetNextHand(_board);
if (index < 0)
{
winner = Turn(player);
break;
}
_board.PutPiece(index, player.MyPiece);
Publish(_board);
player = Turn(player);
}
winner.IsWin = true;
Complete();
return winner;
}
// 次のプレイヤー
private IPlayer Turn(IPlayer player)
{
return player == _player1 ? _player2 : _player1;
}
private List<IObserver<Board>> _observers = new List<IObserver<Board>>();
// 終了を通知する
private void Complete()
{
foreach (var observer in _observers)
{
observer.OnCompleted();
}
}
// 状況変化を知らせるために購読者に通知する
private void Publish(Board board)
{
foreach (var observer in _observers)
{
observer.OnNext(board);
}
}
// 購読を申し込む - observerが通知を受け取れるようになる
public IDisposable Subscribe(IObserver<Board> observer)
{
_observers.Add(observer);
return observer as IDisposable;
}
}
}
IPlayer.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace EightQueensGame
{
public interface IPlayer
{
int GetNextHand(Board board);
Piece MyPiece { get; }
bool IsWin { get; set; }
}
}
HumanPlayer.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace EightQueensGame
{
class HumanPlayer : IPlayer
{
public Piece MyPiece => Piece.White;
public bool IsWin { get; set; }
public int GetNextHand(Board board)
{
if (board.CanPutPlaces().Count() == 0)
{
return -1;
}
while (true)
{
var line = Console.ReadLine();
if (line.Length != 2)
continue;
var y = line[0] - '0';
var x = line[1] - '0';
if (1 <= x && x <= 8 && 1 <= y && y <= 8)
{
var index = board.ToIndex(x, y);
if (board.CanPut(index))
{
return index;
}
}
}
}
}
}
ComputerPlayer.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace EightQueensGame
{
// Computerの思考を担当
public class ComputerPlayer : IPlayer
{
public Piece MyPiece => Piece.Black;
public bool IsWin { get; set; }
private Record _record;
// Solveで得られた最善手を返す。
public int GetNextHand(Board board)
{
Solve(board);
if (_record.Children.Count > 0)
{
var rec = _record.Children[0];
return rec.Index;
}
else
{
// 勝つ手が無い。
// 最初に見つかった置ける場所に石を置く。（かなり手抜き）
var places = board.CanPutPlaces();
if (places.Count() > 0)
return places.First();
return -1;
}
}
// 最後まで探索し、最善手を見つける
public Piece Solve(Board board)
{
_record = new Record();
_record.Root = _record;
Piece win;
// すべての空いている位置に対して試してみる。
foreach (var index in board.GetVacantIndexes())
{
// int loc = this._board.ToLocation(index);
_record = new Record();
_record.Root = _record;
// 現在のボードの状態をコピーし、コピーしたものを利用する
var workboard = board.Clone();
int p = index;
if (workboard.CanPut(p))
{
// 石を置いてみる
Record nr = Put(workboard, p, MyPiece, _record);
// 相手（白）の番の先読み
win = Search(workboard, Opponent(MyPiece), nr);
if (win == MyPiece)
{
// もし、Computerが勝ちならば、処理をやめて戻る。
return win;
}
}
}
return Opponent(MyPiece);
}
// 再帰処理をし、探索する。
// 相手がどんな手を打っても勝てる位置を探す。
public Piece Search(Board board, Piece piece, Record rec)
{
// すべての置ける位置に対して処理をする
foreach (var place in board.CanPutPlaces())
{
Board temp = board.Clone();
// 石を置く。
Record nr = Put(temp, place, piece, rec);
// 相手の番（先読み）
Piece win = Search(temp, Opponent(piece), nr);
if (win == piece)
{
// pieceが勝ったら戻る
//（pieceの相手がどんな手を打っても pieceの勝ち)
// 今までの手を捨て去って、新しい手をrecに加える
rec.Clear();
rec.Add(nr);
return piece;
}
// この位置に置くと相手が勝ってしまうので、次の位置を調べる。
// ちなみにこのゲームには引き分けはない。
}
// どこにも打つ場所が無い。
// あるいは、どこに置いても勝てない。
// つまり相手の勝ち
return Opponent(piece);
}
// pieceをplaceの位置に置き、置いた石とその位置を記録する
private Record Put(Board board, int place, Piece piece, Record rec)
{
// board[place] = piece;
board.PutPiece(place, piece);
Record nr = new Record(place);
rec.Add(nr);
return nr;
}
// 次の手番の相手の石を返す
private Piece Opponent(Piece piece)
{
return piece == Piece.Black ? Piece.White : Piece.Black;
}
// デバッグ用
public string Print()
{
_record.Root.result = "";
_record.Print(0);
return _record.Root.result;
}
}
}
Record.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace EightQueensGame
{
public class Record
{
public Record Root;
public int Index { get; private set; }
public Piece Piece { get; set; }
// Childrenには可能性のある相手の手が複数格納される
public List<Record> Children { get; private set; }
public Record(int loc)
{
Index = loc;
Children = new List<Record>();
}
public Record()
{
Children = new List<Record>();
}
public void Add(Record rec)
{
Children.Add(rec);
rec.Root = this.Root;
}
public void Clear()
{
Children.Clear();
}
public string result = "";
// デバッグ用
public void Print(int indent)
{
if (Piece == Piece.Black || Piece == Piece.White)
{
string s = string.Format("{0} {1}\n", new string(' ', indent), Index.ToString());
this.Root.result += s;
}
foreach (var x in Children)
x.Print(indent + 1);
}
}
}
Board.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace EightQueensGame
{
// 石を表すクラス
public class Piece
{
public static Piece White = new Piece { Value = 'O' };
public static Piece Black = new Piece { Value = 'X' };
public static Piece Empty = new Piece { Value = '.' };
public static Piece Forbid = new Piece { Value = '-' };
public char Value { get; set; }
}
// 盤面クラス
public class Board : BoardBase<Piece>
{
// 少しでも速くするためにキャッシュしておく
private IEnumerable<int> AllIndexes = null;
public Board()
: base(8, 8)
{
AllIndexes = GetAllIndexes();
foreach (var ix in AllIndexes)
this[ix] = Piece.Empty;
}
// オブジェクト複製用
public Board(Board board)
: base(board)
{
AllIndexes = GetAllIndexes();
}
public Board Clone()
{
return new Board(this);
}
// 石を置く
public void PutPiece(int index, Piece piece)
{
this[index] = piece;
if (piece == Piece.Forbid || piece == Piece.Empty)
return;
// Queenが動けるところにはマークをつける
foreach (var i in Courses(index))
if (this[i] == Piece.Empty)
this[i] = Piece.Forbid;
}
// 空いている位置を列挙する
internal IEnumerable<int> GetVacantIndexes()
{
return AllIndexes.Where(x => this[x] == Piece.Empty);
}
// 置けるか？
public bool CanPut(int place)
{
return this[place] == Piece.Empty;
}
// 置ける位置だけを列挙
public IEnumerable<int> CanPutPlaces()
{
return AllIndexes.Where(ix => CanPut(ix));
}
// nowを通る 縦横斜めのすべての位置を列挙
public IEnumerable<int> Courses(int now)
{
return Virtical(now)
.Concat(Horizontal(now))
.Concat(SlantL(now))
.Concat(SlantR(now)).Distinct();
}
private int Up => ToDirection(0, -1);
private int Down => ToDirection(0, 1);
private int Left => ToDirection(-1, 0);
private int Right => ToDirection(1, 0);
private int UpperLeft => ToDirection(-1, -1);
private int UpperRight => ToDirection(1, -1);
private int LowerLeft => ToDirection(1, -1);
private int LowerRight => ToDirection(1, 1);
// 縦の位置を列挙
public IEnumerable<int> Virtical(int now)
{
var (x, y) = ToLocation(now);
return this.EnumerateIndexes(x, y, Up)
.Skip(1)
.Concat(this.EnumerateIndexes(x, y, Down));
}
// 横の位置を列挙
public IEnumerable<int> Horizontal(int now)
{
var (x, y) = ToLocation(now);
return this.EnumerateIndexes(x, y, Left)
.Skip(1)
.Concat(this.EnumerateIndexes(x, y, Right));
}
// 右上がり斜線
public IEnumerable<int> SlantR(int now)
{
var (x, y) = ToLocation(now);
return this.EnumerateIndexes(x, y, UpperRight)
.Skip(1)
.Concat(this.EnumerateIndexes(x, y, LowerLeft));
}
// 左上がりの斜線
public IEnumerable<int> SlantL(int now)
{
var (x, y) = ToLocation(now);
return this.EnumerateIndexes(x, y, UpperLeft)
.Skip(1)
.Concat(this.EnumerateIndexes(x, y, LowerRight));
}
}
}
BpardBase.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace EightQueensGame
{
// 汎用の盤面クラス
// 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
{
get { return _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)
{
//if (0 <= index && index < BoardLength)
return this[index] != null;
//return false;
}
// 全ての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));
}
}