三目並べゲーム－２

前田稔(Maeda Minoru)の超初心者のプログラム入門

プログラムの説明

1. 三目並べゲーム CSForm.cs のソースコードです。
   事前に学習することで、プレイヤーと対等にゲームの相手が出来ます。
   

   // コンピュータとプレイする(Cell に乱数で引分を含む棋譜を学習) using System; using System.Drawing; using System.Windows.Forms; using System.Collections; //ArrayList を使うとき using System.Diagnostics; //Debug.Write を使うとき public class Cell { public ArrayList AL = null; public int n; // N 手目 public int y; // Y 座標 public int x; // X 座標 public int v=0; // 点数 } public class Pos { public int y=0; // Y 座標 public int x=0; // X 座標 } public class MyForm : Form { int[,] m_t = new int[3, 3]; int[,] m_dat = new int[9, 2]; // 手の記録 int m_num; // m_datのIndex bool m_sente= false; // 人間側先手フラグ int m_judge; // 対戦結果 Cell m_top = new Cell(); Pos m_pos = new Pos(); Random rand = new Random(12345); //シード値で初期化 public MyForm() { m_top= CellInit(); Init(); BackColor = SystemColors.AppWorkspace; Width = 250; Height = 270; Paint += new PaintEventHandler(MyHandler); MouseDown += new MouseEventHandler(OnMyMouseDown); } // ウインドウの描画 private void MyHandler(object sender, PaintEventArgs e) { Graphics g = e.Graphics; g.DrawImage(new Bitmap("c:\\data\\test\\game3.gif"), new PointF(10F, 10F)); for (int y = 0; y < 3; y++) for (int x = 0; x < 3; x++) { if (m_t[y, x]==1) g.DrawImage(new Bitmap("c:\\data\\test\\koma_b.gif"), new PointF(x * 61 + 28, y * 61 + 24)); if (m_t[y, x]==-1) g.DrawImage(new Bitmap("c:\\data\\test\\koma_w.gif"), new PointF(x * 61 + 28, y * 61 + 24)); } if (m_judge == 0) { m_judge = Fine(m_t); AddData(m_judge * 3, m_num, m_top, m_dat); if (m_judge==1) MessageBox.Show("黒の勝ち"); if (m_judge==-1) MessageBox.Show("白の勝ち"); if (m_judge==9) MessageBox.Show("引き分け"); } } // マウスのクリックでプレイ private void OnMyMouseDown(object sender, MouseEventArgs e) { Pos p = new Pos(); int c= 0; if (e.Button == MouseButtons.Right) { if (m_num==0) { m_sente= !m_sente; if (m_sente) MessageBox.Show("あなたの先手"); else MessageBox.Show("わたしの先手"); } Init(); Invalidate(); return; } if (m_judge!=0) return; p.x = (e.X-28)/61; p.y = (e.Y-24)/61; if (m_num%2==0) // 先手番 { if (!m_sente) // マシンが先手 { p= Think(m_dat, m_t); } c = 1; } else // 後手番 { if (m_sente) // マシンが後手 { p= Think(m_dat, m_t); } c = -1; } if (m_t[p.y,p.x]!=0) { MessageBox.Show("Miss Play"); return; } m_t[p.y,p.x]= c; m_dat[m_num,0]= p.y; m_dat[m_num,1]= p.x; m_num++; Invalidate(); } // コンピュータが考える(m_sente==true マシンが後手) public Pos Think(int[,] dat, int[,] t) { Cell p,q; int i,k,v,best=0; Debug.WriteLine("NUM:" + m_num); p=q= m_top; for(i=0; i<m_num; i++) { if (p.AL == null) return Next(m_num, t); for (k=0; k<p.AL.Count; k++) { q= (Cell)p.AL[k]; if (q.y==dat[i,0] && q.x==dat[i,1]) break; } if (k>=p.AL.Count) return Next(m_num, t); // 未登録 p= q; } v = -1000000; // マシンが先手のときは最大値 if (m_sente) v= 1000000; // マシンが後手のときは最小値 if (p.AL == null) return Next(m_num, t); DebugList(p.AL); for (k = 0; k < p.AL.Count; k++) { q = (Cell)p.AL[k]; if (m_sente && v>q.v) // マシンが後手 { v= q.v; best= k; } if (!m_sente && v<q.v) // マシンが先手 { v= q.v; best= k; } } m_pos.y = ((Cell)p.AL[best]).y; m_pos.x = ((Cell)p.AL[best]).x; return m_pos; } // 乱数で選択 public Pos Next(int num, int[,] t) { Pos p = new Pos(); int r; r= rand.Next(9-num); for(p.y=0; p.y<3; p.y++) for(p.x=0; p.x<3; p.x++) { if (t[p.y, p.x] == 0) { if (r<1) return p; r--; } } return p; } // 終了判定 public int Fine(int[,] t) { int[] tw = new int[8]; int i; if (m_num > 8) return 9; for (i=0; i<8; i++) tw[i] = 0; for(i=0; i<3; i++) { tw[0] += t[0,i]; tw[1] += t[1,i]; tw[2] += t[2,i]; tw[3] += t[i,0]; tw[4] += t[i,1]; tw[5] += t[i,2]; tw[6] += t[i,i]; tw[7] += t[i,2-i]; } for(i=0; i<8; i++) { if (tw[i]==3) return 1; if (tw[i]==-3) return -1; } return 0; } // ゲームの初期化 public void Init() { for(int y=0; y<3; y++) for(int x=0; x<3; x++) m_t[y,x] = 0; m_num= 0; m_judge = 0; } // Cell に手を記録させる public Cell CellInit() { Cell top = new Cell(); Pos ps; int ret=0, num; for (int j=0; j<2000000; j++) //for (int j=0; j<2; j++) { ret = 0; for (int y = 0; y < 3; y++) for (int x = 0; x < 3; x++) m_t[y, x] = 0; // dat[9] に一局の棋譜を格納 for (num=0; num<9; num++) { ps = Next(num, m_t); if (num % 2 == 0) m_t[ps.y, ps.x] = 1; else m_t[ps.y, ps.x] = -1; m_dat[num, 0] = ps.y; m_dat[num, 1] = ps.x; ret = Fine(m_t); if (ret != 0) { num++; break; } } AddData(ret, num, top, m_dat); } return top; } // dat[] の一局を top(Cell) に登録(v:評価値, num:datの件数) public void AddData(int ret, int num, Cell top, int[,] dat) { Cell pt = top; int k,v; v= ret; if (v>8) v=0; for (int i=0; i<num; i++) { k = AddCell(pt, i, dat[i, 0], dat[i, 1]); pt = (Cell)pt.AL[k]; pt.v += v; } } // pt の ArrayList に i, y, x のセルを追加する public int AddCell(Cell pt, int i, int y, int x) { Cell wk,wk2; int j; wk = new Cell(); wk.n = i; wk.y = y; wk.x = x; if (pt.AL==null) pt.AL= new ArrayList(); for (j=0; j<pt.AL.Count; j++) { wk2 = (Cell)pt.AL[j]; if (wk2.y==y && wk2.x==x) break; } if (j>=pt.AL.Count) pt.AL.Add(wk); return j; } // ☆Debug 関数 // ary[] の確認 public static void DebugAry(int num, int[] ary) { for (int i = 0; i < num; i++) Console.Write(i + "[" + ary[i] + "] "); Debug.Write("\n\n"); } // dat[9] の確認 public void DebugDat(int num, int[,] dat) { for (int i = 0; i < num; i++) Debug.Write("I:" + i + " Y:" + dat[i, 0] + " X:" + dat[i, 1] + "\n"); } // ArrayList の確認 public void DebugList(ArrayList array) { Cell wk; if (array==null) return; for(int i=0; i<array.Count; i++) { wk= (Cell)array[i]; Debug.Write("N:" + wk.n + " Y:" + wk.y + " X:" + wk.x + " V:" + wk.v + "\n"); } } // Cell(セル)から再帰で印字(lev:0 は一手目, lev:1 は二手目・・・) public void DebugCell(int lev, Cell top) { Cell wk; if (lev>9) return; for(int i=0; i<top.AL.Count; i++) // ArrayList の印字 { wk = (Cell)top.AL[i]; Debug.WriteLine("N:" + wk.n + " Y:" + wk.y + " X:" + wk.x + " V:" + wk.v); if (wk.AL != null) DebugCell(lev+1, wk); } } // dat[sz,2] を編集して盤を印字 public void DebugPrint(int sz, int[,] dat) { string str= ""; char[,,] t = new char[2, 3, 3]; // 盤 for(int y=0; y<3; y++) for(int x=0; x<3; x++) { t[0,y,x]= '.'; t[1,y,x]= ' '; } for(int i=0; i<sz; i++) { if (i%2==0) t[0,dat[i,0],dat[i,1]]= 'X'; if (i%2==1) t[0,dat[i,0],dat[i,1]]= '0'; t[1, dat[i, 0], dat[i, 1]] = (char)(i+0x30); } for(int y=0; y<3; y++) { for(int x=0; x<3; x++) str= str + t[0,y,x]; str= str + " : "; for(int x=0; x<3; x++) str= str + t[1,y,x]; str= str + "\n"; } Debug.WriteLine(str); } } class image01 { public static void Main() { MyForm mf = new MyForm(); Application.Run(mf); } }

2. 人間が少し考えれば解る三目並べのような簡単なゲームでも、学習データだけに頼ると２００万回の対局データが必要でした。
   当初１万回ぐらいで良い結果が得られると期待していたのですが、１００万回でも簡単なミスを犯します。
   どこかプログラムミスや考え方が間違っているのかと悩んだのですが、２００万回の事前登録でようやくそれなりの結果を得ることが出来ました。
   三目並べの組み合わせは９の階乗(362,880 通り)あり、効果を発揮できるようになるには当然かもしれません。
   事前に登録する対局データは、コンピュータが乱数を使って自動的に生成するのですが、学習するのに約１２秒の時間がかかりました。
   本格的なディープラーニングでは、データベースなどを利用して膨大なデータを記録するのでしょうね。
   今回のプログラムでは、約１２秒間待っていれば基本的な学習データを生成してくれるので保存しておく必要はありません。
   強い相手と対戦して学習した方がより効果が上がると期待して試したのですが、単純に乱数で生成したものと大きな違いはありませんでした。
   三目並べゲーム自体が単純すぎるからでしょうか？
   学習データの件数を減らすには Next() 関数に常識的な手を組み込む必要があるようです。
   
3. Cell Class(構造体)と Pos Class(構造体)です。
   ArrayList AL で Cell 構造体を連鎖します。
   v が黒番でこの手を選んだときの点数で、黒番では最も大きな値を、白番では最も小さな値の手を選択します。
   

   public class Cell { public ArrayList AL = null; public int n; // N 手目 public int y; // Y 座標 public int x; // X 座標 public int v=0; // 点数 } public class Pos { public int y=0; // Y 座標 public int x=0; // X 座標 }

4. m_judge が対戦結果で「1:黒勝ち, -1:白勝ち, 9:引き分け」です。
   乱数によって毎回結果が変わるとデバッグに差し支えるので 12345 で初期化しています。
   

   int[,] m_t = new int[3, 3]; int[,] m_dat = new int[9, 2]; // 手の記録 int m_num; // m_datのIndex bool m_sente= false; // 人間側先手フラグ int m_judge; // 対戦結果 Cell m_top = new Cell(); Pos m_pos = new Pos(); Random rand = new Random(12345); //シード値で初期化

5. MyForm() から呼び出している CellInit(); 関数で多数の対局データを生成して学習します。
   

   public MyForm() { m_top= CellInit(); Init();

6. MyHandler() で盤を描画して、Fine() 関数でゲームの終了と勝敗を調べます。
   AddData() 関数で今対局した結果を学習するので、少しずつ強くなります？
   

   // ウインドウの描画 private void MyHandler(object sender, PaintEventArgs e) { Graphics g = e.Graphics; g.DrawImage(new Bitmap("c:\\data\\test\\game3.gif"), new PointF(10F, 10F)); for (int y = 0; y < 3; y++) for (int x = 0; x < 3; x++) { if (m_t[y, x]==1) g.DrawImage(new Bitmap("c:\\data\\test\\koma_b.gif"), new PointF(x * 61 + 28, y * 61 + 24)); if (m_t[y, x]==-1) g.DrawImage(new Bitmap("c:\\data\\test\\koma_w.gif"), new PointF(x * 61 + 28, y * 61 + 24)); } if (m_judge == 0) { m_judge = Fine(m_t); AddData(m_judge * 3, m_num, m_top, m_dat); if (m_judge==1) MessageBox.Show("黒の勝ち"); if (m_judge==-1) MessageBox.Show("白の勝ち"); if (m_judge==9) MessageBox.Show("引き分け"); } }

7. コンピュータが考える Think() 関数では Cell のリンクをたどり、最も有利な手を選びます。
   次の手が登録されていないときは Next() 関数を呼び出して乱数で手を決めます。
   学習したデータが少ないときは、この関数が呼ばれることが多くなります。
   Debug.WriteLine() と DebugList() で、Index と選べる候補手を印字してみました。
   

   public Pos Think(int[,] dat, int[,] t) { Cell p,q; int i,k,v,best=0; Debug.WriteLine("NUM:" + m_num); p=q= m_top; for(i=0; i<m_num; i++) { if (p.AL == null) return Next(m_num, t); for (k=0; k<p.AL.Count; k++) { q= (Cell)p.AL[k]; if (q.y==dat[i,0] && q.x==dat[i,1]) break; } if (k>=p.AL.Count) return Next(m_num, t); // 未登録 p= q; } v = -1000000; // マシンが先手のときは最大値 if (m_sente) v= 1000000; // マシンが後手のときは最小値 if (p.AL == null) return Next(m_num, t); DebugList(p.AL); for (k = 0; k < p.AL.Count; k++) { q = (Cell)p.AL[k]; if (m_sente && v>q.v) // マシンが後手 { v= q.v; best= k; } if (!m_sente && v<q.v) // マシンが先手 { v= q.v; best= k; } } m_pos.y = ((Cell)p.AL[best]).y; m_pos.x = ((Cell)p.AL[best]).x; return m_pos; }

8. Next() 関数では乱数を使って打つ手を決めます。
   なるべくこの関数が呼ばれることが無いように沢山のデータを学習することが必要です。
   

   // 乱数で選択 public Pos Next(int num, int[,] t) { Pos p = new Pos(); int r; r= rand.Next(9-num); for(p.y=0; p.y<3; p.y++) for(p.x=0; p.x<3; p.x++) { if (t[p.y, p.x] == 0) { if (r<1) return p; r--; } } return p; }

9. 事前に Cell をリンクして手を学習する関数です。
   Next() 関数を呼び出して、打つ手を乱数で決めています。
   

   // Cell に手を記録させる public Cell CellInit() { Cell top = new Cell(); Pos ps; int ret=0, num; for (int j=0; j<2000000; j++) { ret = 0; for (int y = 0; y < 3; y++) for (int x = 0; x < 3; x++) m_t[y, x] = 0; // dat[9] に一局の棋譜を格納 for (num=0; num<9; num++) { ps = Next(num, m_t); if (num % 2 == 0) m_t[ps.y, ps.x] = 1; else m_t[ps.y, ps.x] = -1; m_dat[num, 0] = ps.y; m_dat[num, 1] = ps.x; ret = Fine(m_t); if (ret != 0) { num++; break; } } AddData(ret, num, top, m_dat); } return top; }

10. 一局のデータを Cell に登録する関数です。
    

    // dat[] の一局を top(Cell) に登録(v:評価値, num:datの件数) public void AddData(int ret, int num, Cell top, int[,] dat) { Cell pt = top; int k,v; v= ret; if (v>8) v=0; // 引き分けのとき for (int i=0; i<num; i++) { k = AddCell(pt, i, dat[i, 0], dat[i, 1]); pt = (Cell)pt.AL[k]; pt.v += v; } }

11. ArrayList に一件のセルを追加する関数です。
    ☆Debug 関数以降は直接プログラムに関係しないデバッグに用いる関数です。
    

    // pt の ArrayList に i, y, x のセルを追加する public int AddCell(Cell pt, int i, int y, int x) { Cell wk,wk2; int j; wk = new Cell(); wk.n = i; wk.y = y; wk.x = x; if (pt.AL==null) pt.AL= new ArrayList(); for (j=0; j<pt.AL.Count; j++) { wk2 = (Cell)pt.AL[j]; if (wk2.y==y && wk2.x==x) break; } if (j>=pt.AL.Count) pt.AL.Add(wk); return j; }

12. １００万件のデータ登録は約７秒で終わるのですが、次のようなミスがあります。
    コンピュータの先手でプレイします。
    ６手目で勝ちを逃して、引き分けになりました。
    

    ●4 ・ 〇3 ・ ●0 ●6 ●2 〇1 〇5

    同じようなパターンでも黒が勝ちます。
    

    〇3 ・ 〇5 ・ ●0 〇1 ●4 ●6 ●2

    白が最善手で引き分けます。
    

    〇1 〇7 ●2 ●4 ●0 〇5 〇3 ●6 ・

    コンピュータの後手では適切にプレイされます。
    

    ●2 〇5 ・ 〇7 ●0 ●6 〇1 ●4 〇3

    ●0 〇3 ●2 ●6 〇1 〇5 〇7 ●4 ・

    ●2 ●0 〇3 〇5 〇1 ●6 ●4 ・ ・

13. ２００万件のデータ登録は約１２秒かかるのですが、先のミスが無くなりました。
    

    ●4 ・ 〇3 ●6 ●0 ・ ●2 〇1 〇5

14. このプログラムのウイークポイントを発見しました。
    人間先手のとき、３手目で明らかなミスを犯しています。
    

    ・ ・ ・ ●2 ●0 ●4 〇1 ・ 〇3

    人間なら二目並んでいれば止めると言う簡単なことなのですが。 (^_^;)
    次の課題として、事前に学習する対局数を減らすことと、ウイークポイントの解消を考えます。
    

[Next Chapter ↓] 三目並べゲーム－３
[Previous Chapter ↑] 三目並べゲーム

超初心者のプログラム入門(C# Frame Work)