• Max-Min和Nega-Max算法:个人而言,我倾向于后者,Knuth的思路真的是非常的独特,思想简单,第一个想到确很不容易,重要的是代码简洁!

MinMax(state, cPlayer) -> f(state)//brute solution
if(terminal(state)||boundary(state))
   then return f(state)
//Max and Min
if(cPlayer==MAX){
   f(state)=int_min;
   foreach child of state
     do
           f=Max{child(state), cPlayer=MIN};
           if(f>f(state)) f(state)=f;
}
if(cPlayer==MIN){
   f(state)=int_max;
   foreach child of state
     do
           f=Min{child(state), cPlayer=MIN};
           if(f<f(state)) f(state)=f;
}
return f(state);

NegaMax(state, cPlayer)->f(state)//brute still but more concret
if(terminal(state)||boundary(state))
   then return f(state)
//NegMax
f(state)=int_min;
foreach child of state
   do
          f=-Max{child(state), cPlayer=MIN};
          if(f>f(state)) f(state)=f;
return f(state);

  • SSS*算法,stockman的算法,1979,基于最优的扩展,个人觉得他的实现更像是松弛算法,有点像上界逼近[一堆论文],这里引用wiki的算法,关键的地方改了下

SSS_start(state, intial-value)->f(state)
//f is the minmax value,based on open table
push(state, live, intial-value);//h is for the last entry
while true
  do
      pop(node);
      if(node.status==live)
         then
            if(node==LEAF) then
               push_back(node, solved, min(eval(state),h));
            endif
           if(node==MIN_NODE) then
              push_back(firstchild(node), live, h);
           endif
           if(node==MAX_NODE) then
             push_back(childgroup(node), live, h);
           endif
      else //solved
           if(node==ROOT_NODE) then
                return h;
           endif
          if(node==MIN_NODE) then
               purge(parent(node))
               push_back(parent(node), solved, h);
          endif
          if(node==MAX_NODE) then
                  if(node has brother) then
                      push_back(brother(node), live, h);
                  else
                  push_back(parent(node), solved, h);
          endif 
  end

  • AB-SSS* with Transposition Table[Must recite, it’s very smart and helpful],非常重要的框架,必须熟练掌握!

Alpha-Beta(state, alpha, beta)->g;
//TT with Alpha-Beta cut-off
  if retrieve(state)==found then
        if state.f+<=alpha or state.f+==state.f-
           then return state.f+;
        if state.f->=beta
           then return state.f-;
//reach the boundary of tree
 if state==LEAF then
        state.f+=state.f-=g;
else
        g=int_min;
        c=firstchild(state);
        while g<beta and c!=NULL do
               g=max{g, -Alpha-Beta(state, -beta, -alpha)};
               alpha=max{alpha, g};
               c=nextbrother(c);
        //for update alpha-beta, opposite
        if g<beta then state.f+=g;//valid +
        if g>alpha then state.f-=g;//valid –
 endif
//for current state
store(state);
return g;

//for AB-SSS* max status
SSS_star(state)->f
    g=int_max;//get the next boundary less than g
    do
         r=g; g=Alpha-Beta(state, r-1, r);
    while r!=g
    return g;

//for AB-SSS* min status
DUAL_star(state)->f
    g=int_min;//get the next boundary bigger than g
   do
        r=g; g=Alpha-Beta(state, r, r+1);
   while r!=g;
   return g;

  • 最后一个很简单但很重要的Zobirst Hash Key!

实现:将chess的square,move,等等[我叫局面因子,自己改的],每个生成一个随机rand()值,生成一个64位的随机树,前20位作为hash的entry点,后面44位作为hash键!如果要移动的话,就将动作也作为一个随机值生成新键。[目前看来暂时用不到L Game的局面太小了,不过可以试验一下],下面节选自wiki,其实不难

At program initialization, we generate an array of pseudorandom numbers [2]:

  • One number for each piece at each square
  • One number to indicate the side to move is black
  • Four numbers to indicate the castling rights, though usually 16 (2^4) are used for speed
  • Eight numbers to indicate the file of a valid En passant square, if any

This leaves us with an array with 781 (12*64 + 1 + 4 + 8) random numbers. Since pawns don’t happen on first and eighth rank, one might be fine with 12*64 though.

E.g the starting position: [Hash for White Rook on a1] xor [White Knight on b1] xor [White Bishop on c1] xor … ( all pieces ) … xor [White castling short] xor [White castling long] xor … ( all castling rights )

Advertisements