Help us understand the problem. What is going on with this article?

8クィーン・ゲーム(思考ボードゲーム)をC#で作成

8クィーン・ゲームとは

8×8のチェス盤に2人で交互にクィーンを置いていき、自分の手番のときに置き場所が無いほうが負けというゲームです。すでに置かれているクィーン(自分が置いたものも含め)の利き筋に新しいクィーンを置くことはできません。
いわゆる8クィーンパズルのゲーム版というところです。

クィーンは、縦横斜めの何処へでも移動できます。将棋の飛車と角を合わせた動きになります。

出典である「ナノピコ教室1」では、先手必勝かどうかを調べるという問題でしたが、ここでは、実際に人との対戦が出来るようにしてみました。

ちなみにあなたが後手の場合は、絶対に勝てません。先手でもちゃんと考えないとなかなか勝てません。

.NET Coreのコンソールアプリケーションとして作成していますので、MacでもWindowsでもそのまま動くはずです。

どうやって解くか

実際のこの手のゲームプログラムでは、序盤戦は定石を用いたルーチンになっていると思われますが、8クイーンゲームでは、探索手の数が少ないので、愚直に全探索をしています。枝刈りなどは行っていません。
最初の一手目はすこし時間がかかりますが、それ以降は、すぐに探索が終了します。

プログラムを単純化するために、黒石(×)をコンピュータ、白石(○)を人間に固定していますが、実際の探索をするSearchメソッドは、石の色に関係なく探索が出来るようにしてあります。

Searchメソッドでは、

  1. 自分の石をある位置に置いてみる
  2. 相手の石で Searchを呼び出す (再帰処理)つまり「ここにおいたら、次に相手はどう打つかな」を考える
  3. 結果が自分の石の勝ちならば、ここで終了(戻る)
  4. 自分の石が勝てなかったら、1に戻り別の場所を試してみる
  5. どこに置いても勝てなかったら、相手の勝ちとして戻る。

という動きになっていて、2手先、3手先を読むのではなく、勝敗がきまるまで、ずーっと先読みを続けています。
思考型の対戦ゲームとしての基本構造を示せるという点で、8クィーンゲームはなかなか良い題材だと思います。

ソースコードにはコメントを付加していますので、詳しくはソースコードを見てください。

実行例

以下に、実行例を示します。

これは、ゲームの途中の状態。人間のプレイヤーは、2桁の数字(行と列)を入力しクィーンをの置く場所を指定します。

スクリーンショット 2019-01-22 17.35.16.png

盤面の _ は、利き筋になってもうクィーンが置けない場所を示しています。.は、クィーンを置ける場所を示しています。

次のは、ゲームが終わった状態。僕は先手(o)でしたが、負けてしまいました(T T)

スクリーンショット 2019-01-22 17.31.07.png

主要なクラス

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));

    }
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした