I am writing AI for a card game and after some tests I have found that MTD (alpha) beta Algorithm - A series of zero-window searches - is only faster using alpha-beta.
The description of the MTD (F) algorithm is done well here
The problem is that for every pass in MTD (F) search (for each estimate) I do not reuse any of the previous positions, which I have stored, although I have written tips on the link that I want (actually cleaning the middle table gives speed to the repeated algorithm).
My problem is that when I store a value in one place and in my transpond table, I also store alpha and beta values for which it is valid. So with another estimate, the second pass through the tree (and therefore alpha and beta) probably can not reuse any information, is it expected or am I missing some basic things here? For example if we come for the result of alpha = 3 beta = 4 for the result of 7 (obviously a sliced), then should I store it in alphabetical table for beta = 6? Or beta = 7?
Your problem comes down to ideologically understanding how to look for an alpha beta. It was a very big problem that I also ran, and after looking around I found that this concept was explained more naturally than any other paper I read on this topic.
Actually you can not treat all alpha-beta because of the same result when a cutoff occurs, as a result, only one bound is represented, and not the right minimum value. It has been proven that using the borders will always give you a better next state, but possibly without accurate scores. When you store the state with a cutoff, you need to treat it as a joint and try to improve it on the next one. It will often evaluate the same node several times, but it will essentially continually improve the actual score.
A more complete implementation of the concepts listed in the previously linked article. Scroll to page 14.
Comments
Post a Comment