三目並べゲーム－３

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

プログラムの説明

1. 三目並べゲーム CSForm.cs のソースコードです。
   常識的な手を打つことで、事前に学習するゲーム数を大幅に減らすことが出来ました。
   

   // コンピュータとプレイする(VB, VW を登録) 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 vb=0; // 黒の勝ち数 public int vw=0; // 白の勝ち数 public int ve=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 == 3 || m_judge == -3 || m_judge == 9) return; m_judge = Fine(1, m_t); if (m_judge==3 || m_judge==-3 || m_judge == 9) { AddData(m_judge, m_num, m_top, m_dat); } if (m_judge==3) MessageBox.Show("黒の勝ち"); if (m_judge==-3) 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>2 || m_judge==-3) 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==false マシンが先手) public Pos Think(int[,] dat, int[,] t) { Cell p,q; int i,k,v,best=0; p= q= m_top; for (i=0; i<m_num; i++) { if (p.AL == null) return Better(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 Better(m_num, t); // 未登録 p= q; } if (p.AL == null) return Better(m_num, t); v = -100000; for(k=0; k<p.AL.Count; k++) { q = (Cell)p.AL[k]; if (!m_sente && v<q.vb+q.ve) // マシンが先手のときは vb { v= q.vb+q.ve; best= k; } if (m_sente && v<q.vw+q.ve) // マシンが後手のときは vw { v= q.vw+q.ve; best= k; } } if (v<=0) return Better(m_num, t); m_pos.y = ((Cell)p.AL[best]).y; m_pos.x = ((Cell)p.AL[best]).x; return m_pos; } // 常識的な手を選択 public Pos Better(int num, int[,] t) { int c,ret; c= 1; if (m_num%2 == 1) c= -1; ret= Fine(c, t); if (ret!=0) return m_pos; return Next(num, t); } // 乱数で選択 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; } // 終了,勝ち手, 防御手(c:手番) public int Fine(int c, int[,] t) { int[] tw = new int[8]; int i,wk; 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 3; if (tw[i]==-3) return -3; } // 勝ち手(３目になる) wk= c+c; for(i=0; i<8; i++) { if (tw[i]==wk) { Set_YX(i,t); return wk; } } // 防御手(２目を止める) wk= 0-wk; for(i=0; i<8; i++) { if (tw[i]==wk) { Set_YX(i, t); return 0-c; } } return 0; } // ３目の残り１個の座標を m_pos に設定 public void Set_YX(int k, int[,] t) { for(int i=0; i<3; i++) { switch(k) { case 0: case 1: case 2: if (t[k,i]==0) { m_pos.y= k; m_pos.x= i; return; } break; case 3: case 4: case 5: if (t[i,k-3]==0) { m_pos.y= i; m_pos.x= k-3; return; } break; case 6: if (t[i,i]==0) { m_pos.y= i; m_pos.x= i; return; } break; case 7: if (t[i,2-i]==0) { m_pos.y= i; m_pos.x= 2-i; return; } break; } } } // ゲームの初期化 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 List の初期化(事前に手を記録) public Cell CellInit() { Cell top = new Cell(); Pos ps; int ret=0, num, c; for (int j=0; j<20000; j++) { ret = 0; for (int y = 0; y < 3; y++) for (int x = 0; x < 3; x++) m_t[y, x] = 0; // m_dat[9] に一局の棋譜を格納 c= 1; // 黒の手番 for (num=0; num<9; num++) { if (num>3) { ret = Fine(c, m_t); if (ret==3 || ret==-3 || ret==9) break; } if (ret!=0) ps= m_pos; else ps= Better(num, m_t); m_t[ps.y, ps.x]= c; m_dat[num, 0] = ps.y; m_dat[num, 1] = ps.x; c= 0-c; // 手番を変える } if (num==9) ret = 9; AddData(ret, num, top, m_dat); } return top; } // dat[] の一局を top(Cell) に登録(ret:評価値, num:datの件数) public void AddData(int ret, int num, Cell top, int[,] dat) { Cell pt = top; int k; for (int i=0; i<num; i++) { k = AddCell(pt, i, dat[i, 0], dat[i, 1]); pt = (Cell)pt.AL[k]; switch(ret) { case 9: pt.ve++; break; case 3: pt.vb++; break; case -3: pt.vw++; break; } } } // 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+" VB:"+wk.vb+" VW:"+wk.vw+" VE:"+wk.ve+"\n"); } } // Cell(セル)から再帰で印字(lev:0 は一手目, lev:1 は二手目・・・) public void DebugCell(int lev, Cell top) { Cell wk; if (lev>=9 || top==null) return; if (top.AL == null) 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+" VB:"+wk.vb+" VW:"+wk.vw+" VE:"+wk.ve); if (wk.AL != null) DebugCell(lev+1, wk); } } // dat[sz,2] を編集して盤を印字 public void DebugMat(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. 三目並べゲーム－２ では、未知の局面に出会うと乱数でプレイしていました。
   これではミスを犯す確率が高く、弱いプログラムになってしまいます。
   三目並べゲームでプレイヤーがプレイする場合、最低限次のことを考えるでしょう。
   ①既に勝負が決している(３目並んでいる)
   ②自分の手番で３目並べることが出来る(手番の勝ち)
   ③勝てない時は、相手が２目並んでいるかを調べる(３目並ぶのを阻止)
   ④それ以外のときは、乱数でプレイする
   次に勝敗の記録ですが、勝ち負けを相殺した値では無く「勝数, 負数, 引分数」に分けて記録します。
   そうすることによって、後手番でリストに負けしか登録されていない時に新しい手を選ぶ余地を残します。
   
3. 最も変わったのは Fine() 関数です。
   ゲームの終了を調べるだけでなく、前に述べた①②③を担います。
   

   戻り値	説明
   3	黒番の勝ちです
   -3	白番の勝ちです
   手番*2	手番の勝ちです
   反手番*2	２目を止めます

   public int Fine(int c, int[,] t) { int[] tw = new int[8]; int i,wk; 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 3; if (tw[i]==-3) return -3; } // 勝ち手(３目になる) wk= c+c; for(i=0; i<8; i++) { if (tw[i]==wk) { Set_YX(i,t); return wk; } } // 防御手(２目を止める) wk= 0-wk; for(i=0; i<8; i++) { if (tw[i]==wk) { Set_YX(i, t); return 0-c; } } return 0; }

4. 「②自分の手番で３目並べることが出来る, ③勝てない時は、相手が２目並んでいることを調べる」の時に石を置く座標を調べます。
   Set_YX() 関数で YX 座標を調べて m_pos に設定します。
   

   // ３目の残り１個の座標を m_pos に設定 public void Set_YX(int k, int[,] t) { for(int i=0; i<3; i++) { switch(k) { case 0: case 1: case 2: if (t[k,i]==0) { m_pos.y= k; m_pos.x= i; return; } break; case 3: case 4: case 5: if (t[i,k-3]==0) { m_pos.y= i; m_pos.x= k-3; return; } break; case 6: if (t[i,i]==0) { m_pos.y= i; m_pos.x= i; return; } break; case 7: if (t[i,2-i]==0) { m_pos.y= i; m_pos.x= 2-i; return; } break; } } }

5. Fine() 関数を利用して、常識的な手を選択する Better() 関数です。
   

   // 常識的な手を選択 public Pos Better(int num, int[,] t) { int c,ret; c= 1; if (m_num%2 == 1) c= -1; ret= Fine(c, t); if (ret!=0) return m_pos; return Next(num, t); }

6. Think() から Better() 関数を呼び出すことで、常識的な手を打つことが出来ます。
   ArrayList に負ける手しか登録されていない時は Better() 関数で新しい手を選びます。
   

   // コンピュータが考える(m_sente==false マシンが先手) public Pos Think(int[,] dat, int[,] t) { Cell p,q; int i,k,v,best=0; p= q= m_top; for (i=0; i<m_num; i++) { if (p.AL == null) return Better(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 Better(m_num, t); // 未登録 p= q; } if (p.AL == null) return Better(m_num, t); v = -100000; for(k=0; k<p.AL.Count; k++) { q = (Cell)p.AL[k]; if (!m_sente && v<q.vb+q.ve) // マシンが先手のときは vb { v= q.vb+q.ve; best= k; } if (m_sente && v<q.vw+q.ve) // マシンが後手のときは vw { v= q.vw+q.ve; best= k; } } if (v<=0) return Better(m_num, t); m_pos.y = ((Cell)p.AL[best]).y; m_pos.x = ((Cell)p.AL[best]).x; return m_pos; }

7. CellInit() でも Better() 関数を利用することで学習回数が大幅に少なくなると共に、余計な登録が無くなることで初期登録の時間が減少しました。
   

   // Cell List の初期化(事前に手を記録) public Cell CellInit() { Cell top = new Cell(); Pos ps; int ret=0, num, c; for (int j=0; j<20000; j++) { ret = 0; for (int y = 0; y < 3; y++) for (int x = 0; x < 3; x++) m_t[y, x] = 0; // m_dat[9] に一局の棋譜を格納 c= 1; // 黒の手番 for (num=0; num<9; num++) { if (num>3) { ret = Fine(c, m_t); if (ret==3 || ret==-3 || ret==9) break; } if (ret!=0) ps= m_pos; else ps= Better(num, m_t); m_t[ps.y, ps.x]= c; m_dat[num, 0] = ps.y; m_dat[num, 1] = ps.x; c= 0-c; // 手番を変える } if (num==9) ret = 9; AddData(ret, num, top, m_dat); } return top; }

8. ☆Debug 関数以降は直接プログラムに関係しないデバッグに用いる関数です。
   今回のプログラムではウイークポイントも解消され、プレイヤーと対等にゲームをすることが出来ます。
   これで三山崩しゲームにディープラーニングを適用する微かな光が見えたようです。
   
9. １万件のデータ登録はすぐ終わるのですが、詳しく調べるとミスがありました。
   コンピュータが先手でプレイします。
   コンピュータが正しく応答した例です。
   

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

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

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

   プイヤーがミスをしてコンピュータが勝った例です。
   

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

   ４手目でコンピュータが勝ちを逃した例です。
   

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

10. コンピュータが後手でプレイします。
    コンピュータが正しく応答した例です。
    

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

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

    １手目でコンピュータが決定的なミスを犯した例です。
    

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

11. ２万件のデータを登録してみました。
    コンピュータが先手でプレイします。
    ４手目でコンピュータが勝ちを逃した例が解消されました。
    

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

    コンピュータ後手で決定的なミスを犯した例も解消されました。
    

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

    その代わり、コンピュータ先手のとき４手目で勝ちを逃す例が見つかりました。
    ＡＩを使ったからと言って、全てが簡単に解決するものでは無いようで、工夫する余地がある所がＡＩの魅力でしょうか？。
    

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

[Previous Chapter ↑] 三目並べゲーム－２

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