Author: Uri Blass
Date: 12:59:59 03/29/04
Go up one level in this thread
On March 29, 2004 at 15:50:10, Dann Corbit wrote: >On March 29, 2004 at 10:17:18, martin fierz wrote: > >>aloha! >> >>i was discussing this somewhere in a thread, but thought i'd like to make this >>question more visible in the hope of getting a good answer: >> >>everybody knows that with plain alpha-beta, a fixed number of moves N per node, >>and perfect move ordering a search to depth D needs >> >>nodes(depth) = sqrt(N)^(D/2) nodes. >> >>with absolutely imperfect move ordering it needs >> >>nodes(depth) = N^(D) nodes. >> >>a typical chess program gets something like 90% move ordering in the sense that >>if a cutoff move exists, it will search it as first move in 90% of all cases. >>here's my question: >> >>can anybody give an estimate for nodes(depth) as function of this move ordering >>parameter? obviously, this would also depend on when you find the best move in >>those cases where you don't find it first. any kind of model is acceptable, e.g. >>you always find it on 2nd, always on sqrt(N)th, always last, at a random number, >>whatever. i'm just interested in the general behavior of nodes(depth) as a >>function of the cutoff-%age. >> >>i'd be extremely surprised if nobody ever estimated this, so: has any of you >>ever seen or calculated such numbers, and if yes, what do they look like? >> >>and is there any theory how this would apply to a modern chess program with >>nullmove and extensions instead of the plain A/B framework above? >> >>basically this question of course means: do you really gain anything tangible >>when improving your MO from say 90% to 92%? > >I have not done the math, but I am guessing no matter what king of move ordering >you have (purely randome or the pv move every time) you will get something like >this: > >nodes = some_constant * sqrt(mini_max_nodes) > >If you have random move ordering, then the constant will be very large. >If you have perfect move ordering, then the constant will be very small. > >You will never get worst case unless you try very hard to achieve it. >It might be possible to degenerate to mini-max (or very close to it) but you >will have to choose the worst possible move at every single turn except the >leaves. I doubt if anyone can do it. >;-) doing it is not enough because the worst move can cause fail high. Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.