Final 関数

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

プログラムの説明

1. オセロゲームで最も面白い Final() 関数のテストをします。
   CSForm.cs のソースコードです。
   

   // 白番で Final 関数のテスト(黒番は右クリック) using System; using System.Drawing; using System.Windows.Forms; using System.Collections; using System.Diagnostics; public class MyForm : Form { int[,] m_t = new int[8, 8] {{ 0, -1, -1, -1, -1, -1, 0, 0 }, { 0, 1, -1, 1, 1, 1, -1, -1 }, { -1, -1, 1, -1, 1, 1, -1, -1 }, { -1, -1, -1, 1, -1, -1, 1, -1 }, { 1, -1, -1, 1, 1, -1, 1, -1 }, { 1, 1, -1, 1, -1, 1, 1, -1 }, { 0, 0, 1, -1, 1, 1, 1, -1 }, { 0, 1, 1, 1, 0, -1, -1, 0 }}; int m_teban= 0; int m_pos; // Constructor public MyForm() { BackColor = SystemColors.AppWorkspace; Width = 560; Height = 600; 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\\ban.gif"), new PointF(10F, 10F)); for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; 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)); } } m_teban= Pass(m_teban); } // マウスのクリック private void OnMyMouseDown(object sender, MouseEventArgs e) { int x, y; if (m_teban==9) { Pass(9); return; } x = (e.X - 28) / 61; y = (e.Y - 24) / 61; if (e.Button == MouseButtons.Right) { if (Reverse(m_teban, x, y, m_t) == false) { MessageBox.Show("置くことはできません 手番:" + m_teban); return; } } if (e.Button == MouseButtons.Left) { Final(0, m_teban, m_t); if (Reverse(m_teban, m_pos, m_t) == false) { string str = "Error Play C:" + m_teban + "[" + m_pos + "]"; MessageBox.Show(str); return; } } m_teban = 0-m_teban; // 手番を反転 Invalidate(); } // パス, 終局を調べる int Pass(int c) { int w; ArrayList array; if (c==0) return -1; // 白番で Start if (c!=9) // パスを調べる { array = Search(c, m_t); if (array.Count>0) return c; } w= 0-c; // 反手番で調べる array = Search(w, m_t); if (array.Count > 0) { if (c==1) { MessageBox.Show("黒はパスです"); } else { MessageBox.Show("白はパスです"); } return w; // 手番を反転 } string str= "★Game Over 黒:" + Count(1, m_t) + " 白:" + Count(-1, m_t); MessageBox.Show(str); return 9; // 終局 } // ｔ[yp,xp] に打てるか調べる bool Check(int c, int xp, int yp, int[,] t) { int i,j,x,y; int nc = 0-c; if (yp>7 || xp>7 || yp<0 || xp<0 || c==0 || t[yp,xp]!=0) return false; for(i=-1; i<2; i++) for(j=-1; j<2; j++) { y = yp + i; // 上下左右を調べる x = xp + j; if (y<8 && x<8 && y>=0 && x>=0 && t[y,x]==nc) { for(; y<8 && x<8 && y>=0 && x>=0 && t[y,x]==nc; y+=i,x+=j); if (y<8 && x<8 && y>=0 && x>=0 && t[y,x]==c) return true; } } return false; //置くことができない } bool Check(int c, int pos, int[,] t) { int x,y; y= pos/10; x= pos%10; return Check(c,x,y,t); } // ｔ[y,x] に駒を置いて、挟んだ駒を裏返す bool Reverse(int c, int xp, int yp, int[,] t) { int i, j, x, y; bool sw = false; int nc = 0-c; if (yp > 7 || xp > 7 || yp < 0 || xp < 0 || c == 0 || t[yp, xp] != 0) return false; for (i = -1; i < 2; i++) for (j = -1; j < 2; j++) { y = yp + i; x = xp + j; if (y < 8 && x < 8 && y >= 0 && x >= 0 && t[y, x] == nc) { for (; y < 8 && x < 8 && y >= 0 && x >= 0 && t[y, x] == nc; y += i, x += j) ; if (y < 8 && x < 8 && y >= 0 && x >= 0 && t[y, x] == c) { for (; y != yp || x != xp; y -= i, x -= j) t[y, x] = c; sw = true; } } } if (sw == false) return false; t[yp, xp] = c; return true; } bool Reverse(int c, int pos, int[,] t) { int x,y; y= pos/10; x= pos%10; return Reverse(c,x,y,t); } // 打てる手をサーチ ArrayList Search(int c, int[,] t) { int x,y,pos; ArrayList array= new ArrayList(); for(y=0; y<8; y++) for(x=0; x<8; x++) { if (Check(c,x,y,t)) { pos= y*10 + x; array.Add(pos); } } return array; } // 駒のカウント int Count(int c, int[,] t) { int cnt; cnt = 0; for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; x++) if (t[y, x] == c) cnt++; } return cnt; } void t_Log(int sz, int[,] t) { string str = ""; for (int y = 0; y < sz; y++) { for (int x = 0; x < sz; x++) { if (t[y, x] == 0) str = str + "."; if (t[y, x] == 1) str = str + "X"; if (t[y, x] == -1) str = str + "O"; } str = str + "\n"; } Debug.Write(str); } //★ t[8,8] の局面を c の手番で最後まで読み切る int Final(int lev, int c, int[,] t) { int[,] w_t; ArrayList array; int best,xy,i,ans; int nc; if (lev>20) { MessageBox.Show("Final Call Over Level"); return(Count(-1,t)-Count(1,t)); } nc= 0-c; array= Search(c, t); if (array.Count==0) { array= Search(nc, t); // パスの時反転して検索 if (array.Count==0) // ゲーム終了まで到達 { return(Count(-1,t)-Count(1,t)); } return(Final(lev+1,nc,t)); //★反転して再起コール★ } xy = 0; best= 60000; if (c==-1) best= -60000; foreach(int DAT in array) { w_t = (int[,])t.Clone(); if (Reverse(c,DAT,w_t)==false) { t_Log(8,t); MessageBox.Show("Final Reverce Error"); } ans= Final(lev+1,nc,w_t); //★再起コール★ if (best<ans && c==-1) { best= ans; xy= DAT; } if (best>ans && c==1) { best= ans; xy= DAT; } } array.Clear(); if (lev==0) m_pos= xy; //lev=0 のとき必ずここを通る return best; } } class osero { public static void Main() { MyForm mf = new MyForm(); Application.Run(mf); } }

2. Final() 関数をテストする「白番で残り９手」の局面です。
   左クリック(白番で Final 関数を呼び出す)から始めて下さい。
   

   int[,] m_t = new int[8, 8] {{ 0, -1, -1, -1, -1, -1, 0, 0 }, { 0, 1, -1, 1, 1, 1, -1, -1 }, { -1, -1, 1, -1, 1, 1, -1, -1 }, { -1, -1, -1, 1, -1, -1, 1, -1 }, { 1, -1, -1, 1, 1, -1, 1, -1 }, { 1, 1, -1, 1, -1, 1, 1, -1 }, { 0, 0, 1, -1, 1, 1, 1, -1 }, { 0, 1, 1, 1, 0, -1, -1, 0 }};

   説明の都合上、左上から空いている箇所に番号を振ります。
   

   １ ２ ３ ４ ５ ６ ７ ８ ９

3. OnMyMouseDown() 関数では、右ボタンでクリックされた座標に駒を置きます。
   左ボタンのクリックで Final() 関数を呼び出します。
   m_t[8,8] で定義した局面は白の手番なので、Pass() 関数では白番(コンピュータ側)のプレイに設定して下さい。
   

   private void OnMyMouseDown(object sender, MouseEventArgs e) { int x, y; if (m_teban==9) { Pass(9); return; } x = (e.X - 28) / 61; y = (e.Y - 24) / 61; if (e.Button == MouseButtons.Right) { if (Reverse(m_teban, x, y, m_t) == false) { MessageBox.Show("置くことはできません 手番:" + m_teban); return; } } if (e.Button == MouseButtons.Left) { Final(0, m_teban, m_t); if (Reverse(m_teban, m_pos, m_t) == false) { string str = "Error Play C:" + m_teban + "[" + m_pos + "]"; MessageBox.Show(str); return; } } m_teban = 0-m_teban; // 手番を反転 Invalidate(); }

4. t[8,8] の局面を c の手番で最後まで読み切る Final() 関数です。
   １０手ぐらいなら待ち時間は気になりませんが、手数が増えるにつれ飛躍的に増えます。
   渡された局面を c の手番で列挙して、プレイした局面で Final() 関数を再帰的に呼び直します。
   再起呼び出しは２０を超えるか、終局になるまで続きます。
   再起から戻ると列挙した手から最善の手を求めます。
   最終的に m_pos にベストの手が格納されます。
   

   int Final(int lev, int c, int[,] t) { int[,] w_t; ArrayList array; int best,xy,i,ans; int nc; if (lev>20) { MessageBox.Show("Final Call Over Level"); return(Count(-1,t)-Count(1,t)); } nc= 0-c; array= Search(c, t); if (array.Count==0) { array= Search(nc, t); // パスの時反転して検索 if (array.Count==0) // ゲーム終了まで到達 { return(Count(-1,t)-Count(1,t)); } return(Final(lev+1,nc,t)); //★反転して再起コール★ } //foreach(int DAT in array) //{ Debug.Write("[" + DAT + "] "); } xy = 0; best= 60000; if (c==-1) best= -60000; foreach(int DAT in array) { w_t = (int[,])t.Clone(); if (Reverse(c,DAT,w_t)==false) { t_Log(8,t); MessageBox.Show("Final Reverce Error"); } ans= Final(lev+1,nc,w_t); //★再起コール★ //Debug.Write("Ans Lev:" + lev + " C:" + nc + " POS:" + DAT + " V:" + ans + "\n"); if (best<ans && c==-1) { best= ans; xy= DAT; } if (best>ans && c==1) { best= ans; xy= DAT; } } array.Clear(); if (lev==0) m_pos= xy; //lev=0 のとき必ずここを通る //Debug.Write("Best Lev:" + lev + " [" + m_pos + "] V:" + best + "\n"); return best; }

5. この局面の最善手は、白の先手で「２６７３９４１８５」で「黒＝２３, 白＝４１」になります。
   

   .OOOOO.. 1 23 .XOXXXOO 4 OOXOXXOO OOOXOOXO XOOXXOXO XX0XOXXO ..XOXXXO 56 .XXX.OO. 7 8 9

   黒が２手目で常識的な３に置いてみましょう。
   「２３９１４６７５８」となり「黒＝２２, 白＝４２」と黒の駒が少なくなります。
   黒の手を色々工夫して試してみて下さい。
   最善手が最も有利なことが解っていただけると思います。
   終盤２０手ぐらい読み切れたら鬼に金棒なのですが、十数手が限度のようです。
   

[Next Chapter ↓] コンピュータがプレイする
[Previous Chapter ↑] プラットホーム

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