Alpha-Beta搜索很简单

基本搜索方法——简介(二)

代码：

/*
 d=3 a=96 b=-69 BCDE
  d=2 a=69 b=-96 FGHI
   d=1 a=96 b=-69 MLKJ
    eval=7
   -7(v) >= -69(b) ret
  7(v) >= -96(b) ret
 -7(v) >= -69(b) ret
7
*/
// https://www.xqbase.com/computer/search_intro2.htm
// https://www.xqbase.com/computer/search_intro3.htm
#include <stdio.h>
#include <vector>

struct { char* haizi; int v; } nodes[] = {
    { "BCDE" }, // A
    { "FGHI" }, // B
    { "" }, { "" },    { "" }, // CDE
    { "LMKJ" },    // F 改这里可以“排序”
    { "NO" }, // G
    { "" }, { "" }, // HI
    { "", 11 }, // J
    { "", 12 }, // K
    { "", 9 }, // L
    { "", 7 }, // M
    { "", 15 }, // N
    { "", 6 }, // O
};

std::vector<int> pstack;    // position(局面) stack

char* gen_moves() { return nodes[pstack.back()].haizi; }
void apply_move(char m) { pstack.push_back(m - 'A'); }
void undo_move() { pstack.pop_back(); }
int eval() { return nodes[pstack.back()].v; }
#define I do { for (int i = 0; i < 4 - d; i++) putchar(' '); } while (0) // Indent

int alpha_beta(int d, int a, int b) {
    if (d <= 0) { int v = eval(); I;printf("eval=%d\n", v); return v; }
    char*    moves = gen_moves();
    I;printf("d=%d a=%d b=%d %s\n", d, a, b, moves);
    for (char* p = moves; *p; p++) {
        apply_move(*p);
        int v = -alpha_beta(d - 1, -b, -a);
        undo_move();
        if (v >= b) { I;printf("%d(v) >= %d(b) ret\n", v, b); return v; }
        if (v > a) { I;printf("%d(v) > %d(a)", v, a); a = v; }
    }
    I;printf("ret %d\n", a); return a;
}

int main() {
    pstack.push_back(0);
    printf("%d\n", -alpha_beta(3, 96, -69));
    getchar(); return 0;
}

这就对了？改下节点F的子节点的顺序试试？

基本搜索方法——简介(三) 解释为什么排序这一步是很重要的。

其实本文的原标题是“Alpha-Beta搜索很简单…………吗？”，耸人听闻骗下点击。:-)

Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

https://www.geeksforgeeks.org/c-program-for-insertion-sort/