はじめに
テーマは「ルービックキューブの最短解を求める」ことです。「最短解」にこだわってぼちぼちとやっています。
この記事は前回の続きです。
touch-sp.hatenablog.com
前回は枝刈りなしの総当たりで8手問題まで解きました。(8手問題を約1分)
以前Pythonで同じことをした時はチューニングして13手問題2分まで行きました。
touch-sp.hatenablog.com
今回C#でPythonの時と全く同じことをして速度比較してみました。
結果
Python
# Start searching length 1 # 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 # Start searching length 10 # Start searching length 11 # Start searching length 12 # Start searching length 13 Finished! (135.14 sec.) Solution: L2 D F2 L2 D U L2 F2 B R F- U R
C#
Start searching lenght 0 Start searching lenght 1 Start searching lenght 2 Start searching lenght 3 Start searching lenght 4 Start searching lenght 5 Start searching lenght 6 Start searching lenght 7 Start searching lenght 8 Start searching lenght 9 Start searching lenght 10 Start searching lenght 11 Start searching lenght 12 Start searching lenght 13 L2 D F2 L2 D U L2 F2 B R F' U R Finished!(00:00:41.7746731)
なんとかかった時間が135秒から42秒になっています。C#の方が約3倍ほど速い結果でした。
枝刈り
とりあえず完成状態から5手動かすまでに出現するすべての局面を書き出しました。また、完成状態から6手動かした時のepの状態を書き出しました。
それを利用して速度アップしています。
5手動かすまでに出現するすべての局面とそこから完成までの手順を書き出す
局面を表すタプル((int, int, int, int))とそこから完成状態までの手順(string [])を辞書型で保存しました。Global.cs
using System.Collections.Generic; public static class Global { public static int[,] cp_move_table; public static int[,] co_move_table; public static int[,] eo_move_table; public static Dictionary<int, int[]> ep_move_dict = new Dictionary<int, int[]>() { {0, new int[]{ 0, 1, 2, 3, 7, 4, 5, 6, 8, 9, 10, 11 } }, {1, new int[]{ 0, 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 11 } }, {2, new int[]{ 0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10, 11 } }, {3, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8 } }, {4, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 8, 9 } }, {5, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 11, 8, 9, 10 } }, {6, new int[]{ 11, 1, 2, 7, 4, 5, 6, 0, 8, 9, 10, 3 } }, {7, new int[]{ 3, 1, 2, 0, 4, 5, 6, 11, 8, 9, 10, 7 } }, {8, new int[]{ 7, 1, 2, 11, 4, 5, 6, 3, 8, 9, 10, 0 } }, {9, new int[]{ 0, 5, 9, 3, 4, 2, 6, 7, 8, 1, 10, 11 } }, {10, new int[]{ 0, 2, 1, 3, 4, 9, 6, 7, 8, 5, 10, 11 } }, {11, new int[]{ 0, 9, 5, 3, 4, 1, 6, 7, 8, 2, 10, 11 } }, {12, new int[]{ 0, 1, 6, 10, 4, 5, 3, 7, 8, 9, 2, 11 } }, {13, new int[]{ 0, 1, 3, 2, 4, 5, 10, 7, 8, 9, 6, 11 } }, {14, new int[]{ 0, 1, 10, 6, 4, 5, 2, 7, 8, 9, 3, 11 } }, {15, new int[]{ 4, 8, 2, 3, 1, 5, 6, 7, 0, 9, 10, 11 } }, {16, new int[]{ 1, 0, 2, 3, 8, 5, 6, 7, 4, 9, 10, 11 } }, {17, new int[]{ 8, 4, 2, 3, 0, 5, 6, 7, 1, 9, 10, 11 } } }; }
State.cs
using System.Linq; class State { public int cp; public int co; public int[] ep; public int eo; public State(int cp, int co, int[] ep, int eo) { this.cp = cp; this.co = co; this.ep = ep; this.eo = eo; } public State apply_move(int move_num) { int new_cp = Global.cp_move_table[this.cp, move_num]; int new_co = Global.co_move_table[this.co, move_num]; int new_eo = Global.eo_move_table[this.eo, move_num]; int[] new_ep = Global.ep_move_dict[move_num].Select(x => this.ep[x]).ToArray(); return new State(new_cp, new_co, new_ep, new_eo); } }
Program.cs
using System; using System.IO; using System.Collections.Generic; using System.Linq; using System.Runtime.Serialization.Formatters.Binary; namespace solved_state_5 { class Program { static void Main(string[] args) { string[] r_move_names = { "U'", "U2", "U", "D'", "D2", "D", "L'", "L2", "L", "R'", "R2", "R", "F'", "F2", "F", "B'", "B2", "B" }; Global.cp_move_table = File_Operation.read_move_table("cp_move_table.data"); Global.co_move_table = File_Operation.read_move_table("co_move_table.data"); Global.eo_move_table = File_Operation.read_move_table("eo_move_table.data"); bool is_move_available(int pre, int now) { if (pre == -1) return true; if (pre / 3 == now / 3) return false; if (pre / 3 == 0 && now / 3 == 1) return false; //U→Dはダメ if (pre / 3 == 3 && now / 3 == 2) return false; //R→Lはダメ if (pre / 3 == 4 && now / 3 == 5) return false; //F→Bはダメ return true; } var moves = new List<int>(); //初期値 var result = new List<int[]>(); //結果を記録するリスト var moves_queue = new Queue<List<int>>(); moves_queue.Enqueue(new List<int>(moves)); while (moves_queue.Count != 0) { List<int> now = moves_queue.Dequeue(); if (now.Count > 0) { result.Add(now.ToArray()); } if (now.Count < 5) { for (int i = 0; i < 18; i++) { int prev_move = now.Count == 0 ? -1 : now.Last(); if (is_move_available(prev_move, i)) { //値型のリストの場合は以下でディープコピーになる List<int> temp_list = new List<int>(now); temp_list.Add(i); moves_queue.Enqueue(temp_list); } } } } int ep_to_index(int[] ep) { int index = 0; for (int i = 0; i < 12; i++) { index *= 12 - i; for (int j = i + 1; j < 12; j++) { if (ep[i] > ep[j]) index += 1; } } return index; } int[] scramble2state(int[] moves) { State state = new State(0, 0, Enumerable.Range(0, 12).ToArray(), 0); foreach (int each_move in moves) { state = state.apply_move(each_move); } return new int[] { state.cp, state.co, ep_to_index(state.ep), state.eo }; } var all_state_5 = new Dictionary<(int, int, int, int), string[]>(); foreach (int[] each_result in result) { int[] result_state = scramble2state(each_result); (int, int, int, int) result_state_tuple = (result_state[0], result_state[1], result_state[2], result_state[3]); if (!(all_state_5.ContainsKey(result_state_tuple))) { all_state_5.Add(result_state_tuple, each_result.Reverse().Select(x => r_move_names[x]).ToArray()); } } Console.WriteLine(all_state_5.Count.ToString()); using FileStream fs = new FileStream("all_state_5.data", FileMode.Create); BinaryFormatter bf = new BinaryFormatter(); bf.Serialize(fs, all_state_5); } } }
5手目に現れる局面を保存(手順なし)
局面を表すタプル((int, int, int, int))をHashSetで保存しました。終了判定に使用しています。Program.cs
using System; using System.Collections.Generic; using System.IO; using System.Runtime.Serialization.Formatters.Binary; using System.Linq; namespace read_file { class Program { static void Main(string[] args) { string path = "all_state_5.data"; Dictionary<(int, int, int, int), string[]> all_state_5; FileStream fs = new FileStream(path, FileMode.Open); BinaryFormatter bf = new BinaryFormatter(); all_state_5 = (Dictionary<(int, int, int, int), string[]>)bf.Deserialize(fs); Console.WriteLine(all_state_5.Count.ToString()); var hash_result_5 = new HashSet<(int, int, int, int)>(); foreach(var m in all_state_5) { if(m.Value.Count() == 5) hash_result_5.Add(m.Key); } using FileStream fs_2 = new FileStream("hash_result_5.data", FileMode.Create); BinaryFormatter bf_2 = new BinaryFormatter(); bf.Serialize(fs_2, hash_result_5); Console.WriteLine(hash_result_5.Count.ToString()); } } }
完成状態から6手動かした時のepの状態を書き出す
Global.cs
using System.Collections.Generic; namespace prune { public static class Global { public static Dictionary<int, int[]> ep_move_dict = new Dictionary<int, int[]>() { {0, new int[]{ 0, 1, 2, 3, 7, 4, 5, 6, 8, 9, 10, 11 } }, {1, new int[]{ 0, 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 11 } }, {2, new int[]{ 0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10, 11 } }, {3, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8 } }, {4, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 8, 9 } }, {5, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 11, 8, 9, 10 } }, {6, new int[]{ 11, 1, 2, 7, 4, 5, 6, 0, 8, 9, 10, 3 } }, {7, new int[]{ 3, 1, 2, 0, 4, 5, 6, 11, 8, 9, 10, 7 } }, {8, new int[]{ 7, 1, 2, 11, 4, 5, 6, 3, 8, 9, 10, 0 } }, {9, new int[]{ 0, 5, 9, 3, 4, 2, 6, 7, 8, 1, 10, 11 } }, {10, new int[]{ 0, 2, 1, 3, 4, 9, 6, 7, 8, 5, 10, 11 } }, {11, new int[]{ 0, 9, 5, 3, 4, 1, 6, 7, 8, 2, 10, 11 } }, {12, new int[]{ 0, 1, 6, 10, 4, 5, 3, 7, 8, 9, 2, 11 } }, {13, new int[]{ 0, 1, 3, 2, 4, 5, 10, 7, 8, 9, 6, 11 } }, {14, new int[]{ 0, 1, 10, 6, 4, 5, 2, 7, 8, 9, 3, 11 } }, {15, new int[]{ 4, 8, 2, 3, 1, 5, 6, 7, 0, 9, 10, 11 } }, {16, new int[]{ 1, 0, 2, 3, 8, 5, 6, 7, 4, 9, 10, 11 } }, {17, new int[]{ 8, 4, 2, 3, 0, 5, 6, 7, 1, 9, 10, 11 } } }; } }
State.cs
using System.Linq; namespace prune { class State { public int[] ep; public State(int[] ep) { this.ep = ep; } public State apply_move(int move_num) { int[] new_ep = Global.ep_move_dict[move_num].Select(x => this.ep[x]).ToArray(); return new State(new_ep); } } }
Program.cs
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Runtime.Serialization.Formatters.Binary; namespace prune { class Program { static void Main(string[] args) { bool is_move_available(int pre, int now) { if (pre == -1) return true; if (pre / 3 == now / 3) return false; if (pre / 3 == 0 && now / 3 == 1) return false; //U→Dはダメ if (pre / 3 == 3 && now / 3 == 2) return false; //R→Lはダメ if (pre / 3 == 4 && now / 3 == 5) return false; //F→Bはダメ return true; } int ep_to_index(int[] ep) { int index = 0; for (int i = 0; i < 12; i++) { index *= 12 - i; for (int j = i + 1; j < 12; j++) { if (ep[i] > ep[j]) index += 1; } } return index; } int scramble2state(int[] moves) { State temp_state = new State(Enumerable.Range(0, 12).ToArray()); foreach (int each_move in moves) { temp_state = temp_state.apply_move(each_move); } return ep_to_index(temp_state.ep); } var moves = new List<int>(); //初期値 var result = new List<int[]>(); //結果を記録するリスト void try_move(int depth) { if (depth == 0) { result.Add(moves.ToArray()); return; } int prev_move = moves.Count == 0 ? -1 : moves.Last(); foreach(int i in Enumerable.Range(0, 18)) { if(is_move_available(prev_move, i)) { moves.Add(i); try_move(depth - 1); moves.RemoveAt(moves.Count - 1); } } } int move_count = 6; try_move(move_count); HashSet<int> finla_result = new HashSet<int>(result.Select(x => scramble2state(x)).ToList()); string save_file_path = $"ep_exist_hash_{move_count}.data"; Console.WriteLine(result.Count.ToString()); Console.WriteLine(finla_result.Count.ToString()); using FileStream fs = new FileStream(save_file_path, FileMode.Create); BinaryFormatter bf = new BinaryFormatter(); bf.Serialize(fs, finla_result); } } }
メインのコード
Global.cs
using System.Collections.Generic; namespace cube_solver { public static class Global { public static int[,] cp_move_table; public static int[,] co_move_table; public static int[,] eo_move_table; public static Dictionary<int, int[]> ep_move_dict = new Dictionary<int, int[]>() { {0, new int[]{ 0, 1, 2, 3, 7, 4, 5, 6, 8, 9, 10, 11 } }, {1, new int[]{ 0, 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 11 } }, {2, new int[]{ 0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10, 11 } }, {3, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8 } }, {4, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 8, 9 } }, {5, new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 11, 8, 9, 10 } }, {6, new int[]{ 11, 1, 2, 7, 4, 5, 6, 0, 8, 9, 10, 3 } }, {7, new int[]{ 3, 1, 2, 0, 4, 5, 6, 11, 8, 9, 10, 7 } }, {8, new int[]{ 7, 1, 2, 11, 4, 5, 6, 3, 8, 9, 10, 0 } }, {9, new int[]{ 0, 5, 9, 3, 4, 2, 6, 7, 8, 1, 10, 11 } }, {10, new int[]{ 0, 2, 1, 3, 4, 9, 6, 7, 8, 5, 10, 11 } }, {11, new int[]{ 0, 9, 5, 3, 4, 1, 6, 7, 8, 2, 10, 11 } }, {12, new int[]{ 0, 1, 6, 10, 4, 5, 3, 7, 8, 9, 2, 11 } }, {13, new int[]{ 0, 1, 3, 2, 4, 5, 10, 7, 8, 9, 6, 11 } }, {14, new int[]{ 0, 1, 10, 6, 4, 5, 2, 7, 8, 9, 3, 11 } }, {15, new int[]{ 4, 8, 2, 3, 1, 5, 6, 7, 0, 9, 10, 11 } }, {16, new int[]{ 1, 0, 2, 3, 8, 5, 6, 7, 4, 9, 10, 11 } }, {17, new int[]{ 8, 4, 2, 3, 0, 5, 6, 7, 1, 9, 10, 11 } } }; public static HashSet<(int, int, int, int)> hash_result_5; public static Dictionary<(int, int, int, int), string[]> all_state_5; public static HashSet<int> ep_exist_hash_6; } }
State.cs
using System.Linq; namespace cube_solver { class State { public int cp; public int co; public int[] ep; public int eo; public State(int cp, int co, int[] ep, int eo) { this.cp = cp; this.co = co; this.ep = ep; this.eo = eo; } public State apply_move(int move_num) { int new_cp = Global.cp_move_table[this.cp, move_num]; int new_co = Global.co_move_table[this.co, move_num]; int new_eo = Global.eo_move_table[this.eo, move_num]; int[] new_ep = Global.ep_move_dict[move_num].Select(x => this.ep[x]).ToArray(); return new State(new_cp, new_co, new_ep, new_eo); } } }
Program.cs
using System; using System.Collections.Generic; using System.IO; using System.Runtime.Serialization.Formatters.Binary; using System.Linq; using System.Diagnostics; namespace cube_solver { class Program { static void Main(string[] args) { int[,] read_move_table(string path) { using (FileStream fs = new FileStream(path, FileMode.Open)) { BinaryFormatter bf = new BinaryFormatter(); return (int[,])bf.Deserialize(fs); } } Global.cp_move_table = read_move_table("cp_move_table.data"); Global.co_move_table = read_move_table("co_move_table.data"); Global.eo_move_table = read_move_table("eo_move_table.data"); using (FileStream fs = new FileStream("hash_result_5.data", FileMode.Open)) { BinaryFormatter bf = new BinaryFormatter(); Global.hash_result_5 = (HashSet<(int, int, int, int)>)bf.Deserialize(fs); } using (FileStream fs = new FileStream("all_state_5.data", FileMode.Open)) { BinaryFormatter bf = new BinaryFormatter(); Global.all_state_5 = (Dictionary<(int, int, int, int), string[]>)bf.Deserialize(fs); } using (FileStream fs = new FileStream("ep_exist_hash_6.data", FileMode.Open)) { BinaryFormatter bf = new BinaryFormatter(); Global.ep_exist_hash_6 = (HashSet<int>)bf.Deserialize(fs); } string[] move_names = { "U", "U2", "U'", "D", "D2", "D'", "L", "L2", "L'", "R", "R2", "R'", "F", "F2", "F'", "B", "B2", "B'" }; bool is_move_available(int pre, int now) { if (pre == -1) return true; if (pre / 3 == now / 3) return false; if (pre / 3 == 0 && now / 3 == 1) return false; //U→Dはダメ if (pre / 3 == 3 && now / 3 == 2) return false; //R→Lはダメ if (pre / 3 == 4 && now / 3 == 5) return false; //F→Bはダメ return true; } int ep_to_index(int[] ep) { int index = 0; for (int i = 0; i < 12; i++) { index *= 12 - i; for (int j = i + 1; j < 12; j++) { if (ep[i] > ep[j]) index += 1; } } return index; } bool is_solved(State q_state) { return Global.hash_result_5.Contains((q_state.cp, q_state.co, ep_to_index(q_state.ep), q_state.eo)); } bool prune(int depth, State q_state) { if (depth == 1 && !(Global.ep_exist_hash_6.Contains(ep_to_index(q_state.ep)))) return true; return false; } List<int> current_solution = new List<int> { -1 }; string[] last_5_solution = new string[] { }; bool depth_limited_search(State q_state, int depth) { if (depth == 0 && is_solved(q_state)) { last_5_solution = Global.all_state_5[(q_state.cp, q_state.co, ep_to_index(q_state.ep), q_state.eo)]; return true; } if (depth == 0) { return false; } if (prune(depth, q_state)) { return false; } int prev_move = current_solution.Last(); for (int move_num = 0; move_num < 18; move_num++) { if (!(is_move_available(prev_move, move_num))) continue; current_solution.Add(move_num); if (depth_limited_search(q_state.apply_move(move_num), depth - 1)) return true; current_solution.RemoveAt(current_solution.Count - 1); } return false; } //string scramble = "R' U' F R' B' F2 L2 D' U' L2 F2 D' L2 D' R B D2 L D2 F2 U2 L R' U' F"; string scramble = "R' U' F R' B' F2 L2 D' U' L2 F2 D' L2"; State scramble2state(string scramble) { State start_state = new State(0, 0, Enumerable.Range(0, 12).ToArray(), 0); int[] moves = scramble.Split(" ").Select(x => Array.IndexOf(move_names, x)).ToArray(); foreach (int each_move in moves) { start_state = start_state.apply_move(each_move); } return start_state; } State scrambled_state = scramble2state(scramble); var sw = new Stopwatch(); sw.Start(); if (Global.all_state_5.ContainsKey((scrambled_state.cp, scrambled_state.co, ep_to_index(scrambled_state.ep), scrambled_state.eo))) { string[] short_solution = Global.all_state_5[(scrambled_state.cp, scrambled_state.co, ep_to_index(scrambled_state.ep), scrambled_state.eo)]; for (int i = 0; i<short_solution.Count()+1; i++) { Console.WriteLine("Start searching lenght {0}", i); } Console.WriteLine(string.Join(" ",short_solution)); } else { for (int i = 0; i < 6; i++) { Console.WriteLine("Start searching lenght {0}", i); } for (int depth = 1; depth < 16; depth++) { Console.WriteLine("Start searching lenght {0}", depth + 5); if (depth_limited_search(scrambled_state, depth)) break; } current_solution.RemoveAt(0); Console.WriteLine(string.Join(" ", current_solution.Select(x => move_names[x])) + " " + string.Join(" ", last_5_solution)); } sw.Stop(); TimeSpan ts = sw.Elapsed; Console.WriteLine("Finished!({0})", ts); Console.ReadKey(); } } }
動作環境
ASRock DeskMini H470 CPU: Core i7 11700 メモリ:16G 2666MHz
参考にさせて頂いたサイト
ルービックキューブを解くプログラムを書いてみよう(前編:キューブを操る実装) - Qiitaルービックキューブを解くプログラムを書いてみよう(中編:IDA*探索) - Qiita
ルービックキューブを解くプログラムを書いてみよう(後編:状態のindex化, Two-Phase-Algorithm) - Qiita
進捗状況
2021年9月2日
16手問題を40分かけて解けるようになりました。Start searching lenght 0 Start searching lenght 1 Start searching lenght 2 Start searching lenght 3 Start searching lenght 4 Start searching lenght 5 Start searching lenght 6 Start searching lenght 7 Start searching lenght 8 Start searching lenght 9 Start searching lenght 10 Start searching lenght 11 Start searching lenght 12 Start searching lenght 13 Start searching lenght 14 Start searching lenght 15 Start searching lenght 16 B' R' D L2 D F2 L2 D U L2 F2 B R F' U R Finished!(00:39:04.9852557)
2021年9月8日
16手問題が40分から30分に縮まりました。Loading pretrained data... Start searching... Start searching lenght 1 Start searching lenght 2 Start searching lenght 3 Start searching lenght 4 Start searching lenght 5 Start searching lenght 6 Start searching lenght 7 Start searching lenght 8 Start searching lenght 9 Start searching lenght 10 Start searching lenght 11 Start searching lenght 12 Start searching lenght 13 Start searching lenght 14 Start searching lenght 15 Start searching lenght 16 B' R' D L2 D F2 L2 D U L2 B F2 R F' U R Finished!(00:29:46.8706479)
2021年9月9日
マルチスレッド化に挑戦したら16手問題が4分に縮まりました。Loading pretrained data... Start searching... Start searching lenght 1 Start searching lenght 2 Start searching lenght 3 Start searching lenght 4 Start searching lenght 5 Start searching lenght 6 Start searching lenght 7 Start searching lenght 8 Start searching lenght 9 Start searching lenght 10 Start searching lenght 11 Start searching lenght 12 Start searching lenght 13 Start searching lenght 14 Start searching lenght 15 Start searching lenght 16 B' R' D L2 D F2 L2 D U L2 B F2 R F' U R Finished!(00:04:08.6661349)