|
|
The Search Algorthm
I use a standard negascout search, with very limited move ordering based on the most recent cut-off at each depth.
That probably means nothing to you 
I'd like to take you through the evolution of a search algorithm, however various people have done this aready as search techniques are pretty standard.
Search Trees
Search trees are a useful way of thinking about how a game progresses. Consider a hypothetical simple game where there are only two possible moves available at each turn. At the root of the tree, i.e. the first turn, we have two possible moves. After each of these moves, there are two more possible moves (so four possible positions the board can be in after two moves). After three moves we have eight possible outcomes, and so on.
We could happily map every single possible state in chess, if we had the time and storage space. But even in our simple game, after 16 moves we have 65536 different states, this shows how large search trees can quickly become. Chess has on average thirty or so possible moves each turn. That's an awfully large search space.
Min-Max
Min-max is one of the basic techniques used in two player game AI. It basically corresponds to the first player trying to minimise the opponents score, and the second player trying to maximise theirs. The score can be just an estimate for a position to allow us to look ahead a certain depth, without needing to evaluate the whole search space.
ai-depot.com has a nice description of min-max and alpha beta pruning.
Alpha-Beta pruning
Windowing and move ordering
Negascout
More info to follow, however try a web search on any of the tems, I'm sure you'll find something interesting.
|
|
Andy's LEGO® Mindstorms® Page
