Re: computer-go: extracting date to beat 9d from chess and draughts scene

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 10:44 AM 11/15/99 +0100, you wrote:
>Stuart Cracraft <cracraft@xxxxxxxxxxxxxxxxx> wrote:
>> At 03:18 PM 11/14/99 +0100, heikki wrote:
>>>Could someone enlighten me as to what this wonderfull nullmove



>> In regards to Go, it is simply "Pass".
>
>Thanks. Could you (or someone else) also explain how increasing the
>moves-to-be-tried from 361 to 362 will produce a huge reduction in the
>search tree?
>
>I can imagine this in some simple cases, like life and death in a corner. If
>you assume the opponent passes on every move, and still can not be killed,
>it is unconditionally alive, and we need not to search all the tricky
>variations. (Also: if that group can not be enclosed with 5 moves in a row,
>then it is not worth trying, or likewise for running out.) 
>
>Is this it? To me it seems that this can be useful in some local searches,
>mostly in those a human player would consider obvious, and for which some
>simple heuristics can be devised (if it has two eyes, it lives anyway,
>sectro line logic, etc.)
>
>I still do not see any serious reduction in whole-board searches.

Alpha beta reduction to start with. The basic implementation
of alfabeta without any enhancement, extension scheme or whatever
using RECURSIVE search

Alfabeta(side,alfa,beta,depthleft)
  
  if( depthleft <= 0 )
    return(quiescencesearch(-beta,-alfa,side);

  best = -infinite;
  for all legal moves
     best = max(best,-Alfabeta(otherside,-beta,-alfa,depthleft-1);
     if( best > alfa ) 
       if( best >= beta )
         return(best);
       fi
       alfa = best;
     fi
  end of for
end of alfabeta()

The reduction is caused by the comparision with beta,
which prunes all trees.

>
>-- 
>Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
>               "In Murphy we Turst"
>
>
Vincent Diepeveen
diep@xxxxxxxxxxxxxxxxx

---
... en verder ben ik van ben ik van mening dat Dap het gesticht in moet