ランダムで指す将棋プログラム

指し手を乱数で決める将棋プログラムなら、3,4時間程度あれば書けるだろう・・・
と思い、試しに書いてみました。



C#で書いたのですが、約9時間もかかってしまいました。
不慣れな描画を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行目。

コメント

このブログの人気の投稿

HomeCompass::Update Ver.1.0.4

プレゼンツールSpectacleのデモを動かしてみる