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>を利用している他のプログラム
などなど。
以下に、全てのソースコードを載せます。(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));
}
}