ランダムで指す将棋プログラム
指し手を乱数で決める将棋プログラムなら、3,4時間程度あれば書けるだろう・・・
と思い、試しに書いてみました。
C#で書いたのですが、約９時間もかかってしまいました。
不慣れな描画をggrながら書いたせいもあるでしょうが、納得のいく処理速度ではないですね。
描画とコメントを除いたとしても、250行もあります。
ソースも時間も、もっと短く書きたいものです。
(2013.09.17追記)
敵陣から駒を引いたときの成の可能性が抜けてました。259行目。
と思い、試しに書いてみました。
C#で書いたのですが、約９時間もかかってしまいました。
不慣れな描画をggrながら書いたせいもあるでしょうが、納得のいく処理速度ではないですね。
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace random_shogi {
public partial class Form1 : Form {
private Kyokumen kyokumen = null;
public Form1() {
InitializeComponent();
}
// 盤面初期化
private void init_Click(object sender, EventArgs e) {
kyokumen = new Kyokumen();
kyokumen.init();
this.Invalidate();
}
// 次の一手
private void next_Click(object sender, EventArgs e) {
if (kyokumen == null) {
return;
}
Kyokumen result = kyokumen.getNextByRandom();
if (result == null) {
MessageBox.Show((kyokumen.teban == 0 ? "後手" : "先手") + "が勝ちました。");
} else {
kyokumen = result;
this.Invalidate();
}
}
// 盤面描画
protected override void OnPaint(PaintEventArgs e) {
base.OnPaint(e);
if (kyokumen == null) {
return;
}
Pen pen = new Pen(Color.Black);
Bitmap canvas = new Bitmap(this.pictureBox1.Width, this.pictureBox1.Height);
Graphics g = Graphics.FromImage(canvas);
Font font = new Font("Arial", 36);
int size = (int)font.GetHeight();
int hosei = 5;
for (int i = 0; i < 10; i++) {
g.DrawLine(pen, 2 * size, i * size, (9 + 2) * size, i * size);
g.DrawLine(pen, (i + 2) * size, 0, (i + 2) * size, size * 9);
}
g.ResetTransform();
g.DrawString((kyokumen.teban == 0 ? "先手番" : "後手番") + "(" + (kyokumen.count + 1) + ")", font, Brushes.Black, 11 * size, 0);
for (int i = 0; i < 7; i++) {
String komaStr = "歩香桂銀金角飛"[i].ToString();
for (int j = 0; j < 2; j++) {
int num = kyokumen.ban[9 + j, i];
g.ResetTransform();
if (j != 0) {
g.TranslateTransform((1) * size + size + hosei, i * size + size - hosei);
g.RotateTransform(180F);
g.DrawString((num + 1).ToString() + komaStr, font, Brushes.Black, j * 0, i * 0);
} else {
g.TranslateTransform((j + 11) * size - hosei, (i + (2 - j)) * size + hosei);
g.DrawString(komaStr + (num + 1).ToString(), font, Brushes.Black, j * 0, i * 0);
}
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
int koma = kyokumen.ban[i, j];
int muki = koma & (int)Kyokumen.Koma.MUKI;
int nari = (koma & (int)Kyokumen.Koma.NARI) == 0 ? 0 : 1;
String komaStr = " ";
if (koma != -1) {
int pos = koma & (int)Kyokumen.Koma.NARIMASK;
komaStr = "歩香桂銀金角飛王と杏圭全？馬龍？"[pos].ToString();
if (pos == 7 && muki != 0) {
komaStr = "玉";
}
}
g.ResetTransform();
if (muki != 0) {
g.TranslateTransform((j + 2) * size + size + hosei, i * size + size - hosei);
g.RotateTransform(180F);
} else {
g.TranslateTransform((j + 2) * size - hosei, i * size + hosei);
}
g.DrawString(komaStr, font, Brushes.Black, j * 0, i * 0);
}
}
this.pictureBox1.Image = canvas;
}
}
public class Kyokumen {
public enum Koma : int {
NONE = -1, FU, KYO, KEI, GIN, KIN, KAKU, HISYA, OU,
MASK = 7, NARI, NARIMASK = 15, MUKI,
};
private static int[][] MOVE = new int[][]{
new int[]{ 0,-1},
new int[]{ 0,-1 ,0,-2, 0,-3, 0,-4, 0,-5, 0,-6, 0,-7, 0,-8,},
new int[]{-1,-2, 1,-2},
new int[]{-1,-1, 0,-1, 1,-1, -1, 1, 1, 1},
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, 0, 1,},
new int[]{-1,-1, -2,-2, -3,-3, -4,-4, -5,-5, -6,-6, -7,-7, -8,-8, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, -8, 8, -7, 7, -6, 6, -5, 5, -4, 4, -3, 3, -2, 2, -1, 1, 1,-1, 2,-2, 3,-3, 4,-4, 5,-5, 6,-6, 7,-7, 8,-8, },
new int[]{-8, 0, -7, 0, -6, 0, -5, 0, -4, 0, -3, 0, -2, 0, -1, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 0,-8, 0,-7, 0,-6, 0,-5, 0,-4, 0,-3, 0,-2, 0,-1, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, },
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, -1, 1, 0, 1, 1, 1,},
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, 0, 1,},
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, 0, 1,},
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, 0, 1,},
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, 0, 1,},
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, 0, 1,},
new int[]{-1,-1, -2,-2, -3,-3, -4,-4, -5,-5, -6,-6, -7,-7, -8,-8, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, -8, 8, -7, 7, -6, 6, -5, 5, -4, 4, -3, 3, -2, 2, -1, 1, 1,-1, 2,-2, 3,-3, 4,-4, 5,-5, 6,-6, 7,-7, 8,-8, 0,-1, -1, 0, 1, 0, 0, 1, },
new int[]{-8, 0, -7, 0, -6, 0, -5, 0, -4, 0, -3, 0, -2, 0, -1, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 0,-8, 0,-7, 0,-6, 0,-5, 0,-4, 0,-3, 0,-2, 0,-1, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, -1,-1, 1,-1, -1, 1, 1, 1,},
new int[]{-1,-1, 0,-1, 1,-1, -1, 0, 1, 0, -1, 1, 0, 1, 1, 1,},
};
public int[,] ban;
public int teban;
public int count;
private bool tumi;
public Kyokumen(Kyokumen kyokumen) {
this.ban = (int[,])kyokumen.ban.Clone();
this.teban = kyokumen.teban;
this.count = kyokumen.count;
this.tumi = kyokumen.tumi;
}
public Kyokumen() {
teban = 0;
count = 0;
tumi = false;
ban = new int[11, 9];
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 9; j++) {
ban[i, j] = -1;
}
}
}
// 盤面初期化
public void init() {
for (int i = 0; i < 9; i++) {
add(2, i, Koma.FU, 1, 0);
add(6, i, Koma.FU, 0, 0);
}
for (int i = 0; i < 4; i++) {
add(8-(i%2)*8, 0+((i&2)>>1)*8, Koma.KYO, i%2, 0);
add(8-(i%2)*8, 1+((i&2)>>1)*6, Koma.KEI, i%2, 0);
add(8-(i%2)*8, 2+((i&2)>>1)*4, Koma.GIN, i%2, 0);
add(8-(i%2)*8, 3+((i&2)>>1)*2, Koma.KIN, i%2, 0);
}
add(7, 1, Koma.KAKU, 0, 0);
add(1, 7, Koma.KAKU, 1, 0);
add(7, 7, Koma.HISYA, 0, 0);
add(1, 1, Koma.HISYA, 1, 0);
add(0, 4, Koma.OU, 1, 0);
add(8, 4, Koma.OU, 0, 0);
}
// 駒の配置
private int add(int column, int row, Koma koma, int muki, int nari) {
if (column != -1) {
ban[column, row] = (int)koma + muki * (int)Koma.MUKI + nari * (int)Koma.NARI;
} else {
ban[9+muki, (int)koma]++;
}
return 0;
}
// 次の局面をランダムで決定
public Kyokumen getNextByRandom() {
List list = getNextKyokumen(1);
if (list == null) {
return null;
}
Random rnd = new Random(Environment.TickCount);
return list[rnd.Next(list.Count)];
}
// 王死判定
public bool isDead() {
return (ban[10 - teban, 7] != -1);
}
// 有効な次の局面を全て列挙する
public List getNextKyokumen(int depth) {
List nextList = new List();
// 盤面の手数
for (int col = 0; col < 9; col++) {
for (int row = 0; row < 9; row++) {
int koma = ban[col, row];
if (koma == -1) {
// 駒がない
continue;
}
int muki = (koma & (int)Koma.MUKI) == 0 ? 0 : 1;
int nari = (koma & (int)Koma.NARI) == 0 ? 0 : 1;
koma &= (int)Koma.NARIMASK;
if (teban != muki) {
// 駒の向きが合わない
continue;
}
int[] move = MOVE[koma];
for (int i = 0; i < move.Length / 2; i++) {
int x = row + move[i * 2 + 0];
int y = col + move[i * 2 + 1] * (muki == 0 ? 1 : -1);
if (x < 0 || x > 8 || y < 0 || y > 8) {
// 盤面外
continue;
}
int nextKoma = ban[y, x];
int nextMuki = (nextKoma & (int)Koma.MUKI) == 0 ? 0 : 1;
if (nextKoma != -1 && teban == nextMuki) {
// 自分の駒がいる
continue;
}
// 香角飛の進路チェック
if (((koma & (int)Koma.MASK) == (int)Koma.HISYA) || ((koma & (int)Koma.MASK) == (int)Koma.KAKU) || (koma == (int)Koma.KYO)) {
int stepX = (x - row > 0)?1:(x - row < 0)?-1:0;
int stepY = (y - col > 0)?1:(y - col < 0)?-1:0;
int nowX = row;
int nowY = col;
bool canMove = true;
for (; ; ) {
nowX += stepX;
nowY += stepY;
if (nowX == x && nowY == y) {
break;
} else if (ban[nowY, nowX] != -1) {
// 通り道に駒がある
canMove = false;
break;
}
}
if (!canMove) {
continue;
}
}
// 次局面を追加
Kyokumen nextKyokumen = new Kyokumen(this);
if (nextKoma != -1) {
// 駒を回収
nextKyokumen.ban[9 + teban, nextKoma & (int)Koma.MASK]++;
}
nextKyokumen.ban[y, x] = nextKyokumen.ban[col, row];
nextKyokumen.ban[col, row] = -1;
bool mustNari = false;
bool canNari = false;
// まだ成っていない
if (nari == 0) {
switch ((Koma)koma) {
case Koma.KYO:
case Koma.FU:
mustNari= (teban == 0 && y == 0) || (teban != 0 && y == 8);
canNari = (teban == 0 && y <= 2) || (teban != 0 && y >= 6);
break;
case Koma.KEI:
mustNari = (teban == 0 && y <= 1) || (teban != 0 && y >= 7);
canNari = (teban == 0 && y == 2) || (teban != 0 && y == 8);
break;
case Koma.GIN:
case Koma.KAKU:
case Koma.HISYA:
canNari = (teban == 0 && y <= 2) || (teban != 0 && y >= 6);
break;
default:
break;
}
}
if (mustNari) {
nextKyokumen.ban[y, x] |= (int)Koma.NARI;
}
nextKyokumen.teban = 1 - nextKyokumen.teban;
nextKyokumen.count++;
nextList.Add(nextKyokumen);
if (canNari && !mustNari) {
// 成れる場合は次局面追加
Kyokumen nextKyokumen2 = new Kyokumen(nextKyokumen);
nextKyokumen2.ban[y, x] |= (int)Koma.NARI;
nextList.Add(nextKyokumen2);
}
}
}
}
// 駒打ちの手数
for (int i = 0; i < 7; i++) {
if (ban[9 + teban, i] == -1) {
continue;
}
for (int col = 0; col < 9; col++) {
for (int row = 0; row < 9; row++) {
int koma = ban[col, row];
if (koma != -1) {
// 駒が打てない
continue;
}
bool canUchi = true;
switch ((Koma)i) {
case Koma.FU:
if ((teban == 0 && col == 0) || (teban != 0 && col == 8)) {
canUchi = false;
}
// 二歩チェック
for (int k = 0; k < 9; k++) {
int rowKoma = ban[k, row];
int rowMuki = (rowKoma & (int)Koma.MUKI) == 0 ? 0 : 1;
if (teban == rowMuki && ((rowKoma & (int)Koma.MASK) == (int)Koma.FU)) {
canUchi = false;
}
}
// 打ち歩詰め
if (depth == 1) {
Kyokumen newKyokumen = new Kyokumen(this);
newKyokumen.ban[9 + teban, i]--;
newKyokumen.ban[col, row] = i | (int)(teban == 0 ? 0 : Koma.MUKI);
newKyokumen.teban = 1 - newKyokumen.teban;
if (newKyokumen.getNextKyokumen(-1) == null) {
canUchi = false;
}
}
break;
case Koma.KYO:
if ((teban == 0 && col == 0) || (teban != 0 && col == 8)) {
canUchi = false;
}
break;
case Koma.KEI:
if ((teban == 0 && col <= 1) || (teban != 0 && col >= 7)) {
canUchi = false;
}
break;
case Koma.GIN:
case Koma.KIN:
case Koma.KAKU:
case Koma.HISYA:
break;
}
if (canUchi) {
Kyokumen newKyokumen = new Kyokumen(this);
newKyokumen.ban[9 + teban, i]--;
newKyokumen.ban[col, row] = i | (int)(teban == 0 ? 0 : Koma.MUKI);
newKyokumen.teban = 1 - newKyokumen.teban;
newKyokumen.count++;
nextList.Add(newKyokumen);
}
}
}
}
// 一つでも王死があれば詰んでる
foreach (var kyokumen in nextList) {
if (kyokumen.isDead() == true) {
this.tumi = true;
break;
}
}
// 次の手で王死させられるなら指し手無効
if (depth != 0) {
for (int i = nextList.Count - 1; i >= 0; i--) {
nextList[i].getNextKyokumen(0);
if (nextList[i].tumi) {
nextList.RemoveAt(i);
}
}
}
if (nextList.Count == 0) {
return null;
}
return nextList;
}
}
}
二歩禁止、打ち歩詰め禁止、打てない場所の禁止に対応して、366行17761文字。描画とコメントを除いたとしても、250行もあります。
ソースも時間も、もっと短く書きたいものです。
(2013.09.17追記)
敵陣から駒を引いたときの成の可能性が抜けてました。259行目。
コメント