2009年02月15日

[パズル]梅花碁(2)

  
梅花碁(1)の続きです。
問2は、「黒ー白ー黒と打って、黒が必ず勝ちになる手を探す」というものです。

前回作成した Board クラスと SolverクラスのGetWinPositionメソッドはそのまま利用しています。

今までのナノピコ教室の問題と同様、バックトラックをする再帰処理を書けばできるはず、ということでC#で書いてみましたが、ビジネスアプリ開発を専門とする僕は、思考型のゲームプログラムの作成にはほとんど縁がないので、ちょっと手こずりました。

拡張すれば、対戦型のプログラムができるようプログラムを設計してあります。
探索コードの中の

List koho

は、そのための用意した変数ですが、このプログラムではほとんど意味をなしていません。
このままだと、あまりにも探索する手が多すぎるので、本格的にやろうとすれば、もっと工夫が必要になってくると思われます。
また、それぞれの手にポイントを付けて、どれが最善手かを調べるようにしないといけませんし、良い手か悪い手かの判断アルゴリズムを考え出さなくてはいけません。
それと、深さ優先の探索を採用していますが、幅優先の探索に変更する必要もあると思われます。って、幅優先のプログラムって今まで書いたことがありません(^^;

また、SearchBlack, SearchWhiteというほとんど瓜二つのメソッドがあるので、これも一つにしたいところです。


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

namespace Umehana {
class Program {
static void Main(string[] args) {
Solver sol = new Solver();
string[] data = new string[] {
" ",
" O # ",
" O O ",
" # ",
" ",
" # # ",
" O ",
" ",
" ",
" ", };
sol.ReadData(data);
sol.Print();
var r = sol.SearchBlack(0);
if (r.Win == Board.Black)
Console.WriteLine("({0},{1})に打てば2手目で黒の勝ちです。",
r.Position.X, r.Position.Y);
else
Console.WriteLine("黒が2手目で勝ちになる手はありません。");
}
}

class Value {
public char Win { get; set; }
public Position Position { get; set; }
}

class Solver {
public Board board;
private Random rnd = new Random();
public Solver () {
board = new Board(10);
}

public void Print() {
board.Print();
}

private char Opponent(char piece) {
return piece == Board.Black ? Board.White : Board.Black;
}

public Value SearchBlack(int depth) {
if (depth >= 3)
return new Value { Win = Board.Empty, Position = null };
Position winpos = GetWinPosition(Board.Black);
if ( winpos != null )
return new Value { Win = Board.Black, Position = winpos };

// すぐに勝ちになる手はない。先読みする。
List<Value> koho = new List<Value>();
foreach (var pos in board.Vacants()) {
board.Put(pos, Board.Black);
try {
Value val = SearchWhite(depth + 1);
if (val.Win == Board.Black)
return new Value { Win = Board.Black, Position = pos };
else if (val.Win != Board.White)
koho.Add(new Value { Win = Board.Empty, Position = pos });
} finally {
board[pos] = Board.Empty;
}
}
int count = koho.Count();
if (count == 0)
// どこに打っても白の勝ち
return new Value { Win = Board.White, Position = board.Vacants().First()};
else
return koho.Skip(rnd.Next(0, count - 1)).First();
}

public Value SearchWhite(int depth) {
if (depth >= 3)
return new Value { Win = Board.Empty, Position = null };
Position winpos = GetWinPosition(Board.White);
if ( winpos != null )
return new Value { Win = Board.White, Position = winpos };

// すぐに勝ちになる手はない。先読みする。
List<Value> koho = new List<Value>();
foreach (var pos in board.Vacants()) {
board.Put(pos, Board.White);
try {
if (board.IsWin(Board.White)) {
return new Value { Win = Board.White, Position = pos };
}

Value val = SearchBlack(depth + 1);
if (val.Win == Board.White)
return new Value { Win = Board.White, Position = pos };
else if (val.Win != Board.Black)
koho.Add(new Value { Win = Board.Empty, Position = pos });
} finally {
board[pos] = Board.Empty;
}
}
int count = koho.Count();
if (count == 0)
// どこに打っても黒の勝ち
return new Value { Win = Board.Black, Position = board.Vacants().First() };
else
return koho.Skip(rnd.Next(0, count - 1)).First();
}

public Position GetWinPosition(char piece) {
foreach (var pos in board.Vacants()) {
board.Put(pos, piece);
try {
if (board.IsWin(piece))
return pos;
} finally {
board[pos] = Board.Empty;
}
}
return null;
}

public void ReadData(string[] lines) {
int y = 0;
foreach (var line in lines) {
int x = 0;
foreach (var c in line) {
if (c == Board.Black || c == Board.White)
board.Put(x, y, c);
x++;
}
y++;
}
}
}

class Position {
public int X { get; set; }
public int Y { get; set; }
}

class Board {
static public char Empty = ' ';
static public char Black = '#';
static public char White = 'O';
private char[,] cells;
private int width;
public Board(int width) {
cells = new char[width, width];
this.width = width;
foreach (var pos in AllCells())
this[pos] = Empty;
}
private char this[int x, int y] {
get { return cells[x, y]; }
set { cells[x, y] = value; }
}
public char this[Position pos] {
get { return cells[pos.X, pos.Y]; }
set { cells[pos.X, pos.Y] = value; }
}
public void Put(int x, int y, char piece) {
cells[x, y] = piece;
}
public void Put(Position pos, char piece) {
cells[pos.X, pos.Y] = piece;
}
public IEnumerable<Position> Vacants() {
foreach (var pos in AllCells()) {
if (this[pos] == Empty)
yield return pos;
}
}
public IEnumerable<Position> AllCells() {
for (int x = 0; x < width; x++)
for (int y = 0; y < width; y++)
yield return new Position { X = x, Y = y };
}
public bool IsWin(char piece) {
foreach (var pos in AllCells())
if (IsWinPattern(pos,piece))
return true;
return false;
}
public bool IsWinPattern(Position pos, char piece) {
if (this[pos] != piece)
return false;
for (int size = 1; size < (width - 1) / 2; size++) {
if (!((size <= pos.X && pos.X < width - size) &&
(size <= pos.Y && pos.Y < width - size)))
continue;
// パターン1
if (this[pos.X - size, pos.Y] == piece &&
this[pos.X + size, pos.Y] == piece &&
this[pos.X, pos.Y - size] == piece &&
this[pos.X, pos.Y + size] == piece)
return true;
// パターン2
if (this[pos.X - size, pos.Y - size] == piece &&
this[pos.X - size, pos.Y + size] == piece &&
this[pos.X + size, pos.Y - size] == piece &&
this[pos.X + size, pos.Y + size] == piece)
return true;
}
return false;
}
public void Print() {
Console.WriteLine(" 0123456789");
for (int y = 0; y < width; y++) {
Console.Write(y);
for (int x = 0; x < width; x++)
Console.Write(cells[x, y]);
Console.WriteLine();
}
}
}
}






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


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51755865