はじめに
YouTubeを見ているとオセロにおいて9手で白が全滅する（黒一色になる）手順が57種類あると紹介されていました。秒で勝つオセロ 9手で全滅 - YouTube
突然ですが今回はその57種類の手順をすべて求めるプログラミングに挑戦してみます。
結果
ルービックキューブのプログラミングに以前挑戦しました。その時と同じ「深さ優先探索」を行いました。なんと2秒で探索が終わりました。
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:02.0492755)
C#コード
メインコード（Program.cs）
盤面を表すBoardクラスと深さ優先探索のためのSearchクラスをあとで紹介します。メインはSearchクラスのメソッドを実行するだけです。
using System.Diagnostics; namespace reversi; 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); } }
Boardクラス（Board.cs）
namespace reversi; class Board { private readonly UInt64 init = 1; private readonly UInt64 right_left_watcher = Convert.ToUInt64("7E7E7E7E7E7E7E7E", 16); private readonly UInt64 upper_lower_watcher = Convert.ToUInt64("00FFFFFFFFFFFF00", 16); private readonly UInt64 around_watcher = Convert.ToUInt64("007E7E7E7E7E7E00", 16); public UInt64 black; public UInt64 white; public int CurrentColor; public Dictionary<int, UInt64> possiblePos = new Dictionary<int, UInt64>(); public Board(UInt64 black_stone, UInt64 white_stone, int turn) { black = black_stone; white = white_stone; CurrentColor = turn; if (CurrentColor == 1) { update_possiblePos(black, white); } else { update_possiblePos(white, black); } } public Board move(int x) { UInt64 rev = possiblePos[x]; UInt64 new_black; UInt64 new_white; if (CurrentColor == 1) { new_black = black ^ ((init << x) | rev); new_white = white ^ rev; } else { new_black = black ^ rev; new_white = white ^ (init << x | rev); } return new Board(new_black, new_white, CurrentColor * -1); } public void display() { foreach (int i in Enumerable.Range(0, 8)) { foreach (int j in Enumerable.Range(0, 8)) { if ((black & init << (8 * i + j)) != 0) { Console.Write(" O "); } else { Console.Write(((white & init << (8 * i + j)) != 0) ? " x " : " . "); } } Console.WriteLine(); Console.WriteLine(); } } public void update_possiblePos(UInt64 turn, UInt64 not_turn) { UInt64 mask; UInt64 tmp; UInt64 rev; possiblePos.Clear(); for (int i = 0; i < 64; i++) { //着手箇所は空白でなければダメ //空きマスが「0」で表されているUInt64と着手箇所との比較 //空白でなければcontinue UInt64 check_position = init << i; if (((turn | not_turn) & (check_position)) != 0) continue; rev = 0; //右方向チェック tmp = 0; mask = check_position << 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; while((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; } if ((mask & turn) != 0) rev |= tmp; } //左方向チェック tmp = 0; mask = check_position >> 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 1; while ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 1; } if ((mask & turn) != 0) rev |= tmp; } //上方向チェック tmp = 0; mask = check_position >> 8; if ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 8; while ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 8; } if ((mask & turn) != 0) rev |= tmp; } //下方向チェック tmp = 0; mask = check_position << 8; if ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 8; while ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 8; } if ((mask & turn) != 0) rev |= tmp; } //右上方向チェック tmp = 0; mask = check_position >> 7; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 7; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 7; } if ((mask & turn) != 0) rev |= tmp; } //右下方向チェック tmp = 0; mask = check_position << 9; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 9; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 9; } if ((mask & turn) != 0) rev |= tmp; } //左上方向チェック tmp = 0; mask = check_position >> 9; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 9; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 9; } if ((mask & turn) != 0) rev |= tmp; } //左下方向チェック tmp = 0; mask = check_position << 7; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 7; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 7; } if ((mask & turn) != 0) rev |= tmp; } if (rev != 0) possiblePos.Add(i, rev); } } }
Searchクラス（Search.cs）
namespace reversi; 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; } } }
開発環境
ASRock DeskMini H470 CPU: Core i7 11700 メモリ：16G 2667MHz Windows 10 Visual Studio Community 2022 Preview 4.0 .NET 6.0.0 rc1
解説
解説記事は別記事で書いています。【C#】【オセロ】解説記事 part 1 - パソコン関連もろもろ
【C#】【オセロ】解説記事 part 2 - パソコン関連もろもろ
【C#】【オセロ】解説記事 part 3 - パソコン関連もろもろ
参考にさせて頂いたサイト
C#でパズルを解く - 協力最短詰めオセロ - Qiitaオセロをビットボードで実装する - Qiita
オセロにおけるビットボード - Enpedia
