はじめにこの記事は以下の記事のサポート記事です。手順を細かく解説しています。
touch-sp.hatenablog.com
解説
前回までで盤面を表すBoardクラスが完成しました。
【C#】【オセロ】解説記事 part 1 - パソコン関連もろもろ
【C#】【オセロ】解説記事 part 2 - パソコン関連もろもろ
今回はSearchクラスとメインプログラムを作っていきます。
今回が最終回となります。
Searchクラス
以前ルービックキューブのプログラムを書いた時に参考にしたサイトがあります。ルービックキューブを解くプログラムを書いてみよう(中編:IDA*探索) - Qiita
やることは同じなので深さ優先探索のプログラムをほぼそのまま使わせてもらいました。解説も非常に詳しいのでそちらを参照して頂くのがよいと思います。
Pythonで書かてれいますがC#で書いてもほとんど変わりません。
depth_limited_searchメソッドの戻り値はbool型からvoidに変更しています。これは1通りの解答を見つけた時点で探索を打ち切らないようにするためです。深さ優先探索を打ち切るためにis_finishedというbool型の変数を設けています。
class Search { public List<int> current_solution; public Board board; bool is_finished = false; public Search() { UInt64 black = Convert.ToUInt64("0000000810000000", 16); UInt64 white = Convert.ToUInt64("0000001008000000", 16); board = new Board(black, white, 1); current_solution = new List<int> { 37 }; board = board.move(37); } private bool is_solved(Board board) { if (board.white == 0 || board.black == 0) return true; return false; } public void depth_limited_search(Board board, int depth) { if (depth == 0 && is_solved(board)) { Console.WriteLine(String.Join(" ", current_solution)); is_finished = true; return; } if (depth == 0) return; foreach(var x in board.possiblePos.Keys) { current_solution.Add(x); depth_limited_search(board.move(x), depth - 1); current_solution.RemoveAt(current_solution.Count - 1); } return; } public void start_search() { for (int depth = 1; depth < 20; depth++) { Console.WriteLine($"Start searching length {depth + 1}"); depth_limited_search(board, depth); if (is_finished == true) break; } } }
Searchオブジェクトを新しく作成した時には盤面は1手すすんだ状態になっています。最初の1手を固定しているためです。
ゴールは盤面がどちらか1色になった状態です。言い換えればどちらかの石の個数が0になった状態です。
石の状態を「0」か「1」で表しているのでゴール判定は非常に簡単になります。64桁すべて「0」の整数は0です。
private bool is_solved(Board board) { if (board.white == 0 || board.black == 0) return true; return false; }
メインプログラム
メインプログラムはSearchオブジェクトを作成して、その中のstart_searchメソッドを実行するだけです。class Program { static void Main(string[] args) { Stopwatch sw = new Stopwatch(); sw.Start(); Search search = new Search(); search.start_search(); sw.Stop(); TimeSpan ts = new TimeSpan(); ts = sw.Elapsed; Console.WriteLine("Finished!({0})", ts); } }
実行結果
Start searching length 2 Start searching length 3 Start searching length 4 Start searching length 5 Start searching length 6 Start searching length 7 Start searching length 8 Start searching length 9 37 29 18 42 34 43 21 26 50 37 29 18 42 34 43 30 26 50 37 29 18 44 53 34 33 45 21 37 29 18 44 53 38 39 45 21 37 29 18 44 53 45 21 9 0 37 29 18 44 53 45 21 20 12 37 29 18 44 53 45 21 34 33 37 29 18 44 53 45 21 38 39 37 29 18 44 53 45 21 52 60 37 29 18 44 53 45 21 54 63 37 29 18 44 53 46 30 38 39 37 29 19 43 51 20 21 22 15 37 29 19 43 51 20 21 34 33 37 29 19 43 51 20 21 38 39 37 29 19 43 51 20 21 50 57 37 29 21 45 53 20 19 18 9 37 29 21 45 53 20 19 34 33 37 29 21 45 53 20 19 38 39 37 29 21 45 53 20 19 54 63 37 29 22 44 51 34 33 43 19 37 29 22 44 51 38 39 43 19 37 29 22 44 51 42 26 34 33 37 29 22 44 51 43 19 20 12 37 29 22 44 51 43 19 34 33 37 29 22 44 51 43 19 38 39 37 29 22 44 51 43 19 50 57 37 29 22 44 51 43 19 52 60 37 29 22 46 38 45 19 30 54 37 29 22 46 38 45 26 30 54 37 43 18 21 20 29 51 19 22 37 43 34 29 20 45 38 44 52 37 43 34 29 52 38 39 44 20 37 43 34 29 52 45 38 44 20 37 43 34 45 52 29 38 44 20 37 45 19 20 13 29 38 44 52 37 45 19 20 13 38 39 44 52 37 45 19 20 21 29 53 18 9 37 45 19 20 21 29 53 34 33 37 45 19 20 21 29 53 38 39 37 45 19 20 21 29 53 54 63 37 45 19 20 21 29 54 13 5 37 45 19 20 21 29 54 53 61 37 45 19 20 21 34 33 29 53 37 45 19 20 21 38 39 29 53 37 45 26 20 13 29 38 44 52 37 45 26 20 13 38 39 44 52 37 45 26 34 53 17 33 44 8 37 45 53 29 19 20 21 18 9 37 45 53 29 19 20 21 34 33 37 45 53 29 19 20 21 38 39 37 45 53 29 19 20 21 54 63 37 45 53 29 21 20 19 18 9 37 45 53 29 21 20 19 34 33 37 45 53 29 21 20 19 38 39 37 45 53 29 21 20 19 54 63 37 45 53 34 26 17 33 44 8 37 45 53 38 31 34 33 29 20 Finished!(00:00:01.7341252)
2秒かからずに57通りの結果が返ってきました。
さいごに
今回は「最短で黒一色になる手順57通りをすべて求める」という目的に沿ってコードを書きました。今回の目的は達成されましたがさらに深くオセロの解析をしたいのであればパスになった時のコードを書く必要がありますので注意して下さい。possiblePosの要素数が0であれば手番をひっくり返すだけですのですぐに書けると思います。
間違いや改善点があればコメント頂けましたら幸いです。
プログラムはGitHubで公開しています。
GitHub - dai-ichiro/vs2022_reversi
