８クィーンゲーム - Gushwell's C# Programming Page

８クィーン・ゲーム

８×８のチェス盤に２人で交互にクィーンを置いていき、自分の手番のときに置き場所が無いほうが負けというゲームです。なお、すでに置かれているクィーン（自分が置いたものも含め）の利き筋に新しいクィーンを置くことはできません。
いわゆる８クィーンパズルのゲーム版というところです。
出典である「ナノピコ教室」では、先手必勝かどうかを調べるという問題でしたが、ここでは、実際に人との対戦が出来るようにしてみました。

※ボタンをクリックするとゲームを開始できます。
※ちなみにあなたが後手の場合は、絶対に勝てません。先手でもちゃんと考えないとなかなか勝てません。

この手のゲームとしては、探索する手が少ないため、勝つ手が見つかるまで全探索しています。Computerが先手の場合に、最初の一手を見つけるのに時間がかかりますが、それ以外は、すぐに探索が終了します。

実際のこの手のゲームプログラムでは、序盤戦は定石を用いたルーチンになっていると思われますが、８クイーンゲームでは、探索手の数が少ないので、愚直に全探索をしています。
枝刈りなどは行っていません。

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

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

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

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

※このプログラムは、そのほかのプログラムでも利用する Board, BoardCanvasクラスを利用しています。Board, BoardCanvasクラスのソースコードはこちらに掲載しています。

■Computer.cs

using System.Linq;
using Gushwell.Etude;
using System.Collections.Generic;

namespace EightQueenFightApp {

// 探索時に利用する打った手の記録
    // 先読みをするので、手はTree上に記録される。
    public class Record {
        public Record Root;
        public Location location { get; private set; }
        public IPiece Piece { get; set; }

// Childrenには可能性のある相手の手が複数格納される
        public List<Record> Children { get; private set; }

public Record(Location loc) {
            location = 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 == Pieces.Black || Piece == Pieces.White) {
                string s = string.Format("{0} {1} {2}\n", new string(' ', indent), location.ToString());
                this.Root.result += s;
            }
            foreach (var x in Children)
                x.Print(indent + 1);
        }
    }

// Computerの思考を担当
    public class Computer {
        private Record _record;
        private int _width;
        private Chessboard _board;

public Computer(Chessboard board) {
            this._board = board;
            _record = new Record();
            _record.Root = _record;
            _width = board.XSize;
        }

// Solveで得られた最善手を返す。
        public Location GetNextLocation() {
            if (_record.Children.Count > 0) {
                var rec = _record.Children[0];
                return rec.location;
            } else {
                // 勝つ手が無い。
                // 最初に見つかった置ける場所に石を置く。（かなり手抜き）
                var places = _board.CanPutPlaces();
                if (places.Count() > 0)
                    return _board.ToLocation(places.First());
                return null;
            }
        }

// 最後まで探索し、最善手を見つける
        public IPiece Solve() {
            IPiece win;
            // すべての空いている位置に対して試してみる。
            foreach (var index in this._board.GetVacantIndexes()) {
                Location loc = this._board.ToLocation(index);
                _record = new Record();
                _record.Root = _record;
                // 現在のボードの状態をコピーし、コピーしたものを利用する
                var workboard = this._board.Clone();
                int p = workboard.ToIndex(loc);
                if (workboard.CanPut(p)) {
                    // 石を置いてみる
                    Record nr = Put(workboard, p, Pieces.Black, _record);
                    // 相手（白）の番の先読み
                    win = Search(workboard, Pieces.White, nr);
                    if (win == Pieces.Black) {
                        // もし、Computerが勝ちならば、処理をやめて戻る。
                        return win;
                    }
                }
            }
            return Pieces.White;
        }

// 再帰処理をし、探索する。
        // 相手がどんな手を打っても勝てる位置を探す。
        public IPiece Search(Chessboard board, IPiece piece, Record rec) {
            // すべての置ける位置に対して処理をする
            foreach (var place in board.CanPutPlaces()) {
                Chessboard temp = board.Clone();
                // 石を置く。
                Record nr = Put(temp, place, piece, rec);
                // 相手の番（先読み）
                IPiece 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(Chessboard board, int place, IPiece piece, Record rec) {
            board[place] = piece;
            Record nr = new Record(board.ToLocation(place));
            rec.Add(nr);
            return nr;
        }

// 次の手番の相手の石を返す
        private IPiece Opponent(IPiece piece) {
            return piece == Pieces.Black ? Pieces.White : Pieces.Black;
        }

// デバッグ用
        public string Print() {
            _record.Root.result = "";
            _record.Print(0);
            return _record.Root.result;
        }
    }
}

■ChessBoard.cs

using System.Linq;
using Gushwell.Etude;
using System.Collections.Generic;

namespace EightQueenFightApp {
    public class Chessboard : Board {
        private int OuterWidth { get; set; }

public Chessboard()
            : base(8, 8) {
            OuterWidth = 10;
        }

public Chessboard(Chessboard board)
            : base(board) {
            OuterWidth = board.XSize + 2;
        }

public Chessboard Clone() {
            return new Chessboard(this);
        }

// 石を置く
        protected override void PutPiece(int index, IPiece piece) {
            base.PutPiece(index, piece);
            if (piece == ForbidPiece || piece == Pieces.Empty)
                return;
            // Queenが動けるところにはマークをつける
            foreach (var i in Courses(index))
                if (this[i] == Pieces.Empty)
                    this[i] = ForbidPiece;
        }

// 置けるか？
        public bool CanPut(int place) {
            return this[place] == Pieces.Empty;
        }

// 置ける位置だけを列挙
        public IEnumerable<int> CanPutPlaces() {
            return this.GetValidIndexes().Where(ix => CanPut(ix));
        }

// nowを通る 縦横斜めのすべての位置を列挙
        public IEnumerable<int> Courses(int now) {
            return Virtical(now)
                .Concat(Horizontal(now))
                .Concat(SlantL(now))
                .Concat(SlantR(now)).Distinct();
        }

// 縦の位置を列挙
        public IEnumerable<int> Virtical(int now) {
            return this.GetSeriesIndexes(now, UpDirection)
                       .Skip(1)
                       .Concat(this.GetSeriesIndexes(now, DownDirection));
        }

// 横の位置を列挙
        public IEnumerable<int> Horizontal(int now) {
            return this.GetSeriesIndexes(now, LeftDirection)
                       .Skip(1)
                       .Concat(this.GetSeriesIndexes(now, RightDirection));
        }

// 右上がり斜線
        public IEnumerable<int> SlantR(int now) {
            return this.GetSeriesIndexes(now, UpperRightDirection)
                       .Skip(1)
                       .Concat(this.GetSeriesIndexes(now, LowerLeftDirection));
        }

// 左上がりの斜線
        public IEnumerable<int> SlantL(int now) {
            return this.GetSeriesIndexes(now, UpperLeftDirection)
                       .Skip(1)
                       .Concat(this.GetSeriesIndexes(now, LowerRightDirection));
        }

static IPiece ForbidPiece = new ForbitPiece();
    }

public struct ForbitPiece : IPiece {
    }

}

■MainPage.xaml.cs

using System.Linq;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Input;
using System.ComponentModel;
using Gushwell.Etude;

namespace EightQueenFightApp {
    // 単純化のためにComputerを黒、人を白に固定。
    // 自分の手番のときに置き場所が無いほうが負けというゲーム。
    // 石を置くことができる場所は、８クィーンパズルと同じ規則に従う。
    public partial class MainPage : UserControl {
        public MainPage() {
            InitializeComponent();
        }
        
        private BackgroundWorker _bw = new BackgroundWorker();
        private BoardCanvas _bcanvas;
        private Chessboard _board;
        private bool _isThinking = true; // 処理の都合上初期値は true
        
        // 初期処理
        private void canvas1_Loaded(object sender, RoutedEventArgs e) {
            _board = new Chessboard();
            _bcanvas = new BoardCanvas(canvas1, _board);
            _bcanvas.DrawRuledLines(BoardType.Chess);
            _bw.DoWork += new DoWorkEventHandler(bw_DoWork);
            _bw.RunWorkerCompleted += new RunWorkerCompletedEventHandler(bw_RunWorkerCompleted);
        }

// マウスがボード上でクリックされた時の処理
        private void canvas1_MouseLeftButtonUp(object sender, MouseButtonEventArgs e) {
            if (_isThinking)
                return;
            Location loc = _bcanvas.ToLocation(e.GetPosition(canvas1));
            PlayMan(loc);
        }
        
        // ゲームスタート
        private void button1_Click(object sender, RoutedEventArgs e) {
            _board.ClearAll();
            if (checkBox1.IsChecked == false) {
                PlayComputer();
            } else {
                textBlock1.Text = "あなたが先手です。白石を置いてください。";
                _isThinking = false;
            }
            button1.Visibility = Visibility.Collapsed;
        }

// locに石が置かれた時の処理
        private void PlayMan(Location loc) {
            if (_board.CanPut(_board.ToIndex(loc))) {
                _board[loc] = Pieces.White;
                PlayComputer();
            }
        }

// Computerが手番の時の処理
        // BackgroundWorkerを使い、バックグラウンドで思考
        private void PlayComputer() {
            canvas1.Cursor = Cursors.Wait;
            textBlock1.Text = "考え中です...";
            _isThinking = true;
            _bw.RunWorkerAsync();
        }

// PlayComputerから呼ばれるバックグラウンド処理
        // 思考そのものは、Computer.Solveで行っている。
        // 最善手は、GetNextLocationで得られる。
        void bw_DoWork(object sender, DoWorkEventArgs e) {
            Computer com = new Computer(_board);
            var r = com.Solve();
            Location loc = com.GetNextLocation();
            e.Result = loc;
        }

// 上の bw_DoWorkが終わると呼び出される。
        void bw_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e) {
            _isThinking = false;
            canvas1.Cursor = Cursors.Arrow;
            Location loc = e.Result as Location;
            if (loc == null) {
                // 黒の置く場所がない。
                textBlock1.Text = "あなたの勝ちです";
                button1.Visibility = Visibility.Visible;
                return;
            }
            // 黒石を置く
            _board[e.Result as Location] = Pieces.Black;
            if (_board.CanPutPlaces().Count() == 0) {
                // 白の置く場所がない。
                textBlock1.Text = "あなたの負けです";
                button1.Visibility = Visibility.Visible;
                return;
            }
            textBlock1.Text = "あなたの番です。白石を置いてください。";
            canvas1.Cursor = Cursors.Hand;
        }
    }
}

■MainPage.xaml

※『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠編　共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。

Gushwell's C# Programming Page

８クィーン・ゲーム

８クィーン・ゲーム