Talk:Principal variation search

I've implemented some typical AI game-search algorithms for my 4th grade AI course and have a hard time trying to understand the behaviour of this one. The code is pretty obscure... Any help? --User:Euyyn

Does the new pseudocode help? User:David Souther

Does this infringe upon copyright or is it the other way around?

Check out this webpage NegaScout - Minimax Algorithm faster than AlphaBeta

I'm going to assume that someone just copied from this webpage and mark it as a copyvio, and rewrite the page. --meatmanek 01:30, 13 March 2006 (UTC)

I would guess that both bits of code are lifted directly from the cited book. I'd check the book for its copyright terms before assuming that this is a violation. C. Scott Ananian 16:21, 12 April 2006 (UTC)

I was under the impression that the book was OKay with letting people use his implementation; still, I re-wrote the pseudocode. User:David Souther

---

I will not be so presumptuous as to edit the page, but it looks to me like the C and Python code snippets are doing different things. Can the original author make a comment here ?

Pseudocode

I edited the code to be a lot more Human Readable. I'm 99% sure it's still right, but if not... fix it ;) User:David Souther

I think David forgot the (d < maxdepth-1) expression of the orininal code, and this expression is the difference between PVS and NegaScout.--80.171.191.208 15:34, 7 August 2006 (UTC)

Re: Does this infringe upon copyright or is it the other way around?

The issue I have with the page is not the pseudocode. (I didn't even notice that at first) The first thing I saw was the poorly paraphrased text.

Striking similarities.

Wikipedia	Reinefeld
Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree.	Like AlphaBeta, NegaScout is a directional search algorithm for computing the minimax value of a node.
It dominates alpha beta pruning in the sense that it will never examine a node that can be pruned by alpha beta.	NegaScout dominates AlphaBeta: It never examines a node that can be pruned by AlphaBeta.
There are trees in which NegaScout searches fewer nodes than SSS* and vice-versa.	There exist trees in which NegaScout searches strictly fewer nodes than SSS* and vice versa.

In addition to this, the article should be rewritten because of poor clarity - it doesn't really even explain what's going on or what the difference is between negascout and minimax.

PS: In the current pseudocode, what is b?

meatmanek 22:16, 11 May 2006 (UTC)

Pseudocode error?

I'm no expert, but this seems very strange, and didn't seem to work in my chess program:

if ( alpha > temp > beta) ...

Isn't alpha typically lower than beta? How could this condition ever pass?

I believe it should be: if ( alpha < temp < beta) ... (This appears to be how it was before Souther modified the pseudocode)

however an opinion of an expert would be nice.

2. Error?

I tried it out, and it seems not to work, because it is to fast in returning results. A algorithm that is slightly different, but does work can be found here: http://www.brucemo.com/compchess/programming/pvs.htm

3. Error?

I also think that there is an error in the pseudocode. To me the two calls to the negascout function are identical, because b==beta. Shouldn't the first call read:

α := -negascout(child, depth-1, -α, -α) ??

I also found this link here: http://www.frayn.net/beowulf/theory.html —Preceding unsigned comment added by 80.129.76.136 (talk) 01:35, 10 February 2008 (UTC)

Yes, the current code is definitely wrong. I believe the null window search should be almost what you have but alpha and beta shouldn't be exactly the same. I'm going to go ahead and change it to the following:

α := -negascout(child, depth-1, -(α+1), -α)

Janzert (talk) 03:40, 20 February 2008 (UTC)

Hmm, ok after looking at it again, b is set to α+1 after the first child. So the real correction is to set b = α+1 initially as well. But α is getting set the the result of the recursive call for each child which I haven't quite convinced myself is correct. Certainly a formulation using a temporary variable would seem to be much clearer.

Janzert (talk) 03:47, 20 February 2008 (UTC)

One more comment, the pseudocode most definetely doesn't do the same thing as the example page since the example doesn't even start null window searches until a search returns greater than alpha.

Janzert (talk) 03:56, 20 February 2008 (UTC)

It was broken after the "correctly set initial window" edit. It is NOT supposed to be a null window search on the first pass. AllUltima (talk) 08:52, 25 February 2008 (UTC)

Include color?

This is a variation of the negamax algorithm, and I was wondering if we should include "color" like the negamax algorithm does. At the very least, we should say that the "heuristic" should return the opposite for min that it does for max.

Pplantin (talk) 16:37, 17 January 2012 (UTC)

There fixed it! 2001:6B0:1:1E20:C096:9CED:28EA:1BE (talk) 12:50, 6 September 2012 (UTC)

Maybe someone should explain what color is. This explanation could be copied from the negamax page. 2001:6B0:1:1E20:C096:9CED:28EA:1BE (talk) 12:52, 6 September 2012 (UTC)