Peg solitaire - 在深度优先搜索中检查钉子与检查孔

Question

我试图用深度优先搜索算法解决Peg Solitaire - 应该可以解决游戏,因为"现代计算机可以在合理的时间内轻松检查所有游戏位置".即使在23小时后,该算法也找不到任何解决方案.我做了一个网络搜索,发现了文章 "深度优先搜索解决了peg solitaire".我从论文中尝试了c程序,并在程序启动后立即找到了第一个解决方案.我比较了算法.算法之间的主要区别在于它们找到可能的跳跃跳跃的方式.虽然我的算法在电路板上搜索从左上角到右下角的孔(如果有可能的跳跃,则检查每个孔),纸算法在电路板上搜索从左上角到右下角的栓钉(如果有可能,检查每个栓钉)跳转).两种算法都按照找到的顺序尝试跳转.强调差异:

• 分析漏洞:运行时间23小时无解决方案
• 分析钉:运行时10秒,2940解决方案

问题:为什么在如何搜索电路板跳跃方面存在如此巨大的(不可解决的/立即解决的)差异？为什么检查钉子而不是检查孔是否可能跳跃更好？

您可以使用以下C++程序尝试该算法.为了保持紧凑,我删除了较不重要的部分(打印电路板,生成初始位板,......).

#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;
}

Answer 1

如果两种方法的结果树中都不存在循环，并且结果树是相同的，则应用相同搜索算法时出现差异的原因一定是节点展开的顺序（启发式）。我仍在检查您的实现，但一切似乎都正确，所以我看不出速度差异的任何其他原因。

不久前，我对这个问题进行了作业，我在书签上发现了这个：您可以在此处阅读更多信息、深度搜索与广度搜索以及一些改进搜索的启发式方法：http ://www.durangobil.com /Peg33.html