ラベル ゲームプログラミング の投稿を表示しています。 すべての投稿を表示
ラベル ゲームプログラミング の投稿を表示しています。 すべての投稿を表示

2018年4月28日土曜日

パズル「美術館」を解くプログラムを書いたお話[Rust]

新しい言語としてRustを始めたのですが,まだ使い慣れていない状態です.
練習がてらなにかプログラムを書きたいと思っていたところ,友人が,プログラミングの課題で「美術館」というパズルを解くプログラムを書かされたという話を聞いた.
面白そうなので書いてみたところ,思ったよりも辛い問題で,躓いた点があったのでメモします.

1.概要

「美術館」というパズルゲームはニコリという出版社が生み出したパズルゲームで,Nクイーン問題みたいなパズル.
ルールやサンプル問題などは以下を参照.

公式サイトはFlashのバージョンの問題からか,ChromeやFirefoxからはスッと試すことができなかったので,一度手でやってみたいという方は4番目のニコリパズル道場!という趣味で自作のパズルをあげてるサイトを見ると良いと思います.

2.解法

単純に深さ優先探索とかで書くと,探索空間が2^(WH)で増えていくので解くことはできない.
ただ,一度自分の手で解いてみるとわかりますが,とりあえず置いてみておかしいところが無いか確認する探索よりも,よく知られている経験則によって置く場所が決まることが多いです.
そういった人間でいう「解くためのコツ」を如何に高速に実装できるかがキモでした.
ただ問題によってはある経験則を消したほうが早くなる場合もあってこうしたら絶対に良くなると言い切るのは難しいです.

私の実装では置ける場所・明るくなった場所をbool型の2次元配列でもっておき,以下の制約を実装しました(1-2はルールの言い換え).
  1. 数字マスの周りに置かれた照明の数が,数字マスの数字と一致した場合,その数字マスの周囲にはもう照明は置けない.
  2. 明るくなったマスには照明は置けない.
  3. 数字マスの数字が,置ける空白マスの数と一致している場合は,全ての置ける空白マスに照明をおける.(e.g. 数字4のマスの周りは全て置ける)
  4. 数字マスの周囲に,数字マスに書かれた数だけ照明を置く事ができない場合は条件を満たすことができないので探索を終える.
  5. 置くことができる暗いマスで,その縦列・横列に置ける場所がない場合はそのマスに照明を置ける.
  6. 置くことができない暗いマスで,その縦列・横列に置ける場所がない場合は条件を満たすことができないので探索を終える.
上記のルールに基づいていけば結構なマスを埋めることができます.
ただ,5はない方が早いこともあるしあったほうが早くなることもあるが,6番目の条件は,これがないとマトモに解けない問題もあります.

この条件でマスを埋めることができなくなった場合は
  1. 照明を置ける場所にとりあえず置いてみて条件が満たせないか確認し,もとに戻す.条件を満たせなかったらそのマスは置けないマスとなる.(e.g.数字3のマスの斜め方向には置けないなどの制約になる→Wikipediaの解法を参照)
  2. 数字の周りから先に探索する
という方針で探索領域を狭めながら探索を進めたところ,当方の環境でニコリのお試し問題すべてを4秒以内に解けるようになりました.
ただ公開するにあたって修正したのですが,修正する前のコードは半分ぐらいの時間で計算しているので実装の仕方次第でもう少し早くなるはずです.

3.ソースコード

サンプル入力・出力とともにGithub Gistにあげました.
サンプル入力はニコリのお試し問題からの引用です.
見た目を良くしたつもりなのですが500行を超えてます.
しかも整形しただけで計算時間が2倍になった理由がわからない…….

4.追記

書いた後に調べたところ,もっと良い経験則があるとのこと.


爆速になるらしいので機会があったら実装したいです(多分しない)

2017年8月5日土曜日

現代制御勉強メモと倒立振子の制御例

## 概要

現代制御の勉強メモです.実装するまでの過程をトレースしたかったので,それに必要な知識の確認程度に書いたものです.
内容は状態フィードバック則と同一次元状態オブザーバのまとめと,それを使って適当な制御対象を制御してみてみます.
なお授業で扱った内容を思い出すためのものである上,幾つか扱ってない部分があったり間違ってたり省略してたりするので,ちゃんとした説明は教科書見直してください.学部生なんだ許されてくれ.

## 勉強メモ


### メインコンセプト

次のような状態方程式と呼ばれる形で表された微分方程式がある.ただし\(x\)はベクトルで内部状態を表し,\(u\)は入力,\(y\)は出力である.また\(A,B,C,D\)は定数行列である.

\[ \begin{eqnarray} \dot{x}&=&Ax+Bu\\ y&=&Cx+Du \end{eqnarray} \]

メインコンセプトは,この微分方程式の内部状態\(x\)を,0ベクトルにどうやって近づけるかということである.\(x\)が0ベクトルに収束するためには行列「\(A\)の固有値の実部がすべて負」でなければいけない.「\(A\)の固有値の実部がすべて負」の時,\(x\)は指数関数的に減衰していくことが知られているため,\(x\)は0ベクトルに収束する.

さて,実際にモデルを立てた時に「\(A\)の固有値の実部がすべて負」という条件が満たされていなかったとする.その場合,\(x\)は0に収束するどころか発散してしまう場合がある.しかし,このとき入力\(u\)をうまく与えてやることで擬似的に「\(A\)の固有値の実部をすべて負」にできる.その最も単純な方式として状態フィードバックを用いた極配置という方法を取る.

この方法では,入力\(u\)を次のような形で与える.ただし\(K\)は適当な定数行列である.

\[ u=Kx+v \]

これを上式に代入すると次のようになる.

\[ \begin{eqnarray} \dot{x}&=&(A+BK)x+Bv\\ y&=&Cx+Du \end{eqnarray} \]

したがって定数行列\(A\)が,擬似的に\(A+BK\)となった.したがって\(K\)をうまいこと決めてやれば,定数行列\(A\)の固有値を変えられる.固有値の実部が全て負になるような\(K\)にすれば,\(x\)は0ベクトルに収束し目的が達成できる.

さて,現代制御論のメインコンセプトは上に述べたとおりである.しかし上では語弊を承知で具体的な計算などはすべて除いた.そのため実際には安定化させられない条件というのがいくつかある.また,入力\(u\)は\(u=Kx+v\)とすればよいといったが,\(x\)がわからなければ\(u\)を決定できない.そのため\(x\)を推定する必要がある.

以下では制御ができるかできないかを表す指標「可制御性」,状態\(x\)が推定できるかできないかを表す指標「可観測性」について述べる.

### 状態フィードバック則(文献[1]P35)

先程定数行列\(K\)をうまく決めてやれば,定数行列\(A\)の固有値を擬似的に変えられることをのべた.実際には\(K\)はその要素を適当な変数で置いてやって固有値方程式
\[ \det(\lambda I-(A+BK))=0 \]
が,実部が負となる適当な固有値 \(\lambda_1,...,\lambda_n\)を自分で決めてやって,次式のようにその解がその固有値になるようにしてやれば良い.

\[ \det(\lambda I-(A+BK))=\prod_{i=1}^n(\lambda - \lambda_i) \]

ただし\(\lambda_1,...,\lambda_n\)は係数が実数の多項式の解となるような状態(複素平面上においた時に実軸対称)でなければならない.

### 可制御性(文献[1]P35)


さて上記の式を実際に立ててみると連立方程式は\(K\)の要素に関する線形連立方程式になることが保証されているらしい.しかし妥当な解が得られないような場合がある.すなわち,思い通りに制御することができない場合がある.思い通りに制御できないことを不可制御性を持つと良い,逆に思い通りに制御できることを可制御であるという.

可制御であるということの必要十分条件は次の条件が満たされている場合である事が示されている(文献[1]P38).
\[ rank M_c=rank [B \,\, AB\,\,\dots\,\,A^{n-1}B]=n \]

この行列\(M_c\)は可制御性行列とよばれるもので,微分方程式の解析解を求めると出てくる

\[ \begin{eqnarray} x(t)&=&e^{At}x(0)+\int_0^t e^{A(t-\tau)}Bu(\tau)d\tau\\ &=&e^{At}x(0)+\int_0^t (\beta_0 (t-\tau)I+\beta_1(t-\tau)A+\dots+\beta_{n-1}(t-\tau)A^{n-1})Bu(\tau)d\tau \\ &=&e^{At}x(0)+[B \,\, AB\,\,\dots\,\,A^{n-1}B][\int\beta_0udt \dots\int\beta_{n-1}udt ]^T\\ &=&e^{At}x(0)+M_c [\int\beta_0udt \dots\int\beta_{n-1}udt ]^T \end{eqnarray} \]

不可制御の場合はどうやっても不安定であったりするので,そういう場合は制御対象を何かしら変える必要がある.

### 同一次元状態オブザーバ(文献[1]P121)

状態フィードバック則では,入力\(u\)を決定するのに\(u=Kx+v\)としているから,内部状態\(x\)がわかっている必要がある.

普通は内部状態\(x\)を知ることはできず,ここでは出力\(y\)と入力\(u\),および定数行列\(A,B,C\)のみから推定するしか無い.内部状態を推定する方法はいくつかあるらしいが同一次元状態オブザーバというものを紹介する.

まず\(x\)と同じ次元を持ち,次のような微分方程式で表される関数\(z(t)\)について考える.

\[ \dot{z}=Az+Bu+G(y-Cz) \]

この\(z\)が\(x(t)=z(t)\)となってくれれば内部状態\(x\)がわかったことになる.ここで\(x\)と\(z\)の差\(e(t)=x(t)-z(t)\)について考えると,\(\dot{e}=\dot{x}-\dot{z}\)であるから,

\[ \begin{eqnarray} \dot{e(t)}&=&A(x-z)-G(Cx-Cz)\\ &=&A(x-z)-GC(x-z)\\ &=&(A-GC)e(t) \end{eqnarray} \]

となるから,行列\(A-GC\)の固有値の実部が全て負であれば\(e\)は0に収束する,すなわち\(x=z\)となる.したがって\(A-GC\)の固有値の実部が全て負となるように\(G\)を状態フィードバック則と同じように決めてやればよい.

### 可観測性(文献[1]P41)

ただ同一次元状態オブザーバを作れない場合がある.すなわち,内部状態をどれだけ頑張っても出力\(y\)から知ることができない場合がある.そのようなシステムを不可観測であるといい,逆に内部状態を推定できるシステムを可観測であるという.

システムが可観測であるという必要十分条件は次の可観測性行列\(M_o\)が
\[ rank M_o = rank\begin{bmatrix}C\\CA\\\vdots\\CA^{n-1}\end{bmatrix}=n \]

であることである.この可観測性行列は入力が0である場合の\(y\)の解析解

\[ \begin{eqnarray} y&=&C e^{At}x(0)\\ &=&C(\beta_0 (t)I+\beta_1(t)A+\dots+\beta_{n-1}(t)A^{n-1})x(0)\\ &=&[\beta_0\dots \beta_{n-1}]M_o x(0) \end{eqnarray} \]

に出てくる行列である(文献[1]P43).


## 具体例

### 運動方程式の導出

ここでは台車にくっついた倒立振子について考えます.ただし運動方程式の導出は面倒なので参考文献[2]のモデルを用います(というかこの運動方程式の導出がちゃんとできないとだめというか,現代制御ではモデル化ができてしまえば後は勝手に制御則が出てくるので,でもう少し運動方程式の導出を再勉強するべきな気がする).

参考文献[2]より,台車の位置及び振り子の回転角度の運動方程式は次式のようになる.

\[ \begin{bmatrix} M+m&ml\cos(\theta)\\ ml\cos(\theta)&J+ml^2 \end{bmatrix} \begin{bmatrix} \ddot{x}\\\ddot{\theta} \end{bmatrix} + \begin{bmatrix} -ml\dot{\theta}^2\sin\theta\\ -mlg\sin\theta\end{bmatrix} + \begin{bmatrix} B\dot{x}\\C\dot{\theta} \end{bmatrix} =\begin{bmatrix} u\\0 \end{bmatrix} \]

ここで
\[ T=\begin{bmatrix} M+m&ml\cos(\theta)\\ ml\cos(\theta)&J+ml^2 \end{bmatrix} \]
とおけば


\[ \begin{eqnarray} \begin{bmatrix} \ddot{x}\\\ddot{\theta} \end{bmatrix} &=&T^{-1}\left(\begin{bmatrix} ml\dot{\theta}^2\sin\theta\\ mlg\sin\theta\end{bmatrix} +\begin{bmatrix} -B&0\\0&-C \end{bmatrix}\begin{bmatrix} \dot{x}\\\dot{\theta} \end{bmatrix} +\begin{bmatrix} u\\0 \end{bmatrix}\right) \end{eqnarray} \]


となる.数値解析する分にはこの程度の形で書けていればルンゲクッタでシミュレーションできる.

### 線形化

次に,現代制御を適用するために\(\dot{\theta},\theta\)が微小であるという近似をすると
\[ T=\begin{bmatrix} M+m&ml\\ ml&J+ml^2 \end{bmatrix} \]
であり,微分方程式は次のようになる.

\[ \begin{eqnarray} \begin{bmatrix} \ddot{x}\\\ddot{\theta} \end{bmatrix} &=&T^{-1}\left(\begin{bmatrix} 0&0\\ 0&mlg\end{bmatrix}\begin{bmatrix} {x}\\{\theta} \end{bmatrix} +\begin{bmatrix} -B&0\\0&-C \end{bmatrix}\begin{bmatrix} \dot{x}\\\dot{\theta} \end{bmatrix} +\begin{bmatrix} 1\\0 \end{bmatrix}u\right)\\ &=&\frac{1}{\det T}\left( \left[\begin{matrix}0 & - g l^{2} m^{2}\\0 & g l m \left(M + m\right)\end{matrix}\right]\begin{bmatrix} {x}\\{\theta} \end{bmatrix}\\+\left[\begin{matrix}- B \left(J + l^{2} m\right) & C l m\\B l m & - C \left(M + m\right)\end{matrix}\right]\begin{bmatrix} \dot{x}\\\dot{\theta} \end{bmatrix} +\left[\begin{matrix}J + l^{2} m\\- l m\end{matrix}\right]u \right) \end{eqnarray} \]
ここで状態量を(変数名かぶってますが)\(x=\begin{bmatrix}x&\dot{x}&\theta&\dot{\theta}\end{bmatrix}^T\)とすると
\[ \frac{d}{dt}x=\frac{1}{\det T} \begin{bmatrix} 0&\det T&0&0\\ 0&-B(J+ml^2)&-m^2l^2g&Cml\\ 0&0&0&\det T\\ 0&Blm&mgl(M+m)&-C(M+m) \end{bmatrix}x+ \frac{1}{\det T} \begin{bmatrix} 0\\J+ml^2\\0\\-ml \end{bmatrix}u \]
となるから,
\[ \begin{eqnarray} A&=&\frac{1}{\det T} \begin{bmatrix} 0&\det T&0&0\\ 0&-B(J+ml^2)&-m^2l^2g&Cml\\ 0&0&0&\det T\\ 0&Blm&mgl(M+m)&-C(M+m) \end{bmatrix}\\ B&=& \frac{1}{\det T} \begin{bmatrix} 0\\J+ml^2\\0\\-ml \end{bmatrix}\\ C&=& \begin{bmatrix} 1&0&0&0\\ 0&0&1&0\\ \end{bmatrix}\\ \end{eqnarray} \]
とおけば線形化した場合の状態方程式が書ける.

### オブザーバ,フィードバックゲインの決定

オブザーバ,フィードバックゲインは手計算で求めるとめんどくさそうなのでライブラリを使います.python-controlやmatlabにはplace関数というものがあって,それを用いるとフィードバックゲインなどを求めることができます.

なお,place関数は\(A+BK\)の\(K\)を決めてくれる関数です.したがって状態オブザーバのゲイン\(G\)を決める方法については,\(A-GC\)の転置をとった\(A^T-C^TG^T\)の\(G^T\)を求めることをすれば良いです.

コードはこんな感じです.

### シミュレーション

シミュレーションはProcessingで行いました.自分用の行列ライブラリ,ODEライブラリを作っておきたかったので読みにくいかもしれないです.

コードはここに上げてあります.
上が制御対象(RK4でシミュレーションした非線形微分方程式),下がオブザーバの出力を可視化したものです.初期値は0にしてあり,キーボードの矢印キーで外乱(入力)を与えてやれば動きます.
制御していない場合は発散し,制御している場合にはちゃんと倒立していることがわかります.オブザーバの出力もだいたい上のと同じ感じになってます.

## 感想

大変だったけどいい経験になりました.あと先輩に聞くと結構授業では端折っているところがあったりするらしいので,もっと勉強しないとなと思いました.

## 参考文献

[1] 吉川恒夫,井村順一,現代制御論,(2014),コロナ社
[2] http://www.robot.mach.mie-u.ac.jp/~nkato/class/sc/Invpend_eq3.pdf
[3] Python で任意極配置のフィードバックゲインを求める | org-技術, http://org-technology.com/posts/pole-placement.html
[4] python-controlを利用する際に直面したエラー - szmlb.net, http://szmlb.hatenablog.com/entry/2015/09/08/203643

2015年10月16日金曜日

オセロのコマンドプロンプト上ゲームを作った[C#]

 まぁGUIで作ったのだが,それを入れるとかなり長くなってしまうからコマンドプロンプト上のものにした。近々GUIで動くやつを公開する予定なのでその時は参考にしてください。

1.簡単な説明

プログラムを見てもらえればGUIに移行するのは容易だと思います。一手先しか読まないAIも実装してあります。
 このAIは評価ボードと呼ばれるものにもとづいて自分の手を決めています。どの場所がどのくらい価値が有るかを示したものです。
この評価ボードが一番高くなる手を打つというわけです。しかしそのため,2手先で全部ひっくり返されてしまうような手を打ってくるので,もしそれを直したいときはミニマックス法やアルファベータ法などを用いるといいと思います。

2.プログラム

まぁ長々と話してもプログラムの説明は難しいのでとりあえずコードです。コメントは多めにしてあるからそれを見てください。
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // ゲーム用クラスを用意
        var r = new Reversi();
        int x,y;
        
        while(r.CheckFinish() == false )
        {
            Show(r);
            
            if( r.Turn )
            {
                // 人間からの入力
                Console.WriteLine("左からの番号を入力");
                if ( int.TryParse(Console.ReadLine(),out x) == false )continue;
                Console.WriteLine("上からの番号を入力");
                if ( int.TryParse(Console.ReadLine(),out y) == false )continue;
                r.PutStone(x,y);
            }
            else
            {
                // AIに打たせる
                r.AIPut();
            }
        }
    }
    
    static void Show(Reversi r)
    {
        Console.Clear();
        
        Console.Write(" ");
        for(int i = 0 ; i < Reversi.N ; i++ )
            Console.Write(" {0}",i);
        Console.WriteLine();
        
        for(int i = 0 ; i < Reversi.N ; i++ )
        {
            Console.Write(i);
            for(int j = 0 ; j < Reversi.N ; j++ )
            {
                switch( r.Board[j,i] )
                {
                    case Reversi.BLACK:
                        Console.Write("●");
                        break;
                    case Reversi.WHITE:
                        Console.Write("○");
                        break;
                    default:
                        Console.Write(" ");
                        break;
                }
            }
            Console.WriteLine();
        }
    }
}

class Reversi
{
    /// <summary>
    /// 状態を保存するボード
    /// </summary>
    public int[,] Board;
    /// <summary>
    /// 一辺のマスの数
    /// </summary>
    public const int N = 8;
    /// <summary>
    /// 何もない状態
    /// </summary>
    public const int NONE = 0;
    /// <summary>
    /// 白の石
    /// </summary>
    public const int WHITE = 1;
    /// <summary>
    /// 黒の石
    /// </summary>
    public const int BLACK = -1;
    /// <summary>
    /// どちらの順番がを示す変数(trueなら黒)
    /// </summary>
    public bool Turn;
    /// <summary>
    /// ボードの状態を保存する変数
    /// </summary>
    private List<int[,]> BoardHistory;
    /// <summary>
    /// 手番を保存する変数
    /// </summary>
    private List<bool> TurnHistory;
    /// <summary>
    /// デフォルトの評価ボード
    /// </summary>
    private int[,] EvaluationBoard = new int[,]{
                {  60, -25, 15, 15, 15, 15,-25, 60},
                { -25, -50,-30,-30,-30,-30,-50,-25},
                {  15, -30, 15, 15, 15, 15,-30, 15},
                {  15, -30, 15, 25, 25, 15,-30, 15},
                {  15, -30, 15, 25, 25, 15,-30, 15},
                {  15, -30, 15, 15, 15, 15,-30, 15},
                { -25, -50,-30,-30,-30,-30,-50,-25},
                {  60, -25, 15, 15, 15, 15,-25, 60}
    };

    /// <summary>
    /// コンストラクタ
    /// </summary>
    public Reversi()
    {
        this.Init();
    }

    /// <summary>
    /// 初期化メソッド
    /// </summary>
    public void Init()
    {
        this.Board = new int[N, N];
        this.Board[3, 3] = WHITE;
        this.Board[4, 4] = WHITE;
        this.Board[3, 4] = BLACK;
        this.Board[4, 3] = BLACK;
        this.Turn = true;

        this.BoardHistory = new List<int[,]>();
        this.TurnHistory = new List<bool>();
    }

    /// <summary>
    /// 置ける場所かどうかを判定するメソッド
    /// </summary>
    /// <param name="x">判定するx座標</param>
    /// <param name="y">判定するy座標</param>
    /// <returns>置ける場合はtrue</returns>
    public bool CanPut(int x, int y)
    {
        //とりあえず実際に置いてみる
        var ret = Put(x, y);

        //おけなかったらおけない場所(当然)
        if (ret == false)
            return false;

        //勝手に置くのはダメなので元に戻す
        Undo();

        return true;
    }

    /// <summary>
    /// 元に戻すメソッド
    /// </summary>
    private void Undo()
    {
        // 一番最後の要素のindex
        int n = this.BoardHistory.Count - 1;

        if (n < 0)
            return;

        // 一個前の状態に戻す
        this.Board = this.BoardHistory[n];
        this.Turn = this.TurnHistory[n];

        // その時のボードの状態・手番は消す
        this.BoardHistory.RemoveAt(n);
        this.TurnHistory.RemoveAt(n);
    }

    /// <summary>
    /// 手番を変更するメソッド
    /// </summary>
    private void ChangeTurn()
    {
        // とりあえず順番変える
        this.Turn = !this.Turn;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                // おける場所が一か所でもあればOK
                if (CanPut(i, j) == true)
                    return;
            }
        }

        // おける場所がなかったので手番は元に戻る
        this.Turn = !this.Turn;
    }

    /// <summary>
    /// ゲームが終了したかどうかを判定するメソッド
    /// </summary>
    /// <returns>終了したらtrue</returns>
    public bool CheckFinish()
    {
        // ChangeTurnで!Turnの場合は置ける場所がないのはわかっている
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (CanPut(i, j) == true)
                    return false;
            }
        }

        // 今の人も置く場所がないので終わり
        return true;
    }

    /// <summary>
    /// 石の数を数え上げるメソッド
    /// </summary>
    /// <param name="target">数える対象</param>
    /// <returns>石の数</returns>
    public int CountStone(int target)
    {
        int count = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (Board[i, j] == target)
                    count++;

        return count;
    }

    /// <summary>
    /// 石を置き,手番を変更するメソッド
    /// </summary>
    /// <param name="x">置く場所のx座標</param>
    /// <param name="y">置く場所のy座標</param>
    /// <returns>置くことが出来たらtrueを返す</returns>
    public bool PutStone(int x, int y)
    {
        // とりあえず置く
        var flag = Put(x, y);

        if (flag == false)
            return false;

        ChangeTurn();

        return true;
    }

    /// <summary>
    /// 石を置くメソッド
    /// </summary>
    /// <param name="x">置く場所のx座標</param>
    /// <param name="y">置く場所のy座標</param>
    /// <returns>置くことが出来たらtrueを返す</returns>
    private bool Put(int x, int y)
    {
        //範囲外なら何もせず返す
        if (InRange(x, y) == false)
            return false;
        // なにかあったら置けない
        if (Board[x, y] != NONE)
            return false;

        // ひっくり返したかどうかを格納するメソッド
        bool isChanged = false;
        // 現在の状態を一旦保存する
        var currentBoard = (int[,])(this.Board.Clone());
        // 現在の攻撃側はどちらかを一旦保存する
        var currentTurn = this.Turn;

        for (int i = 0; i < 9; i++)
        {
            //これでdx,dyは-1から1までの値が入る
            int dx = i / 3 - 1;
            int dy = i % 3 - 1;

            //両方共0じゃなければ
            //(dx,dy)方向へひっくり返せるかを調べる
            if (dx != 0 || dy != 0)
                isChanged = isChanged | Reverse(x, y, dx, dy);
        }

        // ひっくり返さなかった場合はfalse
        if (isChanged == false)
            return false;


        // ココに来てやっと置くことが出来る
        this.Board[x, y] = NowStone();

        // 手番とボードの状態を保存
        this.BoardHistory.Add(currentBoard);
        this.TurnHistory.Add(currentTurn);

        return true;
    }

    /// <summary>
    /// 石をひっくり返すメソッド
    /// </summary>
    /// <param name="x">石をおいたx座標</param>
    /// <param name="y">石をおいたy座標</param>
    /// <param name="dx">調べる方向のx</param>
    /// <param name="dy">調べる方向のy</param>
    /// <returns>ひっくり返せたらtrue</returns>
    private bool Reverse(int x, int y, int dx, int dy)
    {
        var attack = NowStone();
        var defense = -attack;

        // その方向が枠の外ならひっくり返せない
        if (InRange(x + dx, y + dy) == false)
            return false;
        // 一個先を見て敵の石じゃなかったらひっくり返せない
        if (Board[x + dx, y + dy] != defense)
            return false;


        // その先を見ていく
        for (int i = 2; i < N; i++)
        {
            int index_x = x + i * dx;
            int index_y = y + i * dy;

            if (InRange(index_x, index_y) == false)
            {
                //範囲外ならfalse
                return false;
            }
            else if (Board[index_x, index_y] == attack)
            {
                //探した先に攻撃側の駒があった場合はひっくり返す
                for (; i >= 1; i--)
                    Board[x + i * dx, y + i * dy] = attack;
                return true;
            }
            else if (Board[index_x, index_y] == NONE)
            {
                // その先に仲間の石がなかったのでfalse
                return false;
            }
        }

        // 仲間の石が見つからなかったのでfalse
        return false;
    }

    /// <summary>
    /// 現在攻撃側の石を置くメソッド
    /// </summary>
    /// <returns></returns>
    private int NowStone()
    {
        if (this.Turn)
            return BLACK;
        else
            return WHITE;
    }

    /// <summary>
    /// 特定の位置が配列の範囲内かどうかを判定するメソッド
    /// </summary>
    /// <param name="x">判定するx座標</param>
    /// <param name="y">判定するy座標</param>
    /// <returns>範囲内ならtrue</returns>
    private bool InRange(int x, int y)
    {
        if (x < 0 || x >= N)
            return false;
        if (y < 0 || y >= N)
            return false;

        return true;
    }

    /// <summary>
    /// 評価関数
    /// </summary>
    /// <param name="evaluationBoard">評価ボード</param>
    /// <returns>評価値(黒が有利なら正)</returns>
    private int Evaluate(int[,] evaluationBoard)
    {
        var point = 0;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                point += evaluationBoard[i, j] * Board[i, j];
            }
        }

        return point;
    }

    /// <summary>
    /// 人工知能による最適な手の選択し,置く
    /// </summary>
    /// <param name="evaluationBoard">評価ボード</param>
    public void AIPut(int[,] evaluationBoard)
    {
        int max = int.MinValue;
        int x = 0;
        int y = 0;
        // 自分の石を覚えとく
        int myStone = NowStone();

        // 終わっていたら関係ない
        if (CheckFinish() == true)
            return;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                // とりあえず石を置く
                if (PutStone(i, j) == true)
                {
                    // 置けたら盤面評価
                    // 自分の石の値をかけて常に正にする
                    var point = myStone * Evaluate(evaluationBoard);

                    // ポイントが高かったら
                    if (point > max)
                    {
                        // その手を保存する
                        x = i;
                        y = j;
                        max = point;
                    }

                    // 元に戻す
                    Undo();
                }
            }
        }

        // 置ける場所なら置く
        if (InRange(x, y) == true)
            PutStone(x, y);
    }
    
    /// <summary>
    /// 人工知能による最適な手の選択し,置く
    /// </summary>
    public void AIPut()
    {
        AIPut(this.EvaluationBoard);
    }
}