discrepancy in alpha-beta

[Bob]

Archived from groups: comp.ai.games (More info?)

I noticed some pseudocode from wikipedia
(http://en.wikipedia.org/wiki/Alpha-beta_pruning) that does these
checks in alpha beta:

min:
if beta <= alpha return alpha

max:
if beta <= alpha return beta

Then there's code at
http://www.cs.dartmouth.edu/~rus/courses/AI/AI-03/Lectures/l6.html that
says this:

min:
If beta >= alpha return alpha

max:
If alpha >= beta return beta


As you can see, the checks for min differ. Anyone know who's right?

 

[Guest]

Archived from groups: comp.ai.games (More info?)

When alpha < beta, things are "normal". When alpha >= beta, the current
path can be pruned.

When you are maximizing, you are trying out a bunch of potential moves
for max, which means you are looking at a bunch of new alpha values.
Then you test a new alpha value against the current beta value. So if
you find a violation of alpha < beta, you return the alpha immediately.

When you are minimizing, you are trying out a bunch of of new beta
values associated with min's move. Here you test the current alpha
value against each new beta value. If you find one that violates alpha
< beta, you return it immediately.

So it looks like Wikipedia is correct here, and the test for min
in the Dartmouth notes is in error (possibly a typo).

Mike

 

[Bob]

Archived from groups: comp.ai.games (More info?)

It looks like Wikipedia is correct. BTW, your explanation has some
mistakes. In max, you return beta if alpha < beta is violated.

Michael C. Horsch wrote:
> When alpha < beta, things are "normal". When alpha >= beta, the current
> path can be pruned.
>
> When you are maximizing, you are trying out a bunch of potential moves
> for max, which means you are looking at a bunch of new alpha values.
> Then you test a new alpha value against the current beta value. So if
> you find a violation of alpha < beta, you return the alpha immediately.
>
> When you are minimizing, you are trying out a bunch of of new beta
> values associated with min's move. Here you test the current alpha
> value against each new beta value. If you find one that violates alpha
> < beta, you return it immediately.
>
> So it looks like Wikipedia is correct here, and the test for min
> in the Dartmouth notes is in error (possibly a typo).
>
> Mike