钉单人纸牌–在深度优先搜索中检查钉与检查孔 [英] Peg solitaire – checking pegs vs. checking holes in a depth-first search
问题描述
我正在尝试使用深度优先的搜索算法来解决纸牌接龙-因为现代计算机可以轻松地在合理的时间内检查
所有游戏位置。即使过了23小时，
算法也找不到任何解决方案。我进行了一次网络搜索，发现了文件
深度优先搜索可解决钉纸牌 。我尝试从文件
中尝试c程序，并且在程序启动后立即找到了第一个解决方案。我比较了
算法。算法之间的主要区别在于它们查找
可能的钉跳的方式。当我的算法从左上
到右下角在板上搜索孔（检查每个孔是否有
跳跃的可能）时，纸张算法搜索从左上角到底部
右击钉子（检查每个钉子是否存在跳动）。这两种算法都是
按照找到的顺序尝试跳转。要强调区别：
I am trying to solve Peg Solitaire with a depth-first search algorithm – it should be possible to solve the game since "modern computers can easily examine all game positions in a reasonable time". Even after 23 hours, the algorithm didn't find any solution. I did a web search and found the paper "Depth-first search solves peg solitaire". I tried the c-program from the paper and the first solution was found immediately after the program started. I compared the algorithms. The main difference between the algorithms is the way they find possible peg-jumps. While my algorithm searches the board for holes from top left to bottom right (each hole is checked if there are possible jumps), the paper-algorithm searches the board for pegs from top left to bottom right (each peg is checked if there are possible jumps). Both algorithms are trying the jumps in the order they are found. To underline the difference:
- 分析漏洞：运行时23小时没有解决方案
- 分析挂钩：运行时10秒，共2940个解决方案
问题：为什么会出现这样的巨人（无法解决/无法立即解决）如何在跳板上搜索差异？为什么最好检查钉子而不是检查可能的跳动的孔？
Question: Why is there such a giant (not solvable / immediately solved) difference on how to search the board for jumps? Why is it better to check the pegs instead of checking the holes for possible jumps?
您可以在以下C ++程序中尝试该算法。为了使它紧凑，我已经删除了次要的重要部分（印刷电路板，生成初始位板等）。
You can try the algorithm with following C++ program. To keep it compact I have removed the lesser important parts (printing the board, generating the initial bitboard, ...).
#include <iostream>
#include <ctime>
#include <vector>
#include <utility>
#include <ctime>
typedef unsigned __int64 ui64;
typedef std::vector<std::pair<int, int> > vecjumps; // first=from, second=to
ui64 moves = 0; // Number of moves made so far
int solutions = 0; // Number of solutions found so far
clock_t start; // To measure time
// Bitboard
// Board Bits
// ------------------------------
// *** 02 03 04
// *** 10 11 12
// ******* 16 17 18 19 20 21 22
// ***o*** 24 25 26 27 28 29 30
// ******* 32 33 34 35 36 37 38
// *** 42 43 44
// *** 50 51 52
const ui64 bitboard = 0x001c1c7f7f7f1c1c; // 1ULL << 2 | 1ULL << 3 | ...
ui64 board = bitboard & ~(1ULL << 27); // Initial Board: Bit 27 <=> Hole
// To try the hole-version: Swap Commented and Uncommented parts
vecjumps getMoves(ui64 b)
{
// Find the possible jumps through bit-shift operations. mr <=> right jump
// possibilities. The inverted Board represents the Holes. Shifting the
// board by 16 right/left --> moving all pegs up/down. Shifting the board
// by 1 --> moving all pegs left/right
//ui64 mr = (((b >> 1) & b) << 2) & ~b & bitboard;
//ui64 md = (((b >> 8) & b) << 16) & ~b & bitboard;
//ui64 ml = (((b >> 1) & b) >> 1) & ~b & bitboard;
//ui64 mu = (((b >> 8) & b) >> 8) & ~b & bitboard;
ui64 mr = ((((b >> 1) & b) << 2) & ~b & bitboard) >> 2;
ui64 md = ((((b >> 8) & b) << 16) & ~b & bitboard) >> 16;
ui64 ml = ((((b >> 1) & b) >> 1) & ~b & bitboard) << 2;
ui64 mu = ((((b >> 8) & b) >> 8) & ~b & bitboard) << 16;
vecjumps jumps;
jumps.reserve(12);
for (int i = 2; i < 53; i++)
{
//if (mr & (1ULL << i)) jumps.push_back(std::make_pair(i - 2, i));
//if (md & (1ULL << i)) jumps.push_back(std::make_pair(i - 16, i));
//if (ml & (1ULL << i)) jumps.push_back(std::make_pair(i + 2, i));
//if (mu & (1ULL << i)) jumps.push_back(std::make_pair(i + 16, i));
if (mr & (1ULL << i)) jumps.push_back(std::make_pair(i, i + 2));
if (md & (1ULL << i)) jumps.push_back(std::make_pair(i, i + 16));
if (ml & (1ULL << i)) jumps.push_back(std::make_pair(i, i - 2));
if (mu & (1ULL << i)) jumps.push_back(std::make_pair(i, i - 16));
}
return jumps;
}
void makeMove(ui64& b, int from, int to)
{
// Through a xor-instruction, a jump from 11 to 27 includes 19
// 19 = (11 + 27) / 2
b ^= 1ULL << from | 1ULL << (from + to) / 2 | 1ULL << to;
moves++;
if (moves % 10000000 == 0)
printf("(%8d, %14llu moves, %lf)\n",
solutions, moves, (double)(clock() - start) / CLOCKS_PER_SEC);
}
// Depth First Search Algorithm
bool findSolution(int depth)
{
if (!depth) return ((1ULL << 27) & board);
vecjumps jumps = getMoves(board);
for (vecjumps::const_iterator cit = jumps.begin(); cit != jumps.end();
++cit)
{
ui64 copy = board;
makeMove(board, (*cit).first, (*cit).second);
if (findSolution(depth - 1)) solutions++;
board = copy;
}
return false;
}
int main()
{
start = clock();
findSolution(31);
printf("(%8d, %14llu moves, %lf)\n",
solutions, moves, (double)(clock() - start) / CLOCKS_PER_SEC);
return 0;
}
推荐答案
如果没有循环无论采用哪种方法生成的树，并且生成的树都是相同的，采用相同的搜索算法时，产生hudge差异的原因必须是节点的扩展顺序（启发式）。我仍在检查您的实现，但似乎一切正常，因此看不到速度差异的任何其他原因。
If there are no loops in the resulting tree in either method, and the resulting tree is the same, the reason for the hudge difference when aplying the same search algorithm must be the order in which the nodes are expanded (heuristic). I'm still checking your implementation but everything seems right on it, so I can't see any other reason for the speed difference.
前一段时间，我有一个建议关于这个问题的信息，我在我的书签上找到了：您可以在此处阅读更多信息，深度搜索与广度搜索以及一些启发式方法以改进搜索： http://www.durangobill.com/Peg33.html
Some time ago I had an assigment on this problem, and I found this on my bookmarks: You can read more info, depth search vs breadth search and a couple of heuristics to improve the search here: http://www.durangobill.com/Peg33.html
这篇关于钉单人纸牌–在深度优先搜索中检查钉与检查孔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
