Need help with chess program!
Larry Craighead
plies in a minute on my Pentium 133 MHz. With material and piece
square evaluation only, I can manage a mere 20000 nps. I am getting
horribly desperate. What am I doing wrong? Other programs are
managing node counts less than half as large at modest depths like 4
plies, and have similar or faster speed with a much more complex
evaluation. Would anyone like to look at my source and tell me WHAT I
AM FUCKING DOING WRONG? I can supply either a uuencoded .zip or
tar.gz. My code is for Borland version 4.5.
Matt Craighead
Joe Stella
kerr...@alpha.pr1.k12.co.us (Thomas Kerrigan) writes:
>1. PV
>2. null move
>3. hash table move
>4. winning captures
>5. swaps
>6. killers (2)
>7. history killers
>8. dull moves :)
>9. losing captures
>If you do this, you should get 5-6 ply in a few seconds.
<sigh> I know I should separate losing captures from winning captures,
but I have just been too lazy to write an exchange evaluator to allow
me to do this. I forgot about null moves, though, so I my move ordering
really is
1) Null move
2) Hash table move
3) Captures (largest -> smallest captured piece value)
4) History Heuristic
I wonder, how much speed will it buy me if I separate out the losing
captures?
>If you need more
>speed, consider that the evaluation function is a major factor in tree
>size. If you're only using piece/square tables, you can expect your trees
>to be large (but 6 ply should never take a minute).
I don't think I understand this one. Are you saying that a better evaluator
will cut down the tree size? If so, does this happen because move ordering
is better with a better evaluator? Or are you thinking of some other effect?
Joe S.
Thomas Kerrigan
search around 50k NPS, and its pure C, with a "complete" evaluation
function. It wasn't easy to get this fast, but its very possible.
However, you shouldn't be concerned with your NPS count when your trees
are huge. Here's how I order moves:
1. PV
2. null move
3. hash table move
4. winning captures
5. swaps
6. killers (2)
7. history killers
8. dull moves :)
9. losing captures
If you do this, you should get 5-6 ply in a few seconds. If you need more
speed, consider that the evaluation function is a major factor in tree
size. If you're only using piece/square tables, you can expect your trees
to be large (but 6 ply should never take a minute).
Cheers,
Tom
------------------------------------------------------------------------------
"You can bring any calculator you like to the midterm, as long as it
doesn't dim the lights when you turn it on." -Hepler, Systems Design 182
Thomas C. Kerrigan
'kerr...@alpha.pr1.k12.co.us'
Larry Craighead
(Thomas Kerrigan) writes:
>
>20k NPS on a p5/100 ain't "mere", I agree. However, I think Stobor
would
>search around 50k NPS, and its pure C, with a "complete" evaluation
>function. It wasn't easy to get this fast, but its very possible.
Remember that 20k on 133 MHz is about the same as 15k on 100 MHz, which
was what Joe said he was getting.
>However, you shouldn't be concerned with your NPS count when your
trees
>are huge. Here's how I order moves:
>
>1. PV
Useless with hash table?
>2. null move
Not used.
>3. hash table move
I have this.
>4. winning captures
>5. swaps
I have no easy way to do a SEE, so this is impossible.
>6. killers (2)
>7. history killers
Aren't regular killers pretty useless with history too?
>8. dull moves :)
Defined as...
>9. losing captures
See 4-5.
>
>If you do this, you should get 5-6 ply in a few seconds. If you need
more
>speed, consider that the evaluation function is a major factor in tree
>size. If you're only using piece/square tables, you can expect your
trees
>to be large (but 6 ply should never take a minute).
Odd. As I add more evaluation, my trees get larger.
>Cheers,
>Tom
>
>----------------------------------------------------------------------
-------
>"You can bring any calculator you like to the midterm, as long as it
>doesn't dim the lights when you turn it on." -Hepler, Systems Design
182
>
>Thomas C. Kerrigan
>'kerr...@alpha.pr1.k12.co.us'
Matt Craighead
Joe Stella
plug...@ix.netcom.com (Larry Craighead) writes:
>Remember that 20k on 133 MHz is about the same as 15k on 100 MHz, which
>was what Joe said he was getting.
Sorry if my last bit of advice was too elementary, but I didn't remember
if I had seen your name here before so I didn't know what level you were at.
>>
>>1. PV
>Useless with hash table?
No. On deep searches, the hash table can be "overburdened", unless you have
mega-mega memory (like one fortunate person we know... :-) ). In this
case, it's good to use the PV and even to use a "refutation table", which
essentially stores a "PV" (or best line of play) for each ply 1 move. I have
tried to implement this in my program, but I keep messing it up... :-(
>>2. null move
>Not used.
Then you should expect to get about a ply less depth than programs that
use null move pruning. Maybe your program is not doing so badly as you
think...
How about posting a position along with how long it takes your program to
search it? A tactical problem with a definite solution is best; then you can
see how long it takes to find the answer. I think positions where material
is won are better than "mate in n" positions, because mates can be found
very quickly by using various kinds of check extension heuristics but this
really does not help the playing strength of the program very much. In fact,
they can make the program worse because the branching factor goes too high...
Joe S.
Thomas Kerrigan
move *ordering* is actually better than using SEE (by a TINY fraction).
The real advantage to SEE is pruning in quiescence...
Also, send me this program that evidently sucks so much and I'll take a
look at it. Perhaps I could spot a few problems.
Cheers,
Tom
------------------------------------------------------------------------------
Thomas Kerrigan
Right now Stobor has a "modern" search, and if anything my trees should
be smaller than Hyatt's, because I don't have his passed pawn push
extension or allow checks in quiescence. However, Crafty's trees are
often smaller than mine by a factor of 2-8. Bruce Moreland has complained
about this too.
The way I explain it is with the evaluation function. Notice that a
program may get 5-6 ply a move, but that figure jumps to 7-9 when there's
something totally obvious to do, such as recapture a queen with the only
attacker. I explain this by pointing out that the score for that move is
much better than any other move. Following this reasoning, I think
Hyatt's trees are so small because his evaluation function has enough
terms to return radically different scores for different moves.
Joe Stella
(Thomas Kerrigan) writes:
>>Joe:
>>[...]
>>Also, send me this program that evidently sucks so much and I'll take a
>>look at it. Perhaps I could spot a few problems.
I think you got the wrong guy. The original poster in this thread is
Matt Craighead, not me. But I'm sure he's listening...
Joe S.
Robert Hyatt
Larry Craighead <plug...@ix.netcom.com> wrote:
--->I have done everything I can... but my program still cannot search 6
--->plies in a minute on my Pentium 133 MHz. With material and piece
--->square evaluation only, I can manage a mere 20000 nps. I am getting
--->horribly desperate. What am I doing wrong? Other programs are
--->managing node counts less than half as large at modest depths like 4
--->plies, and have similar or faster speed with a much more complex
--->evaluation. Would anyone like to look at my source and tell me WHAT I
--->AM FUCKING DOING WRONG? I can supply either a uuencoded .zip or
--->tar.gz. My code is for Borland version 4.5.
--->
--->Matt Craighead
You are looking at the wrong thing. 20K nps is more than enough to search
6 plies, so you should look at the size of your tree instead. If you have
a favorite position, I can run it thru crafty (of course, you can download
crafty and do it too if you prefer.) I would always make a sanity check by
printing the tree (to a file of course) for a search, then going through it
by hand. Check for the following potential bugs (may be more than I've given,
but it's a start as I've done most of 'em).
1. non-captures in q-search, often caused by trying the hash table move,
and not making sure it's a capture.
2. duplicate moves in tree, caused by trying to be cute and not generate
things until you need them, then you repeat moves you've already tried.
3. bugs in alpha/beta
4. search extensions that are applied at unexpected (and inappropriate)
times to blows the tree up.. check extension when not in check, recapture
extension for QxP PxQ, since PxQ is not worth extending, it already wins
all kinds of material, etc. Very likely you make booboos here, as it's
easy to do. Been there, done that, probably doin' it tomorrow too.
It takes a lot of effort to do this, but it should pay off. The first version
of Cray Blitz only searched 1K nps on the cray, yet did 6-7 ply searches.
Crafty is searching 10-20K nps on ICC, and is reaching 6-7 plies in under
10 seconds. Good luck. There's two ways to go fast: (a) search faster or
(b) search smaller trees.
Bob
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Thomas Kerrigan
be) confused. Sorry.
Anyway, Mr. Craighead, I just read your latest post. Perhaps I'm just
having a bad day, but your tone sure sounds hostile to me. Please
remember that you're asking for help and we're doing our best to
deliver. Perhaps this is incentive to be a bit more pleasant.
> Remember that 20k on 133 MHz is about the same as 15k on 100 MHz, which
> was what Joe said he was getting.
Excellent. You can divide. Why should I remember this?
> > 1. PV
> Useless with hash table?
Nope. Shrinks my tree 5%. Its also useful for debugging extensions, and
necessary for pondering.
> >2. null move
> Not used.
Does that mean you're not going to use it, or what?
> >3. hash table move
> I have this.
Give yourself a medal.
> >4. winning captures
> >5. swaps
> I have no easy way to do a SEE, so this is impossible.
Bloody hell, I have no easy way to do this either. Neither does anybody
else. If you want your tree to shrink without doing any work, then pray.
Don't post here.
> >6. killers (2)
> >7. history killers
> Aren't regular killers pretty useless with history too?
Nope. They shrink my tree 4%.
> >8. dull moves :)
> Defined as...
Moves that don't fit anywhere else.
Larry Craighead
Kerrigan) writes:
>
>Joe: I tested this a LONG time ago, but I found that using MVV/LVA for
>move *ordering* is actually better than using SEE (by a TINY fraction).
>The real advantage to SEE is pruning in quiescence...
Oddly, I got a _slowdown_ when I put in MVV/LVA to replace simple victim
ordering. I now have it as a compile-time option.
>Also, send me this program that evidently sucks so much and I'll take a
>look at it. Perhaps I could spot a few problems.
What format do you want?
Hope you don't mind having no comments. :) I never use them. You'll notice some
things like en passant captures are still not implemented.
>Cheers,
>Tom
>
>----------------------------------------------------------------------
-------
>"You can bring any calculator you like to the midterm, as long as it
>doesn't dim the lights when you turn it on." -Hepler, Systems Design
182
>
>Thomas C. Kerrigan
>'kerr...@alpha.pr1.k12.co.us'
Matt Craighead
Larry Craighead
(Thomas Kerrigan) writes:
>
>First, I have a miserable newsreader, and this may cause me to act
(and
>be) confused. Sorry.
>
>Anyway, Mr. Craighead, I just read your latest post. Perhaps I'm just
>having a bad day, but your tone sure sounds hostile to me. Please
>remember that you're asking for help and we're doing our best to
>deliver. Perhaps this is incentive to be a bit more pleasant.
If I was in a bad mood, I certainly didn't notice. I think I was just
going a little hastily, not thinking as much as I should have before
posting.
>> > 1. PV
>> Useless with hash table?
>
>Nope. Shrinks my tree 5%. Its also useful for debugging extensions,
and
>necessary for pondering.
I removed it, and got no change in my node count. Odd? However, I
have so much memory that I almost never get a t-table clash.
Necessary for pondering? Can't one look up the positions in question
in the hash table? I guess I should look further into this because I
don't have any pondering implemented.
>> >2. null move
>> Not used.
>
>Does that mean you're not going to use it, or what?
No, I haven't worked on my program enough to implement it yet.
Comparing my node counts with those of other programs without the null
move, I still am doing worse. I would rather look at why I'm doing bad
now before adding in another variable.
>> >6. killers (2)
>> >7. history killers
>> Aren't regular killers pretty useless with history too?
>
>Nope. They shrink my tree 4%.
I'd better test that. The literature I've read seems to say that the
HH eliminates the need for killers.
Steven J. Edwards
>Hope you don't mind having no comments. :) I never use them. You'll notice some
>things like en passant captures are still not implemented.
A few words of advice:
1) At the 1994 ACM event, commentator IM Mike Valvo asked the
participants how long they had been working on their programs. I
believe the average time was greater than seven years. Therefore,
unless one has an eidetic memory, comments are a must for a successful
long term effort. Also, someday one may want to elist collaborators,
or one may want to distribute sources.
2) I would strongly recommend that the basics of a chess playing
program be in place and thouroughly debugged prior to adventures with
any search code. This means full move generation, legality checking,
a decent command interface, a trace output facility, and a means
(batch file processing) of automated testing including regression
testing.
A long time ago in one of the ACM events, a certain program (a Fortran
implementation) blew two of its four games because it couldn't handle
en passant captures. It's hard to accept excuses for such an omission
(or for lack of castling or underpromotion) in the 1990s when even low
cost commercial programs had these necessities nearly twenty years
ago.
-- Steven (s...@mv.mv.com)
Jon Dart
> Right now Stobor has a "modern" search, and if anything my trees should
> be smaller than Hyatt's, because I don't have his passed pawn push
> extension or allow checks in quiescence. However, Crafty's trees are
> often smaller than mine by a factor of 2-8. Bruce Moreland has complained
> about this too.
I recently modified Arasan's node counting code to be the same
as Crafty's (and most other programs).
Then I ran some tests, mostly using the Bratko-Kopec test #22.
I'm doing about 3600 nodes per second on a Pentium 90. Crafty
is about 5600 nodes per second, so it's better, but I'm doing
ok (I use bitboards very little, only for pawn structure evaluation).
The big difference is, Crafty is searching a little over 20000 nodes
at 5 ply with this test (22660 to be exact), which really blew me away.
Arasan was searching .. well, let's just say it was embarrassing.
I discovered that I was making some unnecessarily pessimistic tests
before going into the null move search. So I loosened up the
tests, and now I search about 90000 nodes in this position (5 ply).
More extensive tests (e.g. WAC) show no loss of accuracy with the
null move fix, so I seem to be on the right track there.
I'm still trying to figure out how Bob does 22660 nodes. I'd like to
see results from other programs on this test.
> I think Hyatt's trees are so small because his evaluation function
> has enough terms to return radically different scores for different moves.
Could be. It appears to me that crafty is also quite a bit more
selective in its quiescence search than my program is. I'm still
investigating.
--Jon
--
-----------------------------------
Jon Dart jd...@netcom.com
Larry Craighead
>
>Could be. It appears to me that crafty is also quite a bit more
>selective in its quiescence search than my program is. I'm still
>investigating.
Crafty's node counts were approximately halfed by the SEE pruning in
the q-search, if I remember right.
>--Jon
>
>
>
>--
>-----------------------------------
>Jon Dart jd...@netcom.com
Matt Craighead
Thomas Kerrigan
GNU, CM3k, etc.) but I've *never* seen anything else as fast as Crafty...
I don't think Hyatt realizes the number of headaches he's causing. ;)
Cheers,
Tom
------------------------------------------------------------------------------
Steven J. Edwards
>A long time ago in one of the ACM events, a certain program (a Fortran
>implementation) blew two of its four games because it couldn't handle
>en passant captures. It's hard to accept excuses for such an omission
>(or for lack of castling or underpromotion) in the 1990s when even low
>cost commercial programs had these necessities nearly twenty years
>ago.
Which reminds me of a more recent instance of a program that had a
serious problem in the user interface move parser. The particular
problem occurred when either of two knights could move to the same
square except that one of them was pinned. (I think this was the bug
trigger.) It wasn't just a problem that the parser couldn't handle
standard algebraic notation, but that it refused to accept a bug
triggering opponent's move in any notation. In fact, the program had
to be stopped and its board manually set up in the new position for
the game to proceed. My understanding of the rules for the particular
event was that this was grounds for a loss declaration as was the case
in the aforementioned en passant incidents. But this is a poor way to
win a game and so no complaint was registered; the only penalty was
that the offending program's clock continued to run while the manual
intervention was underway. However, one cannot always count on the
goodwill of one's opponent, so I would warn every implementor to get
the basics right before making excursions into the more exotic regions
of search and destruction.
-- Steven (s...@mv.mv.com)
Robert Hyatt
SheppardCo <shepp...@aol.com> wrote:
--->>> I think Hyatt's trees are so small because his evaluation function
--->>> has enough terms to return radically different scores for different
--->moves.
--->
--->I have seen this theory mentioned a few times, and it doesn't
--->seem possible to me.
--->
--->In general, evaluation functions that make more discriminations
--->will make the search move ordering *worse*. The reason is
--->that the search engine doesn't get as many cutoffs based upon
--->equally good moves; instead, it must search for the uniquely
--->better move.
--->
--->If you wish to confirm this theory it is quite easy to do; just
--->modify your evaluation functions to do material-only evaluation
--->and watch your search depths increase. (Note that the
--->appropriate way to conduct this test is to set your evaluation
--->parameters to 0, so that the evaluation function still takes just
--->as long to compute its answer.)
--->
--->A more likely theory: Crafty's move ordering, futility pruning,
--->and quiescence search control are excellent. If your trees
--->are significantly larger than Crafty's, these are the places
--->to start looking.
I think Tom's fixed his node count somewhat. Was a counting bug, rather
than a searching bug. I agree that more eval terms "spread the spectrum"
of the evaluation range, which should usually increase the tree size, not
the reverse.
The most likely reason for different tree sizes between any two programs
is usually found in either (a) move ordering where one is better than the
other or (b) search extensions which can often add significant numbers
of nodes, which may or may not be good.
Dan Thies
: I agree that more eval terms "spread the spectrum"
: of the evaluation range, which should usually increase the tree size, not
: the reverse.
Two things we are trying to deal with this are:
1. Don't bother checking eval terms that are irrelevant - if you're down
a rook, there's no point checking to see if you have a backward pawn.
2. Use a limited evaluation function which is specific to the position -
in the endgame, you don't need to worry about whether you can still
castle or not.
Dan
--
Dan Thies = Off-The-Wall Solutions = rt...@cyberspace.com
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
(Business AI, Game AI, Neural Nets) - Read comp.ai.games!
"I flunked my Turing Test, but at least I passed the driving exam!"