1
$\begingroup$

In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state p with $\alpha$ and $\beta$ cutoff and gets a v value, i.e.,

v = alphabeta(p, $\alpha$, $\beta$)

are these properties true?

  1. alphabeta(p, -$\infty$, $\beta$) = v when $\alpha$ < v
  2. alphabeta(p, $\alpha$, $\infty$) = v when v < $\beta$
  3. alphabeta(p, $\alpha$', $\beta$') = v when $\alpha$ $\le$ $\alpha$' $\le$ $\beta$' $\le$ $\beta$
  4. if v > $\beta$, then alphabeta(p, $\beta$, $\infty$) = alphabeta(p, $\alpha$, $\infty$)
  5. if v < $\alpha$, then alphabeta(p, -$\infty$, $\alpha$) = alphabeta(p, -$\infty$, $\beta$)

I've reached to this results studying the algorithm itself after reading a couple of papers. After applying it to a real case I've got an improvement of ~30% (in number of states visited, and this gives about a 30% of time execution improvement also), but I want to know if there is a mathematical background that supports these changes to the algorithm.

$\endgroup$
4
  • $\begingroup$ My apologies, I had only glanced at your question, so my comment was not really fitting. And one shouldn't answer in comments anyway. But I am not sure what exactly you are asking. Do you doubt whether the procedure (with initial values of -/+ infinity) is correct? Do you wonder what correctness means? How to prove it? $\endgroup$
    – Carsten S
    Feb 8 at 15:48
  • $\begingroup$ No @CarstenS, probably I haven't explained it well. From the initial definition of the algorithm I have found some 'tricks' that make it work quite faster by pruning more branches. It works in the setups I have tested, but I want to be sure that it will work in all cases, so I'm looking for the mathematical proof of that. Properties 1 to 5 are the mathematical basis of my 'tricks'. If these properties are true (proved), then the modifications to the algorithm can stay, if not, they must be removed or reformulated. $\endgroup$
    – Ivan
    Feb 8 at 16:13
  • $\begingroup$ BTW I have fount that prop. 4 and 5 are weakly supported due some papers use them. Probably 3 also. But no idea about 1 and 2. $\endgroup$
    – Ivan
    Feb 8 at 16:14
  • $\begingroup$ Yes, I know AI site, but after asking myself which SE is more appropriate for this question I decided to come here. Also discarded math.SE. Maybe I'm wrong and AI is better, but I don't know how to move the question between sites (or maybe it's right to just repeat the question?). And about the multiple questions issue, I also thought about it but I decided to ask all together due I'm asking about the properties of an algorithm, very correlated ones to anothers, and it could be a bit weird to ask 5 almost equal questions. $\endgroup$
    – Ivan
    Feb 10 at 11:23
0
$\begingroup$

For a complete reference you can check An Analysis of Alpha-Beta Priming If I am not misunderstanding eq 15 and 16 apply to your case.

$\endgroup$
2
  • 4
    $\begingroup$ I'm not seeing how this answers the question. What is the answer to the questions asked in the post above? Which of those properties are true, and where specifically in that paper should we look to verify that? Can you give a page number and/or section number? Please reserve the 'Your Answer' box only for answers that directly answer the question that was asked (not for "you might also be interested in..." information, for instance). $\endgroup$
    – D.W.
    Feb 9 at 5:23
  • $\begingroup$ (That speck in the hyperlinked pixel raster isn't $'$, but $^1$.) $\endgroup$
    – greybeard
    Feb 9 at 6:46
0
$\begingroup$

My understanding is that these inequalities are just required to make alpha/beta pruning correct, that is to guarantee that you get the minimax result.

You say you get an improvement of 30%. You might add if that is 30% fewer numbers checked, or 30% faster execution time (you might be checking say 65% fewer numbers, but might take twice as long on average per number checked).

But alpha/beta works best if you have a reasonably good heuristic to find and check “good” values i first, and for each value i find bad values ij first. The reason: If you examine an i first where the minimum of $a_{ij}$ is large, then it will be easier to reject i’ which is not as good as i, and if you were able to guess a j first that makes $a_{ij}$ small then i’ is again easier to reject.

In chess alpha-beta pruning will be substantially better than just 30%.

PS. I thought about it, and your savings should be a lot more than 30%, even if your values are random. Say you have 100x100 values which are a just random. If you examined i and now examine i’ and i’ has a higher maximum, then you examine on average 50% of the values to find the maximum at which point the search for i’ is pruned (or likely even earlier). If the maximum is lower, you examine 100 values. For the k-th value I that you examine the chance that it has the lowest maximum so far is 1/k so it’s much more likely that you examine around 50 numbers, not 100.

But after a while the smallest maximum will get smaller, and you’ll find a bigger element in a row much faster than after 50 attempts. Someone with more patience can probably give you a good approximation but I’m sure you need to examine much fewer than 70% of all numbers.

$\endgroup$
2
  • 1
    $\begingroup$ I understood the question as : "Using these inequalities, I get an algorithm with a runtime which is 30% faster than standard alpha/beta pruning. Is it safe for me to use these inequalities? In other words: do they always hold?" But I might be wrong in my interpretation. $\endgroup$
    – Tassle
    Feb 13 at 0:37
  • $\begingroup$ Thanks for your answer. This 30% improvement is in nodes visited, and therefore this is also a 30% in execution time. This is comparing the original algorithm with or without the changes due to assuming that the listed properties are true. Initially my algorithm is a minimax with alphabeta pruning with transposition tables and iterative deepening. When I execute the algorithm without these "hacks" (I can only call it hacks until I have a mathematical proof) in a particular move I visit 14000 states (nodes), but with the hacks I only need to visit around 10000 states with the same result. $\endgroup$
    – Ivan
    Feb 13 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.