首页 > 编程语言 >Alpha-Beta算法简介

Alpha-Beta算法简介

时间:2022-12-11 21:22:36浏览次数:74  
标签:return int 简介 黑方 Beta score 69 Alpha 红方

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

相关文章