Alpha-Beta - Chessprogramming wiki
可运行的代码(最后的注释值得一看):
nclude <stdio.h> #include <vector> struct { int score; char* kids; } nodes[] = { { 0, "BCD" }, // A 可以在这里“排序”,如CBD { 0, "EFG" }, // B { 0, "HIJ" }, // C { 0, "KLM" }, // D { 9 }, { 8 }, { 7 }, { 6 }, { 5 }, { 4 }, { 3 }, { 2 }, { 1 } }; std::vector<int> pstack; // position(局面) stack const char* gen_moves() { return nodes[pstack.back()].kids; } void make_move(char m) { pstack.push_back(m - 'A'); } void undo_move() { pstack.pop_back(); } int eval() { return nodes[pstack.back()].score; } #define I do { for (int i = 0; i < 7 - 3 * d; i++) putchar(' '); } while (0) // Indent int quiesce(int a, int b) { // 直接return score可以,Quiescence Search不是必须的。 // https://www.chessprogramming.org/Quiescence_Search int score = eval(); if (score >= b) return b; if (score > a) a = score; return a; } int alpha_beta(int a, int b, int d) { const char* moves = gen_moves(); if (!moves) return quiesce(a, b); I;printf("[ %d, %d ] %s\n", a, b, moves); for (const char* p = moves; *p; p++) { make_move(*p); int score = -alpha_beta(-b, -a, d - 1); undo_move(); if (score >= b) { I;printf("%d >= %d, ret b(%d)\n", score, b, b); return b; } if (score > a) { int old = a; a = score; I;printf("%d > %d, a = %d\n", score, old, a); } } I;printf("ret a(%d)\n", a); return a; } int main() { pstack.push_back(0); printf("%d\n", alpha_beta(-96, 69, 2)); getchar(); return 0; } /* * 以象棋为例,MAX是红方,MIN是黑方。如评价函数是红方子数减去黑方子数,红想要15(16个子vs光杆老将),黑想要-15 * 方块形的根节点是A,该红方走。下一层圆圈是B,C,D,该黑方走。再一层E..M又该红方走。 * 搜索的目的是为红方找出最佳着法,但红方在思考时必须站在黑方的角度考虑,比如开局红方炮二进七打马,不能指望黑方 配合,起横车不吃马。红方要找黑方尽了最大努力的情况下依然对红方有利的走法。 [ -96, 69 ] BCD # [alpha, beta] alpha先设为-infinity,即比所有的走法都差 [ -69, 96 ] EFG # Negative Max 很容易把人绕晕。69和96,而不是-infinity和infinity可能是鄙人首创。:-) -9 > -69, a = -9 -8 > -9, a = -8 -7 > -8, a = -7 ret a(-7) # 在红方已经走棋的前提下,黑方会使自己的利益最大化,即选最小的分。 7 > -96, a = 7 # 红想“如果我炮二平五”,黑方使劲全力,我也能有7分。 [ -69, -7 ] HIJ # 红想“如果我……”,就算黑方配合,我也最多6分。 -7 >= -7, ret b(-7) [ -69, -7 ] KLM # 红想“如果我……”,就算黑方配合,我也最多5分。 -7 >= -7, ret b(-7) ret a(7) # 所以,炮二平五,最少7分,黑方走错的话,9分。 7 如果斜线部分把I..M彻底涂掉,怎么知道它们的分数分别是5到1?可能是: If one already has found a quite good move and search for alternatives, one refutation is enough to avoid it. A refutation of an argument, accusation, or theory is something that proves it is wrong or untrue. (FORMAL) 也许: 1. 看到6比7小,5,4就不生成了;看到3比7小,2,1就不生成了。 2. 或者浅层处理,用快速的方法估计是5,不再使用准确缓慢的方法(包括但不限于往深搜几步——指数级增长)。 */
标签:return,int,简介,黑方,Beta,score,69,Alpha,红方 From: https://www.cnblogs.com/funwithwords/p/16974514.html