GameDev.net Posting Guidelines (please read before posting)
Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 30 July 2008 - 12:37 PM
Posted 30 July 2008 - 03:20 PM
Posted 03 August 2008 - 08:22 AM
Posted 03 August 2008 - 08:47 AM
int NegaMax(Position P, int depth, int alpha, int beta) {
if(depth<=0) {
return QuiescenceSearch(P, alpha, beta); // For some games, simply return the static evaluation here
}
// Look this position up in the hash table
HashEntry hash_entry;
bool hash_hit=query_hash(b.hash_key(), &hash_entry);
if(hash_hit && hash_entry.depth>=depth){
switch(hash_entry.score_type){
case lower_bound:
if(alpha<hash_entry.score)
alpha=hash_entry.score;
break;
case upper_bound:
if(beta>hash_entry.score)
beta=hash_entry.score;
break;
case exact_score:
return hash_entry.score;
}
if(alpha>=beta)
return hash_entry.score;
}
// ... continue search normally
}
Posted 03 August 2008 - 09:17 AM
Quote:
Original post by alvaro
Let me see if I can explain it with pseudo-code:
*** Source Snippet Removed ***
Feel free to ask if anything is still not clear.
Posted 03 August 2008 - 01:36 PM
Posted 06 August 2008 - 06:52 AM
Quote:
Original post by alvaro
I can try to explain alpha-beta in my own words, and see if that helps you.
We are writing a function that, given a subtree of the game and two values alpha and beta, will return a number s which is:
* an exact score if alpha < s and s < beta,
* an upper bound if s < alpha,
* a lower bound if beta < s.
In order to do that, you look at the subtree corresponding to each child of the root, and you recursively call alpha-beta on each child, with carefully chosen values for alpha and beta of the new searches so you extract the information you want.
So my interpretation is:
* alpha: a value such that if the true score is alpha or below, we don't really care what it is exactly.
* beta: a value such that if the true score is beta or above, we don't really care what it is exactly.
The reason why we don't care is that we know in previous moves the players had options such that if the true score is outside (alpha,beta), this branch won't be chosen as the best and its score won't propagate to the root.
Several refinements to alpha-beta use null-window searches (where beta == alpha+1), which are a way of deciding whether the true score is better than alpha.
A word of caution: There are many things that you expect to be true about alpha-beta searching which go out the window once you introduce transposition tables. For instance, you would expect that if you repeat a search you'll get the same result, or that if a search told me that the true score of a subtree is above 50, a new search with a window (alpha=50, beta=infinity) would return something larger than 50. These things may not be true because the transposition table will not be in the same state in between calls. However, having transposition tables is such a huge performance boost that they are worth all the insanity that comes with them. This insanity I talk about is usually called "search instability". Another problem that transposition tables bring with them is "graph history interaction".
Posted 06 August 2008 - 11:03 AM
Quote:
Original post by gfrommer
One more question regarding Transposition Tables.... does it make sense to preload a transposition table with moves before I run my iterative deepening minimaxAB search? My game runs in a web browser so I've made it stateless... and each time a new move is submitted, the processing starts with an empty transposition table. What are the issues with loading/saving transposition cache results? Is it even worth my time to load a couple hundread megs of TT data before I start the search?
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.