Not logged inRybka Chess Community Forum
Up Topic The Rybka Lounge / Chess / chess algorithm
- - By kaustubh (**) Date 2007-03-15 12:06
Which chess algorithm is better minimax , negamax , alpha - beta pruining , negascout  or principle variation search ?
Parent - - By Vempele (Silver) Date 2007-03-15 14:23 Edited 2007-03-15 14:25
First, NegaScout and PVS are the same thing.

Minimax is just an unpruned tree with a huge branching fractor. All the other algorithms you mentioned produce the exact same result as minimax in much shorter time, assuming no additional pruning. Except negamax, which seems to be just a simpler way to code minimax.

Alpha-beta dominates minimax by a huge margin.

PVS dominates alpha-beta. Almost all chess programs use it nowadays.

Wikipedia is your friend.
Parent - - By kaustubh (**) Date 2007-03-16 01:59
Vempele thank you for your information you gave . One question i want to ask you what algorithm does rybka use .
Parent - By Anil (*) Date 2007-03-17 09:01
WIN-i-Max algorithm! ;-)
Parent - By grolich (***) Date 2007-03-18 14:20 Edited 2007-03-18 14:40
I'd be very surprised if it's not PV search with a bit (or a lot...) of extra pruning and selection added.

Practically all modern engines use PV search with added cutoff tests / pruning in order to determine the depth of search in each line.
That means that completely fixed depth searches are practically never used (I've seen that part confuse many other students in the past, since all the algorithmic examples given in classes usually refer to a search at depth n, for some n... That never really happens in reality).

No one uses the original, old minmax Algorithm anymore.
It's just much much worse.

Of course, there are more algorithms you have not mentioned, which may be better theoretically.
MTD is one, but it has its problematic issues.
Also there is a First-Best algorithm (I think it is called SSS* or something like that)
which seems to sometimes do better than PV search in practice, but requires a lot more memory (it applies Branch and Bound techniques, and is not a depth first search, hence the memory requirements).

but unless Vas is keeping some deeply held secrets, my guess is that it is a PV search,
and the things that differentiate Rybka from the other engines are:
1) its evaluation function, which is a LOT more complex than other engines (takes a lot more time).
2) its aggressive pruning / selection, which both compensate for the slowness / complexity of the Evaluation function, and are made possible by it...

Just wanted to point out the options you left out.
I think I can pretty much rule out SSS* because I have not witnessed any abnormal memory consumption by Rybka.
Also, there are problems related to reliance on the hash tables with MTD, which are complicated to solve in practice.

So, most probably, the answer to your question is:

a variable depth PV search (which is really a small modification / addition on alpha beta, since it still uses alpha beta values and cutoffs).

Didn't Vas relate to this in the past?
Up Topic The Rybka Lounge / Chess / chess algorithm

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill