3目並べとは

3×3の格子盤を用意し、二人が交互に「○」と「×」を書き込んでいき、先に3つ並べたほうが勝ちになるゲームでです。
日本では○×ゲーム、海外ではTic tac tooとして知られています。たぶん、ほとんどの人が一度はやったことのあるゲームだと思います。

このゲームは、両者が最善手を打った場合は、必ず引き分けになります。

作成したプログラム

人間とコンピュータが対戦を行う形式としました。コンピュータは常に最善手を打つようにプログラムしています。絶対に負けません（僕のプログラムが正しければですが...)

まずは、どんなプログラムを書いたのか、その実行例を示します。

見てののとおり、コンソール画面で動作する実にシンプルな見た目のプログラムです。

上のスクリーンショットは、ゲームの途中の画面です。
人間の手番で23と入力しています。2桁の数字でどこに打つのかの位置を指定しています。23は、2行目、3列目を意味します。

次のスクリーンショットは、ゲームが終了（引き分け）した時の画面です。

プログラムを構成するクラス

主要なクラスは、以下の通りです。いわゆるビューに依存したクラスは、ControllerクラスとHumanPlayerクラスだけです。

Controllerクラス

ゲームを制御するクラスです。先手後手を決め、ゲームを開始します。ゲームが終了したら再度ゲームをするかを確認します。実質的なメインプログラムです。

このクラスは、IObserver<Board> を実装しています。いわゆる購読者クラスで、ゲームの状況が変わるとその盤面の状況を受け取ることができます。盤面が変化するとその内容を表示します。いわゆるViewerの役割も担っています。

Gameクラス

1回のゲームを表すクラスです。PerfectPlayerとHumanPlayerを交互に呼び出しゲームを進めます。
このクラスはIObservable<Board> を実装しています。いわゆる発行者クラスです。1手指すたびにその状況を購読者に通知します。そのため、見た目とは完全に独立したクラスになっています。

Boardクラス

盤の状態を表すクラスです。BoardBase<T>(後述)を継承しています。型引数Tには、駒を示すStoneクラスを割り当てます。

Stoneクラス

○×の石を表すクラスです。何も置いていない場所には、空のStone(Stone.Empty)が置いてあるものとします。

IPlayerインターフェイス

プレイヤーを表すインターフェース。

PerfectPlayerクラス

コンピュータ側のプレイヤーを表すクラスです。BestMoveというメソッドを定義し、ここで最善手を見つけています。

BestMoveでは、相手が最善手を指すものと仮定して、最後まで（再帰的に）先読みをします。自分が勝つ手があればそれを指し、なければ引き分けの手を、引き分けもなければ、負けの手を指します。でも、このゲームに限っては負ける手を指すことはないはずです。最低でも引き分けの手を指します。

このルーチンをもっとシンプルなコードにしたかったのですが、この手のプログラミングに慣れていないせいか、思ったよりも長いコードになってしまいました。

HumanPlayerクラス

人間のプレイヤーを表すクラスです。キーボードから手を入力します。

C# のソースコード

クラスの数を少なくして、もっと短いコードのプログラムにすることもできると思いますが、クラスに分割したい派なので、多少長いコードになっても、僕にとってのわかりやすさを優先しました。

3×3の盤面を表すBoardクラスは他のプログラムでも利用しているBoardBase<T>から派生させています。なので、すこしオーバースペックかもしれません。

`BoardBase<T>`を利用している他のプログラム

協力最短詰めオセロ
ナイト(騎士)の最適配置問題
8-Queenパズルを解く
騎士巡回問題(Knight's Tour)

などなど。

以下に、全てのソースコードを載せます。(GitHubでも公開しています)

Program.cs

using System;

namespace TicTacToo {
    class Program {
        static void Main(string[] args) {
            var controller = new Controller();
            while (true) {
                controller.Run();
                if (!Controller.Confirm("Try Again?"))
                    break;
            }
        }
    }
}

Controller.cs

using System;
namespace TicTacToo {
    class Controller : IObserver<Board> {
        private IPlayer _player1;
        private IPlayer _player2;
        private Board _board;

        // 試合の開始
        public void Run() {
            DecideFirstPlayer();
            _board = new Board();
            var game = new Game(_player1, _player2, _board);
            // 購読者は自分自身
            game.Subscribe(this);
            var win = game.Start();
        }

        // 先手を決める
        private void DecideFirstPlayer() {
            var b = Confirm("Are you first?");
            if (b) {
                _player1 = new HumanPlayer(Stone.Black);
                _player2 = new PerfectPlayer(Stone.White);
            } else {
                _player1 = new PerfectPlayer(Stone.Black);
                _player2 = new HumanPlayer(Stone.White);
            }
        }

        private IPlayer GetHumanPlayer() =>
             _player1 is HumanPlayer ? _player1 : _player2;

        // 盤面を表示
        private void Print(Board board) {
            Console.Clear();
            Console.WriteLine("You: {0}\n", GetHumanPlayer().Stone.Value);
            for (int y = 1; y <= 3; y++) {
                for (int x = 1; x <= 3; x++) {
                    Console.Write(board[x, y].Value + " ");
                }
                Console.WriteLine();
            }
        }

        // 終了した
        public void OnCompleted() {
            var win = _board.Judge();
            var human = GetHumanPlayer();
            if (win == Stone.Empty)
                Console.WriteLine("Draw");
            else if (win == human.Stone)
                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 TicTacToo {
    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 Stone Start() {
            IPlayer player = _player1;
            Publish(_board);
            while (!_board.IsFin()) {
                player.NextMove(_board);
                Publish(_board);
                player = Turn(player);
            }
            Complete();
            return _board.Judge();

        }

        // 次のプレイヤー
        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;
namespace TicTacToo {
    public interface IPlayer {
        Stone Stone { get; }
        int NextMove(Board board);
    }
}

HumanPlayer.cs

using System;
namespace TicTacToo {
    public class HumanPlayer : IPlayer {
        public Stone Stone { get; private set; }

        public HumanPlayer(Stone mark) {
            Stone = mark;
        }

        // 次の一手を打つ
        public int NextMove(Board board) {
            while (true) {
                var line = Console.ReadLine();
                if (line.Length != 2)
                    continue;
                var x = line[1] - '0';
                var y = line[0] - '0';
                if (1 <= x && x <= 3 && 1 <= y && y <= 3) {
                    var index = board.ToIndex(x, y);
                    if (board.CanPut(index)) {
                        board[index] = Stone;
                        return index;
                    }
                }
            }
        }
    }
}

PerfectPlayer.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace TicTacToo {
    public class PerfectPlayer : IPlayer {

        public Stone Stone { get; private set; }

        // コンストラクタ
        public PerfectPlayer(Stone myStone) {
            Stone = myStone;
        }

        // 一手を打つ
        public int NextMove(Board board) {
            if (board.GetVacantIndexes().Count() == 9) {
                var (place, winner) = FirstMove(Stone, board);
                board[place] = Stone;
                return place;
            } else {
                var (place, winner) = BestMove(board, Stone);
                board[place] = Stone;
                return place;
            }
        }

        // 次のプレイヤー
        private Stone NextPlayer(Stone now) {
            return now == Stone.Black ? Stone.White : Stone.Black;
        }

        // 王手をみつける
        private int FindCheckmate(Board board, List<int> line, Stone myStone) {
            if (line.Count(x => board[x] == myStone) == 2) {
                var vacants = line.Where(x => board[x] == Stone.Empty);
                if (vacants.Count() == 1)
                    return vacants.First();
            }
            return -1;
        }

        // 最善手を打つ
        private (int, Stone) BestMove(Board board, Stone player, int level = 0) {
            var opponent = NextPlayer(player);
            if (board.IsFin())
                // ここで終わったということは、引き分けしかない。Stone.Emptyは引分けを示す
                return (-1, Stone.Empty);

            var drawix = -1;
            var loseix = -1;
            // 空いている手を一つずつ確かめる
            foreach (var ix in board.GetVacantIndexes()) {
                // ixに石を置いてみる
                board[ix] = player;
                try {
                    var win = board.Judge();
                    if (win == player)
                        // 勝利したのでこれを最善手として戻る
                        return (ix, player);
                    if (win == Stone.Empty) {
                        // まだ終わっていないので、さらに探索 相手も最善手を指すと仮定する
                        var (nextix, winner) = BestMove(board, opponent, level + 1);
                        if (winner == player)
                            // 相手がどこにおいても自分の勝ちなので、これを最善手として戻る
                            return (ix, winner);
                        if (winner == Stone.Empty)
                            // 相手が最善手を指して引分けだった
                            drawix = ix;
                        else
                            // 自分がixに打つと、相手の勝ち
                            loseix = ix;

                    }
                } finally {
                    // 置いた石をixから取り除く
                    board[ix] = Stone.Empty;
                }
            }
            // ここまで来たということは勝ちは無かった。
            if (drawix != -1)
                // 引分けがあったので、引分けの手を最善手として戻る。Stone.Emptyは引分けを示す
                return (drawix, Stone.Empty);
            // 負けてしまった。仕方がないので、負ける手を自分の指す手として戻る
            return (loseix, opponent);
        }

        Random _rnd = new Random();

        // 最初の一手を決める
        private (int, Stone) FirstMove(Stone player, Board board) {

            var indexes = new[] { board.ToIndex(1,1), 
            board.ToIndex(1,3),
            board.ToIndex(3,1),
            board.ToIndex(3,3),
            board.ToIndex(2,2) };
            return (indexes[_rnd.Next(0, indexes.Count())], Stone.Empty);
        }
    }
}

Board.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace TicTacToo {
    public class Stone {
        // 盤面に何も置いていない状態は、Emptyの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; private set; }
        public override string ToString() {
            return Value.ToString();
        }
    }

    public class Board : BoardBase<Stone> {
        public Board() : base(3, 3) {
            foreach (var ix in GetAllIndexes())
                this[ix] = Stone.Empty;
        }

        // 石を置けるか
        public bool CanPut(int index) {
            return this[index] == Stone.Empty;
        }

        // 終了しかた？
        public bool IsFin() {
            if (Judge() != Stone.Empty)
                return true;
            return this.GetVacantIndexes().Count() == 0;
        }

        // 空いている場所を列挙する
        public IEnumerable<int> GetVacantIndexes() {
            return GetAllIndexes().Where(x => this[x] == Stone.Empty);
        }

        // 全ての場所を列挙する
        public override IEnumerable<int> GetAllIndexes() {
            for (int y = 1; y <= 3; y++)
                for (int x = 1; x <= 3; x++)
                    yield return ToIndex(x, y);
        }

        // 縦横斜めすべての筋を列挙する
        public IEnumerable<List<int>> GetLineIndexes() {
            // 横
            for (int y = 1; y <= 3; y++) {
                var p = ToIndex(1, y);
                yield return new List<int> { p, p + 1, p + 2 };
            }
            // 縦
            for (int x = 1; x <= 3; x++) {
                var p = ToIndex(x, 1);
                var d = ToDirection(0, 1);
                yield return new List<int> { p, p + d, p + d + d };
            }
            // 斜め 左上から右下
            {
                var p = ToIndex(1, 1);
                var d = ToDirection(1, 1);
                yield return new List<int> { p, p + d, p + d + d };
            }
            // 斜め 右上から左下
            {
                var p = ToIndex(3, 1);
                var d = ToDirection(-1, 1);
                yield return new List<int> { p, p + d, p + d + d };
            }
        }

        // どちらが勝ったか？
        public Stone Judge() {
            foreach (var list in this.GetLineIndexes().ToList()) {

                if (list.All(x => this[x] == Stone.White))
                    return Stone.White;
                if (list.All(x => this[x] == Stone.Black))
                    return Stone.Black;
            }
            return Stone.Empty;
        }
    }
}

BoardBase.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace TicTacToo {
    // 汎用の盤面クラス
    // 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));

    }
}