Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised

Author: martin fierz

Date: 08:19:52 03/29/04

Go up one level in this thread


On March 29, 2004 at 11:14:17, Anthony Cozzie wrote:

>On March 29, 2004 at 11:05:17, martin fierz wrote:
>
>>On March 29, 2004 at 10:27:19, Anthony Cozzie wrote:
>>
>>>On March 29, 2004 at 10:01:55, martin fierz wrote:
>>>
>>>>On March 29, 2004 at 09:46:48, Uri Blass wrote:
>>>>
>>>>>On March 29, 2004 at 08:54:09, martin fierz wrote:
>>>>>
>>>>>>On March 29, 2004 at 07:04:13, Uri Blass wrote:
>>>>>>
>>>>>>>On March 29, 2004 at 06:25:28, martin fierz wrote:
>>>>>>>
>>>>>>>>On March 28, 2004 at 18:55:53, Artem Pyatakov wrote:
>>>>>>>>
>>>>>>>>hi artem,
>>>>>>>>
>>>>>>>>[snip]
>>>>>>>>
>>>>>>>>>>>On the other hand, I think a lot of researchers have been overly ambitious and
>>>>>>>>>>>have tried to replace Alpha-Beta & tricks with a neural network or some totally
>>>>>>>>>>>different approach. I think that with the current state of AI tools, these
>>>>>>>>>>>efforts are bound to fail.
>>>>>>>>>>
>>>>>>>>>>A lot of researchers?  Other than myself, I don't know of any other workers who
>>>>>>>>>>are attempting a complete and competitive chess playing program that doesn't
>>>>>>>>>>tread the oft traveled A/B bag-of-tricks road.
>>>>>>>>>
>>>>>>>>>That's good a point (will probably include in paper) - not many are working on a
>>>>>>>>>complete chess program, since most just address a particular section, like the
>>>>>>>>>evaluation function. But one old effort - MORPH - comes to mind, and I think I
>>>>>>>>>noticed a couple of other failed Neural Net efforts (don't have references
>>>>>>>>>handy, but I can look).
>>>>>>>>
>>>>>>>>steven is doing a completely radical departure from A/B. but many others are
>>>>>>>>applying more gradual changes to the A/B-model, with reasonable success
>>>>>>>>(smarthink, kaissa, gothmog come to mind, and probably most commercial engines
>>>>>>>>too). at least these engines make considerably larger attempts to shape their
>>>>>>>>game tree than a "classic" A/B searcher like crafty does.
>>>>>>>>
>>>>>>>>[snip]
>>>>>>>>
>>>>>>>>>As I mentioned before, I decided to concentrate my research on move ordering for
>>>>>>>>>a couple of reasons:
>>>>>>>>>1) Move ordering promises big payoffs if done right.
>>>>>>>>
>>>>>>>>how much deeper can you search if you reach 95% move ordering success (defined
>>>>>>>>as cutoff @ 1st / all cutoffs) instead of ~90% that most get today? how much if
>>>>>>>>you reach 100%?
>>>>>>>
>>>>>>>I cannot answer the 95% question but I can answer the 100%.
>>>>>>>
>>>>>>>If you reach 100% then always choosing the first move is enough because if the
>>>>>>>first move does not generate a cutoff no move is going to generate a cutoff so
>>>>>>>you can finish to search to the end of the game very quickly because you search
>>>>>>>only one move in every ply.
>>>>>>>
>>>>>>>Uri
>>>>>>
>>>>>>you do not answer the question here - and what you answer is wrong too :-)
>>>>>>always choosing the best move first to search means you search sqrt(N) moves per
>>>>>>ply on average, not 1 move per ply.
>>>>>
>>>>>No
>>>>>
>>>>>In that case you do not need to search the other moves because you know that
>>>>>they are worse.
>>>>>
>>>>>If you always start from the best move than the pruning strategy of not
>>>>>searching moves except the first move is simply correct and I see no reason not
>>>>>to use it.
>>>>>
>>>>>Uri
>>>>
>>>>come on uri, this is ridiculous. of course you can use that shortcut IF you know
>>>>that your move ordering is 100% perfect. in that case you need no search at all
>>>>either. obviously this is an academic question and has nothing to do with
>>>>reality, and is not what i'm asking... the question remains: in the extremely
>>>>unlikely case that you have 100% perfect move ordering (by accident), what do
>>>>you gain compared to 90% perfect (in the usual sense of move ordering %age)?
>>>>
>>>>cheers
>>>>  martin
>>>
>>>It would be possible to determine this experimentally - just keep track of each
>>>position and the best move at each ply on the hard disk.  It wouldn't be
>>>practical for use but it would be pretty interesting.
>>>
>>>anthony
>>
>>if i had to do this i would produce a mock A/B program which first randomly
>>decides whether the node is a fail-high node (~50% of all cases i guess), and
>>then again randomly decides whether it fails high on the first move (~90% of all
>>cases), and finally decides to fail high somewhere in between move 2...N if not
>>on the first move (perhaps with equal probability, or with decreasing
>>probability from move 2...N). by playing around with the probabilites of these
>>random decisions, you can easily determine the numbers i'm looking for, and see
>>how they depend on the quality of your move ordering.
>>
>>i disagree though that this is not practical: for example, if you find that
>>going from 90% to 91% move ordering (= fail high at first/total fail highs) you
>>need to search 50% less nodes on a typical search depth your engine reaches,
>>then you definitely know you should work on your move ordering. if you find that
>>you need to search 0.1% less nodes, you know that working on MO is a waste of
>>time from now on. the true value will probably lie somewhere in between, but in
>>any case, it gives you an idea of what you might gain with more expensive MO
>>schemes.
>>
>>i can imagine some kind of formula just by doing some assumptions, which may be
>>completely wrong...:
>>
>>the totally wrong-ordered case goes as
>>nodes(depth) ~ (N*N)^D/2
>>
>>the totally ordered case goes as
>>nodes(depth) ~(1*N)^D/2
>>
>>this formula stems from the fact that you search exactly 1 move at player A's
>>moves, and all N at player B's moves AFAIK, so for going 2 ply deeper i need 1*N
>>nodes. so let me assume random move ordering for player A, meaning i get the
>>best move right on average at move N/2, which gives me
>>
>>nodes(depth) ~ (N*N/2)^D/2.
>>
>>perhaps that should read (N*sqrt(N))^D/2, because it might be the geometric
>>instead of the arithmetic mean?!
>>
>>in any case, you can now assume that you find the best move 1st in the fraction
>>F (~0.9), and in the remaining case at random, this leads to
>>
>>nodes(depth) ~ (N*(1*F+(N/2*(1-F)))^D/2.
>>
>>plugging in some numbers like N=20 (reduce from 40, trying to account for
>>nullmove?!), D=10, F=0.90 and 0.91 i get
>>
>>nodes(10, F=0.90) = 79 million
>>nodes(10, F=0.91) = 62 million
>>
>>so for 1% better move ordering i get 22% less nodes?! seems rather excessive.
>>let me try again using sqrt(N) instead of N/2 - that still gets a 12% reduction.
>>
>>hmm, either my formulas are crap or i really have to work on my move
>>ordering ;-)
>>
>>cheers
>>  martin
>
>
>OK, we did not communicate here.

aha, i see - this time i understood!
let's see, even better than "muse-@-XY" would be "zappa-@XY", because i
generally believe that such experiments should be made with the best possible
engine ;-)

anyway, thanks for the suggestion, it sounds very sensible. a bit of work, but
definitely doable.

cheers
 martin

>
>What I am proposing is this:
>
>Create some code that stores for each transposition table key the best move at
>each ply.  Requires maybe 1/2 GB of memory for a reasonable depth search (my
>back-of-the-envelope unoptimized computation).
>
>E.G.:
>
>Key 0x8432762183
>Q-Nxd5
>1-Nf3
>2-Nf3
>3-Qc3
>...
>
>Run search, record node counts.  Keep track of every time the move ordering was
>wrong (both at PV and CUT nodes).
>
>Flush transposition table. Run search iteratively until move ordering is
>perfect. You can use the new table to simply always choose the best move first.
>This might require a few runs since the tree might search different nodes as the
>move ordering gets better.
>
>At that point you will have a search of muse with perfect move ordering.  Record
>the number of nodes visited versus a regular search. Of course, this is not
>practical for a tounament game (for obvious reasons).
>
>Some interesting sub-experiments: move ordering differences by ply - 3% at 5 ply
>vs 100 % at 8 ply (?)  Also, move ordering at PV nodes vs fail-high nodes.
>
>anthony



This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.