Chess Programming Questions
Randall Jouett
Recently, I've playing Chess on ICC, and seeing all the computers playing
on that particular environment has tweaked my interest again in chess
programming.( My ICC name is NOP, which is for No OPeration in assembly
language :^) ).
I wrote a chess program many years ago in Motorola 68K assembly,
which ran on a 7 Mhz Amiga. The name of the program was called
"Nuker." Basically, this program worked, except I never got around
to adding en passant, because I was too busy with school.
Anywho, I was wondering what the current state of affairs is in the
chess-programming world? Any new algorithms? Has tree pruning been
improved? Has David Levy updated his "Computer Chess Compendium"
book to reflect these changes? What is the defacto source for
programming info these days? I've found a couple of links to a few
computer-chess-programming sites, but I have yet to find one that
explains these things in a verbose manner, such as what Levy did
in his compendium. Might have something to do with the current search
engine I'm using? (Shrug.) :^)
Hmmm. Can't seem to find a FAQ for chess programming. Anyone have
a link?
So, with all that out of the way, I was just kinda curious and
wondering what's new in the computer chess world. Any help and
links are appreciated.
BTW, I played a couple of test games between Nuker and Battle Chess,
and even though Nuker didn't know anything about en passant, it still
CRUSHED the other program! :^). Also, even though I had to restart the
game if Battle Chess threw an en passant into the works, Nuker still
had a distinct advantage :^). Some might say that this wasn't all that
great of an accomplishment, especially since Battle Chess is probably
rated around 900 or so :^), but trust me when I tell ya that there is
nothing like seeing a chess program of your own design beat the crap
out of a commercially-available product :^) :^).
Best Regards,
Randall "NOP" Jouett
Dann Corbit
The Winboard forum:
http://f11.parsimony.net/forum16635/
CCC signup:
http://www.talkchess.com/signup.html
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
The Drunken Lord
that's where you'll find programmers.
Russell
"Dann Corbit" <dco...@connx.com> wrote
> CCC signup:
> http://www.talkchess.com/signup.html
The other poster recommended going to www.icdchess.com and it just has a
link to this same place, the Computer Chess Club (CCC) which is at
www.talkchess.com . People discuss chess programming issues there daily, and
some of the authors of the best programs in the world post there regularly.
It would probably help also to tell an approximate date that you'd like to
be updated on, like "What's new since 1980?" or whatever year you got out of
the scene.
Russell
Randall Jouett
Ok. Will do, and thanks for the links!
Randall
Randall Jouett
Kewl! Sounds like my kinda place :^).
As far as programming and dates go, I'd have to say that my
knowledge is good up to Mini/Max, alpha-beta routines, bitboards,
and hash tables. Anything after that, and I guess I'm still just
an unknowing newbie/wannabe/fish :^).
Specifically, I'm interested in the current state of move ordering,
the recent developments in quiescent positions (for positional-style
play), and improvements in depth-first and breadth-first search
algorithms.
BTW, how many of the top programs are using bit-boards? Back in the
mid to late 80's, I was thinking about using the the Amiga's built-in
bit blitter for move generation. This particular blitter could combine
3 sources and either logically OR, AND, and NOR all of them together
(including shifts on the sources or destination) for one output.
I tried and tried to get that particular chip to take the current
position/bitboard as the source and "blit" new moves, but I could never
work out the algorithm correctly. I wonder if anyone out there has tried
this and was successful? It should be doable. I only wish I would have
had more time to work it out! :^/. Hmmm. Maybe some to the new bad-ass
graphics cards could be used this way for move generation? (Shrug.)
OTOH, the latest, greatest processors could probably do it just as fast?!
(Shrug.)
Thanks for listening to the ponderings of a born-again chess programmer! :^)
Randy
--
Randall "NOP" Jouett
Amateur Radio: AB5NI
I eat spaghetti code out of a bit bucket while sitting at a hash table!
Randall Jouett
The Drunken Lord wrote:
>
> go to www.icdchess.com and join the computer forum.
>
> that's where you'll find programmers.
Will do, and thanks for the info!
DGiunti
>but trust me when I tell ya that there is
>nothing like seeing a chess program of your own design beat the crap
>out of a commercially-available product :^) :^).
I know what you mean about that feeling from doing the same thing with
GnuChess for PCs back about that time. My FidoNet users were telling me that
it beat at least the american commercial programs. And when I released the
source to this conference, I soon found out that my optimizations had helped
beat the world champ for the first time at a fast game too. That was my goal
for the project. I just wanted to get on the team that did it.
I stopped programming just after that, and have not done much to improve my
old port. It still runs nicely under windows and is more visious than ever,
ripping 200K nodes a second on a 1gHz '86. My perfect hashing method did not
withstand the test of time, however.
This conference still gets a lot of traffic. Some of the other less public
forums may get less hecklers, but you will never know until you ask.
David Giunti email: DGi...@aol.community
What is the question? Gertrude Stein's last words
No one mouth is big enough to utter the whole thing. Alan Watts
On Display in the UK http://www.web-gallery.co.uk
SEAKAPTAIN
BTW, I'm replying to you from a friends account on AOL, unfortunately :^).
We're fixing a busted exhaust-manifold gasket, and I had a bit of free
time. Please respond to my regular account, though.
> I know what you mean about that feeling from doing the same thing with
>GnuChess for PCs back about that time. My FidoNet users were telling me
>that it beat at least the american commercial programs. And when I released
the
>source to this conference, I soon found out that my optimizations had helped
>beat the world champ for the first time at a fast game too. That was my
>goal for the project. I just wanted to get on the team that did it.
Kewl! It's always nice to hear/read about someone enhancing the state
of the art a bit, even if it was many years ago.
> I stopped programming just after that, and have not done much to improve
>my old port. It still runs nicely under windows and is more visious than
ever,
>ripping 200K nodes a second on a 1gHz '86. My perfect hashing method did not
>withstand the test of time, however.
Specifically, what was the idea behind the perfect hash? 200K
nodes a second is pretty decent, especially if you compate the
number of nodes we were looking at in the 80's :^).
Currently, I'm a bit of brainstorming and looking into the following,
athough I haven't quite determined yet if these things are worth
doing at the expense of the number of nodes that could be searched.
I guess some of them could be turned off or on in a given situation,
though...
* Reversing the value of a Knight and Bishop if the board
seems closed/locked. I'd be interested in hearing from someone
whose tried this.
* Subtracting the bishop's value a bit in the opening if most of
the pawns are of the same color as the bishop. This would allow
the program to determine that this particular bishop is a bad
bishop, and that it should be worth exchanging for a knight.
* Win/Loss Analysis. That is, the program will play a
game, and if it wins, it keeps the current values for
the pieces, such as 3.5 for a bishop, 3 for a knight,
5 for a rook, and 9 for a queen. If it loses, then values
are adjusted within a certain limit. This could help the
program to play a bit better for the given algorithm.
(Shrug.)
* Using the other processors for move generation, such
the the DSP on a sound card, or maybe even try to
use a GPU on a video card. I don't know if you could
consider this to be an SMP-type setup, but it might
be worth looking into, especially since these cards
aren't being used too much (if at all) while the program
is generating moves. This would have to be a dedicated
setup, of course :^).
(Note: I don't know too much about GPU's these days,
and I'm not really sure if something like this could be
incorporated into a chess program. Is this doable?)
* Mobility Analysis. Slightly raise/lower the value of pieces
if their mobility is good/bad, saving these scores (along
with the opening played) to disk after the move is made.
After analyzing this stuff a bit, I sometimes wonder if it
might be better to just write a neural net for analysis,
letting the program learn how to play the best it can play
with the selected algorithm. Also, the program could be
setup to use a different algorithm (or combinations of
a subset of algorithms) under different time controls, allowing
it to select code that could be better for Blitz-type game,
etc.
One thing I've noticed is that it's easy to tell that some of the
programs/robots on are first looking at the minor-piece moves/nodes
before pawn pushes,castling, or queen moves. IMHO, this could be
good or bad in a blitz-type game, but there's really no way of knowing
this unless we were to do a complete analysis of the game, keeping
statistical tract of wins a losses.
BTW, this is also where you could select (what I like to
call) sub-type algorithms, such as "Bishops are better
than knights" when playing against a particular opponent.
It would seem that a neuarl net could eventually figure out
the playing style of a particular opponent. (Shrug.)
> This conference still gets a lot of traffic. Some of the other less
> public forums may get less hecklers, but you will never know until you ask.
True. OTOH, I've been on the Usenet and Internet for over twenty
years now, and I've learned to just ignore these fools. Unfortunately,
they haven't yet realized that heckling others is nothing more than
childish banter, and their doing this in a vain attempt to make themselves
look better at anothers expense. Foolishness, and a complete and total
waste of their time and mine. Once I realized this, I came to the conclusion
that this type of person is a total frickin' idiot, and they're best ignored
:^).
Anywho, I guess I'll just join all the mailing lists when I get home.
I'd love to only be on the Usenet or one particular mailing list, but
I think there's a chance I might miss something important :^).
It's a slight chance, especially since most of the top-level chess
programmers tend to be closed mouthed about their algorithms,
but it's a chance none the less :^).
Thanks for your response, David, and good luck to ya', buddy!
NOP
--
Randall Jouett
DGiunti
>
>Specifically, what was the idea behind the perfect hash? 200K
>nodes a second is pretty decent, especially if you compate the
>number of nodes we were looking at in the 80's :^).
The method was to check each value used in the hashtable constants (in a 32
bit system) and reject values which had too many bits set. The XOR logic fails
(has more collisions) when values are '1' heavy. It worked quite nicely for
programs, but faster CPUs exposed the fact that it was not always perfect:
There are more possible moves that the hashtable can possibly contain so it
would fail, and needs a secondary check to assure uniqueness. Dr. Hyatt even
incorporated it in Crafty for a while I am told.
A similar table manipulation for the currently used 64 bit values would
likely be effective with fewer possible collisions. Some escape on error would
still be needed. I wonder if just comparing the position's bitmap would be
enough of a check... it would be quick fast and cheap.
I don't have much to add to your brainstorming ideas. You could hack on
something to see the effects. I could attach my last release version of Dave's
GnuChess30f to you. It and the corrected opening book come in at less than
200K with the source. You would have to make some constants variables and play
around with their setting algorithmically. To be honest I never really got to
understand eval() well. I reasoned that part of the program was in better
hands than mine because I am not that great a chess player. But I could use my
own craft to more efficiently use that knowledge.
Marcel van Kervinck
> Back in the
> mid to late 80's, I was thinking about using the the Amiga's built-in
> bit blitter for move generation. This particular blitter could combine
> 3 sources and either logically OR, AND, and NOR all of them together
> (including shifts on the sources or destination) for one output.
> I tried and tried to get that particular chip to take the current
> position/bitboard as the source and "blit" new moves, but I could never
> work out the algorithm correctly. I wonder if anyone out there has tried
> this and was successful? It should be doable. I only wish I would have
> had more time to work it out! :^/.
My program copies attack tables for each move
in the tree. Then it updates them according
to the move. I found out that that was simpler and
faster than then reverse-updating during undo-move().
The memcopy would involve ~2*160 bytes (it is not
just attacks in there). When I did this the main
development platform was still the amiga. Naturally
I tried to make it even faster by letting the blitter
make the copy for me. It turned out not to work for
a couple of reasons:
- it was not a lot of data anyway
- setting up the blit also costs time
- it would not work on other hardware, and worse:
- blitting was constraint to slow chip memory
So I gave up on the idea of blitting chess.
Marcel
-- _ _
_| |_|_|
|_ |_ mar...@bitpit.net
|_| Marcel van Kervinck
Randall Jouett
DGiunti wrote:
>
> NOP writes:
>
>>
>>Specifically, what was the idea behind the perfect hash? 200K
>>nodes a second is pretty decent, especially if you compare it to
>>the number of nodes we were looking at in the 80's :^).
>
> The method was to check each value used in the hashtable constants (in a 32
> bit system) and reject values which had too many bits set. The XOR logic fails
> (has more collisions) when values are '1' heavy. It worked quite nicely for
> programs, but faster CPUs exposed the fact that it was not always perfect:
> There are more possible moves that the hashtable can possibly contain so it
> would fail, and needs a secondary check to assure uniqueness. Dr. Hyatt even
> incorporated it in Crafty for a while I am told.
Sounds like a good method to me. BTW, are most ot the top-rated programs using
bitboards? I started hacking the code for NOP -- the name of my program :^) --
today in ANSI C, setting up various constants and what not, and I finally reached
the point where I asked myself, "Self, should you use bitboards or the old tried
and trusted method of indexed arrays?" Mainly, I'm thinking about using the
index method for the sake of simplicity, getting the program up and running in a
decent amount of time. OTOH, if bitboards are "the way to go" these days, then
I guess I should consider using them.
> A similar table manipulation for the currently used 64 bit values would
> likely be effective with fewer possible collisions. Some escape on error would
> still be needed. I wonder if just comparing the position's bitmap would be
> enough of a check... it would be quick fast and cheap.
Off the top of my head, I think anything analytical and cheap (CPU wise)
should be an added heuristic in a program. Actually, I've been thinking
about adding every heuristic and it's grandmother to my program, with
various heuristics being selected at different levels of the game. You
would think that the program would eventually figure out that a certain
combination of heuristics are good when playing blitz or in the middle
game, and others flat out suck :^). Actually, I think it would be rather
amusing to watch the program train itself, coming to the conclusion that
"this particular combination of heuristics in the end game are utter
garbage!" :^)
> I don't have much to add to your brainstorming ideas. You could hack on
> something to see the effects.
Yep. I guess every chess programmer has to go through this at some point,
finding out what works and what doesn't. :^)
> I could attach my last release version of Dave's GnuChess30f to you.
> It and the corrected opening book come in at less than 200K with the
> source.
This sounds great, Dave. Send it my way, and I'd be glad to take a look
at the code. BTW, have you profiled the code, and have you added any
assembly language to the program? Mainly, I was just wondering if the
better programs out there still use assembly or not. I plan on doing
this, although I can't stand writing code in 80X86 assembly language.
To me, the instruction set is bass ackwards, being raised on Motorola
chips :^). OTOH, I do realize that this particular application probably
requires assembly at some points, so I guess I'm going to have to bite
the bullet, bare down, and hack the code. OTOH, this doesn't mean that
I have to enjoy doing this :^).
> You would have to make some constants variables and play around with
> their setting algorithmically.
Exactly the idea I've been thinking about! OTOH, I wonder how
long it will take me to learn the code? I guess with a bit of
help from you, it shouldn't be all that big of a deal. (Shrug.)
> To be honest I never really got to understand eval() well.
Quite understandable! I'm sure this is the "heart" of the program
and where most of its playing strength is located. From your remark,
though, it sounds like the code might need to be slowly picked apart
and I/we could add some additional comments, possibly making the code
a bit easier to read. Sometimes when I'm porting a piece of code
to Linux, I'll actually re-write some of the sections of the program
once I figure out what the original programmer was trying to do :^).
Not the most elegant solution, but I've found out it is sometimes
faster than trying to totally figure out a large program :^).
> I reasoned that part of the program was in better hands than mine
> because I am not that great a chess player.
Welcome to the club! :^)
> But I could use my own craft to more efficiently use that knowledge.
Good thinking, Dave! If I remember correctly, the hardware designer
and lead programmer for DeepThought/DeepBlue is rated around 1200-1400
(USCF) or so, yet he was capable of writing a program that was the world
champion. IMHO, what's really needed in this particular ball game (Read:
programming a computer to play a good game of chess) is good mental-association
skills, pragmatism, and the ability to stick with a project and try out
different things, even when the might seem a bit abstract at times.
OTOH, a good understanding of things such as:
* A knight of the rim is grim. (Edge of the board).
* Rooks belong on open files.
* Doubled rooks are even better.
* A rook on your opponents 7th rank is a good start.
* Double rooks on the 7th rank are even better.
* Good tactical shots can be found when your
opponents pieces are pinned.
* Castle early and often; twice on Sunday :^).
* A knight on the sixth rank supported by a pawn is worth a rock,
especially if it's cutting into your position in the middle
game!
* Pass pawns should be held under lock and key. (Protected.)
They also must be pushed.
* doubled pawns can sometimes suck. Actually, this one can be a bit
fuzzy at times :^).
* Isolated pawns are targets.
* Knights are better than bishops when the board is locked up in the center.
* and Attack on the wings when the center is locked.
* Good tactics come from a good position.
Anywho, most of these things are easily learned by a computer --
and never, ever forgotten! :^). Also, even if a person can learn
these things, that doesn't mean that he or she has the necessary
visualization aptitude to become a strong player. (Read: 2200 or
above.) Frankly, this is why we see 14-year old GM's. It's their
exceptional visualization skills that allow them to succeed at this
particular game, yet if you were to ask them how they did this at
such a young age, they probably tell you it's because they were
blessed by being intelligent :^). Utter hogwash! It's the visualization
aptitude that does it, yet we attribute a high degree of intellect
to someone who can play this game well! Biggest bunch of crap I've
ever heard or read! I think that if a lot of the strong players went
over to the Human Engineering Laboratory (AKA The Johnson Oconner Research
Foundation) and read up on aptitudes, or even took their aptitude
exams, they'd have some rude awakenings :^).
IMHO, I think that to be a decent chess programmer, a person has to have
a good, creative, and abstract mind. Not only does this person have to
be a good abstract thinker and see "the big picture," but he/she also has
to be able to think logically, in a linear fashion, seeing the "next logical
step" in advancement, or they have to at least have the audacity and
curiosity to try something new and have a "stick with it" attitude.
So, maybe a lot of us will never reach the master or GM level. So what?!
Who cares?! We can at least try to increase the state of the art in AI,
and maybe one of us might come up with a earth-shattering heuristic that
might make something like Data from Trek a reality in our lifetimes.
Oh...and don't forget that programming computers to play chess has a
MUCH better chance of making you millionaire, if something like that
is your long term goal :^).
So, most of us aren't strong players. Who cares! What is important,
IMHO, is that we can improve our game to the point where we're not
all that bad. Also, if a person decides to take a shot at programming
a computer to play chess, they might find some new heuristic that really
gets things fired up in tree pruning or something, and an advancement
like that just might ignite a whole new way of programming and really
shake things up. One thing I do know, though: this will never happen
unless some of us decide to say, "Screw this! I'm at least going to
give it a try!" :^)
Best Regards, and good hearing from you again, Dave!
NOP
--
Randall Jouett
Amateur Radio: AB5NI
I eat spaghetti code out of a bit bucket while sitting at a hash table!
P.S.
In about a week or so, NOP -- the chess program -- should be ready
to blunder its first queen :^).
Randall Jouett
DGiunti wrote:
>
> NOP writes:
>
>>
>>Specifically, what was the idea behind the perfect hash? 200K
>>nodes a second is pretty decent, especially if you compare it to
>>the number of nodes we were looking at in the 80's :^).
>
> The method was to check each value used in the hashtable constants (in a 32
> bit system) and reject values which had too many bits set. The XOR logic fails
> (has more collisions) when values are '1' heavy. It worked quite nicely for
> programs, but faster CPUs exposed the fact that it was not always perfect:
> There are more possible moves that the hashtable can possibly contain so it
> would fail, and needs a secondary check to assure uniqueness. Dr. Hyatt even
> incorporated it in Crafty for a while I am told.
Sounds like a good method to me. BTW, are most ot the top-rated programs using
bitboards? I started hacking the code for NOP -- the name of my program :^) --
today in ANSI C, setting up various constants and what not, and I finally reached
the point where I asked myself, "Self, should you use bitboards or the old tried
and trusted method of indexed arrays?" Mainly, I'm thinking about using the
index method for the sake of simplicity, getting the program up and running in a
decent amount of time. OTOH, if bitboards are "the way to go" these days, then
I guess I should consider using them.
> A similar table manipulation for the currently used 64 bit values would
> likely be effective with fewer possible collisions. Some escape on error would
> still be needed. I wonder if just comparing the position's bitmap would be
> enough of a check... it would be quick fast and cheap.
Off the top of my head, I think anything analytical and cheap (CPU wise)
should be an added heuristic in a program. Actually, I've been thinking
about adding every heuristic and it's grandmother to my program, with
various heuristics being selected at different levels of the game. You
would think that the program would eventually figure out that a certain
combination of heuristics are good when playing blitz or in the middle
game, and others flat out suck :^). Actually, I think it would be rather
amusing to watch the program train itself, coming to the conclusion that
"this particular combination of heuristics in the end game are utter
garbage!" :^)
> I don't have much to add to your brainstorming ideas. You could hack on
> something to see the effects.
Yep. I guess every chess programmer has to go through this at some point,
finding out what works and what doesn't. :^)
> I could attach my last release version of Dave's GnuChess30f to you.
> It and the corrected opening book come in at less than 200K with the
> source.
This sounds great, Dave. Send it my way, and I'd be glad to take a look
at the code. BTW, have you profiled the code, and have you added any
assembly language to the program? Mainly, I was just wondering if the
better programs out there still use assembly or not. I plan on doing
this, although I can't stand writing code in 80X86 assembly language.
To me, the instruction set is bass ackwards, being raised on Motorola
chips :^). OTOH, I do realize that this particular application probably
requires assembly at some points, so I guess I'm going to have to bite
the bullet, bare down, and hack the code. OTOH, this doesn't mean that
I have to enjoy doing this :^).
> You would have to make some constants variables and play around with
> their setting algorithmically.
Exactly the idea I've been thinking about! OTOH, I wonder how
long it will take me to learn the code? I guess with a bit of
help from you, it shouldn't be all that big of a deal. (Shrug.)
> To be honest I never really got to understand eval() well.
Quite understandable! I'm sure this is the "heart" of the program
and where most of its playing strength is located. From your remark,
though, it sounds like the code might need to be slowly picked apart
and I/we could add some additional comments, possibly making the code
a bit easier to read. Sometimes when I'm porting a piece of code
to Linux, I'll actually re-write some of the sections of the program
once I figure out what the original programmer was trying to do :^).
Not the most elegant solution, but I've found out it is sometimes
faster than trying to totally figure out a large program :^).
> I reasoned that part of the program was in better hands than mine
> because I am not that great a chess player.
Welcome to the club! :^)
> But I could use my own craft to more efficiently use that knowledge.
Good thinking, Dave! If I remember correctly, the hardware designer
NOP
--
Randall Jouett
Amateur Radio: AB5NI
I eat spaghetti code out of a bit bucket while sitting at a hash table!
DGiunti
>DGiunti wrote:
>>
>> NOP writes:
>>
>>>
>>>Specifically, what was the idea behind the perfect hash? 200K
>>>nodes a second is pretty decent, especially if you compare it to
>>>the number of nodes we were looking at in the 80's :^).
>>
>> The method was to check each value used in the hashtable constants (in a
>> 32
>> bit system) and reject values which had too many bits set. The XOR logic
>> fails
>> (has more collisions) when values are '1' heavy. It worked quite nicely
>> for
>> programs, but faster CPUs exposed the fact that it was not always perfect:
>> There are more possible moves that the hashtable can possibly contain so it
>> would fail, and needs a secondary check to assure uniqueness. Dr. Hyatt
>> even
>> incorporated it in Crafty for a while I am told.
>
>
>Sounds like a good method to me. BTW, are most ot the top-rated programs
>using
>bitboards? I started hacking the code for NOP -- the name of my program :^)
I am not sure about which of the leading commercial programs use BitBoards.
A google search on that topic in this newsgroup would likely tell the tale. I
think that some of them do and some of them don't. I know that Crafty and
Gnuchess503 use them if you are looking for models to implement your ideas, as
they are both freely available. I think that the bitboard approach is
interesting. But I have not studied it usefully.
Which compiler and platform do you plan developing in? There are slight
modifications needed in the code to accommodate the differences.
>today in ANSI C, setting up various constants and what not, and I finally
>reached
>the point where I asked myself, "Self, should you use bitboards or the old
>tried
>and trusted method of indexed arrays?" Mainly, I'm thinking about using the
>index method for the sake of simplicity, getting the program up and running
>in a
>decent amount of time. OTOH, if bitboards are "the way to go" these days,
>then
>I guess I should consider using them.
It's certainly an area where progress is possible! You could do it either
way and possibly just interchange these references and see what the actual
differences are.
>> A similar table manipulation for the currently used 64 bit values would
>> likely be effective with fewer possible collisions. Some escape on error
>> would
>> still be needed. I wonder if just comparing the position's bitmap would be
>> enough of a check... it would be quick fast and cheap.
>
>
>Off the top of my head, I think anything analytical and cheap (CPU wise)
The idea is to do as little work as possible and still be as useful as
possible. I think that the equation here would be the relationship of the
number of possible moves and the number of possible bitboards, and what the
likelihood of dual crashes would be. If you are already using bitboards the
cost of inclusion as the 64bit data is Null. The number of compares for the
check is likely smaller than would be required in the non bitboard environment.
In Gnu30f another hashtable was used and the effect was to double the
computation of another hastable index which were only extra guard digits.
>should be an added heuristic in a program. Actually, I've been thinking
>about adding every heuristic and it's grandmother to my program, with
>various heuristics being selected at different levels of the game. You
>would think that the program would eventually figure out that a certain
>combination of heuristics are good when playing blitz or in the middle
>game, and others flat out suck :^). Actually, I think it would be rather
>amusing to watch the program train itself, coming to the conclusion that
>"this particular combination of heuristics in the end game are utter
>garbage!" :^)
One way that I tried to simulate this sort of behavior was to examine
position where a lot of sacrifices produced victory. Clearly a move that
leaves the Queen in pris is such a bad move. But when the horizon is broad
enough, it's goodbye Lady and hello Victory. Some bad moves turn out to be
good. If variable sets of behaviors for the droid can be useful, it may be
possible to have them self tune the behavior. Dr. Hyatt was looking into this
sort of huristic approach with his opening book analysis. I am not sure where
that went, but you could find out with a download.
>> I don't have much to add to your brainstorming ideas. You could hack on
>> something to see the effects.
>
>Yep. I guess every chess programmer has to go through this at some point,
>finding out what works and what doesn't. :^)
>
>
>> I could attach my last release version of Dave's GnuChess30f to you.
>> It and the corrected opening book come in at less than 200K with the
>> source.
>
>This sounds great, Dave. Send it my way, and I'd be glad to take a look
>at the code. BTW, have you profiled the code, and have you added any
>assembly language to the program?
My approach was more along the lines of MarcoAssembly. I used assembly like
calls to implement the screen update functions; they were much faster. And
that is the part that needs to be redone for a compile on windows, or another
platform.
> Mainly, I was just wondering if the
>better programs out there still use assembly or not.
If you are writing in C or C++ you can conditionally do both with the same
program. If you encapsulate your assembly you just conditionally compile the
program.
> I plan on doing
>this, although I can't stand writing code in 80X86 assembly language.
>To me, the instruction set is bass ackwards, being raised on Motorola
>chips :^). OTOH, I do realize that this particular application probably
>requires assembly at some points, so I guess I'm going to have to bite
>the bullet, bare down, and hack the code. OTOH, this doesn't mean that
>I have to enjoy doing this :^).
Well, it's what you have to play with now that really matters. There is
quite an array of processing power in pentium class chips now available. You
have sets of 64 and 128 bit registers, as well as the 80 bit floating point
unit. I think that the operations on the 64 bit data are the most interesting
in terms of bit boards. There may be reason to 'inflate' the data and use the
128bit regs too. I'm still trying to get a register map of my new Geforce 2
MX200 GPU chip, but there are 150 other GPUs out there that might not be
compatible with it's architecture.
>> You would have to make some constants variables and play around with
>> their setting algorithmically.
>
>
>Exactly the idea I've been thinking about! OTOH, I wonder how
>long it will take me to learn the code? I guess with a bit of
>help from you, it shouldn't be all that big of a deal. (Shrug.)
Most of the 30f's code is as received. It's a nasty tangle of conditional
compilation, however.
>> To be honest I never really got to understand eval() well.
>
>
>Quite understandable! I'm sure this is the "heart" of the program
>and where most of its playing strength is located. From your remark,
>though, it sounds like the code might need to be slowly picked apart
>and I/we could add some additional comments, possibly making the code
>a bit easier to read. Sometimes when I'm porting a piece of code
>to Linux, I'll actually re-write some of the sections of the program
>once I figure out what the original programmer was trying to do :^).
>Not the most elegant solution, but I've found out it is sometimes
>faster than trying to totally figure out a large program :^).
That was an effort on my part too. All the original code is there too.
>> I reasoned that part of the program was in better hands than mine
>> because I am not that great a chess player.
>
>Welcome to the club! :^)
>
>> But I could use my own craft to more efficiently use that knowledge.
>
>Good thinking, Dave! If I remember correctly, the hardware designer
>and lead programmer for DeepThought/DeepBlue is rated around 1200-1400
>(USCF) or so, yet he was capable of writing a program that was the world
>champion. IMHO, what's really needed in this particular ball game (Read:
>programming a computer to play a good game of chess) is good
>mental-association
>skills, pragmatism, and the ability to stick with a project and try out
>different things, even when the might seem a bit abstract at times.
It looks like you are sketching out your too do list. You would likely be
better off working on the current line of Gnu. I think that the only
improvement of mine that made it back to the main line was the addition of
another draw condition. The new one is bit board based.
Dann Corbit's Modified Sources:
ftp://cap.connx.com/pub/chess-engines/new-approach/gnuchess503.ZIP
The nicest thing about 30f is that it is *tiny* and you could easily add
sections to implement these heuristics.
Data or the Doctor, anyway. A formalism for intelegence integration would be
useful in either of those projects too.
>Oh...and don't forget that programming computers to play chess has a
>MUCH better chance of making you millionaire, if something like that
>is your long term goal :^).
I don't think I would have used Gnu for that purpose, at least the way I did!
>So, most of us aren't strong players. Who cares! What is important,
>IMHO, is that we can improve our game to the point where we're not
>all that bad. Also, if a person decides to take a shot at programming
>a computer to play chess, they might find some new heuristic that really
>gets things fired up in tree pruning or something, and an advancement
>like that just might ignite a whole new way of programming and really
>shake things up. One thing I do know, though: this will never happen
>unless some of us decide to say, "Screw this! I'm at least going to
>give it a try!" :^)
I can't recall the number of times I said something similar while initiating
the 25 minute compiles that produced a new version of Gnu back on my XT!
Guy Macon
DGiunti <dgi...@aol.community> wrote:
>
>NOP writes:
>> Mainly, I was just wondering if the
>> better programs out there still use assembly or not.
>
> If you are writing in C or C++ you can conditionally do both
> with the same program. If you encapsulate your assembly you
> just conditionally compile the program.
In my experience (many years managing software projects), the best
method is to write everything in C or C++ with *NO* thought of speed
(go for maximum elegance/clarity and minimum bugs), troubleshoot it
fully, them use a profiling tool to find out where the program is
spending most of it's time and optimize that. When optimizing, go
for a faster algorithm first, optimized C/C++ code second, and
assembly language last.
Read the Programming Pearls books for more details on optimizing.
Randall Jouett
Marcel van Kervinck wrote:
>
> Randall Jouett <ru...@bellsouth.net> wrote:
>
> > Back in the
> > mid to late 80's, I was thinking about using the the Amiga's built-in
> > bit blitter for move generation. This particular blitter could combine
> > 3 sources and either logically OR, AND, and NOR all of them together
> > (including shifts on the sources or destination) for one output.
> > I tried and tried to get that particular chip to take the current
> > position/bitboard as the source and "blit" new moves, but I could never
> > work out the algorithm correctly. I wonder if anyone out there has tried
> > this and was successful? It should be doable. I only wish I would have
> > had more time to work it out! :^/.
>
> My program copies attack tables for each move
> in the tree. Then it updates them according
> to the move. I found out that that was simpler and
> faster than then reverse-updating during undo-move().
> The memcopy would involve ~2*160 bytes (it is not
> just attacks in there). When I did this the main
> development platform was still the amiga. Naturally
> I tried to make it even faster by letting the blitter
> make the copy for me. It turned out not to work for
> a couple of reasons:
> - it was not a lot of data anyway
> - setting up the blit also costs time
Pretty much the same for me, Marcel. Setting up the
blit was a real killer.
> - it would not work on other hardware, and worse:
> - blitting was constraint to slow chip memory
I kinda figured that this was the case. Off the top of
my head, the blitter did look like it would have been
decent. Now that you mention all of this, I guess I
was lucky that I was in school and didn't have time
to work things out. :^)
> So I gave up on the idea of blitting chess.
Ok. Thanks for all the info, Marcel.
NOP
--
Randall Jouett
DGiunti
<_Email_Address_is_@_www.guymacon.com_> writes:
That is why I like the encapsulation by #define method. You can have all 3
ready to run with a single compilation unit. You can even target different
markets with the same code. It's harder to maintain down the line, but the
details of construction can not be escaped, and if you port to another system
you can adjust only the needed sections, or create another Macro to do the job.
Randall Jouett
Hello again, Dave.
DGiunti wrote:
>
> I am not sure about which of the leading commercial programs use BitBoards.
> A google search on that topic in this newsgroup would likely tell the tale. I
> think that some of them do and some of them don't. I know that Crafty and
> Gnuchess503 use them if you are looking for models to implement your ideas, as
> they are both freely available. I think that the bitboard approach is
> interesting. But I have not studied it usefully.
Well, they're having a big discussion on this particular topic on
www.talkchess.com (Computer Chess Club). Some interesting reading.
> Which compiler and platform do you plan developing in? There are slight
> modifications needed in the code to accommodate the differences.
Well, the current plan is to use gcc, profile the code, and then
optimise the critical sections in NASM. OTOH, I might want to make
the code portable over to Visual C++. Basically, I think I'm going
to shoot for portability.
> >today in ANSI C, setting up various constants and what not, and I finally
> >reached
> >the point where I asked myself, "Self, should you use bitboards or the old
> >tried
> >and trusted method of indexed arrays?" Mainly, I'm thinking about using the
> >index method for the sake of simplicity, getting the program up and running
> >in a
> >decent amount of time. OTOH, if bitboards are "the way to go" these days,
> >then
> >I guess I should consider using them.
>
> It's certainly an area where progress is possible! You could do it either
> way and possibly just interchange these references and see what the actual
> differences are.
Yeah. Sure could. Doing both could be a pain, though :^).
Ah. Kewl. I really miss programming in assembly, believe it or not :^).
To me, it does does seem a bit verbose at times. OTOH, every last detail
is spelt out, and it just seems easier to read to me than some C and C++
code. I don't know. Maybe I'm weird or something :^).
> > Mainly, I was just wondering if the
> >better programs out there still use assembly or not.
>
> If you are writing in C or C++ you can conditionally do both with the same
> program. If you encapsulate your assembly you just conditionally compile the
> program.
I was thinking exactly along these lines. Hopefully, NASM can play
well with gcc :^).
> Well, it's what you have to play with now that really matters. There is
> quite an array of processing power in pentium class chips now available. You
> have sets of 64 and 128 bit registers, as well as the 80 bit floating point
> unit. I think that the operations on the 64 bit data are the most interesting
> in terms of bit boards. There may be reason to 'inflate' the data and use the
> 128bit regs too. I'm still trying to get a register map of my new Geforce 2
> MX200 GPU chip, but there are 150 other GPUs out there that might not be
> compatible with it's architecture.
These registers would most definately help! :^) BTW, if you get the
register map, could you e-mail it my way? I'd like to take a look at
it, too.
> >> You would have to make some constants variables and play around with
> >> their setting algorithmically.
> >
> >
> >Exactly the idea I've been thinking about! OTOH, I wonder how
> >long it will take me to learn the code? I guess with a bit of
> >help from you, it shouldn't be all that big of a deal. (Shrug.)
>
> Most of the 30f's code is as received. It's a nasty tangle of conditional
> compilation, however.
Ton's of #ifdef code, huh? :^). No biggie. I just work around it.
BTW, sorry to taking so long to respond. Had tons of junk going
on around here.
> >> To be honest I never really got to understand eval() well.
> >
> >
> >Quite understandable! I'm sure this is the "heart" of the program
> >and where most of its playing strength is located. From your remark,
> >though, it sounds like the code might need to be slowly picked apart
> >and I/we could add some additional comments, possibly making the code
> >a bit easier to read. Sometimes when I'm porting a piece of code
> >to Linux, I'll actually re-write some of the sections of the program
> >once I figure out what the original programmer was trying to do :^).
> >Not the most elegant solution, but I've found out it is sometimes
> >faster than trying to totally figure out a large program :^).
>
> That was an effort on my part too. All the original code is there too.
>
> >> I reasoned that part of the program was in better hands than mine
> >> because I am not that great a chess player.
> >
> >Welcome to the club! :^)
> >
> >> But I could use my own craft to more efficiently use that knowledge.
> >
> >Good thinking, Dave! If I remember correctly, the hardware designer
> >and lead programmer for DeepThought/DeepBlue is rated around 1200-1400
> >(USCF) or so, yet he was capable of writing a program that was the world
> >champion. IMHO, what's really needed in this particular ball game (Read:
> >programming a computer to play a good game of chess) is good
> >mental-association skills, pragmatism, and the ability to stick with
> >a project and try out different things, even when they might seem a bit
> >abstract at times.
>
> It looks like you are sketching out your too do list. You would likely be
> better off working on the current line of Gnu. I think that the only
> improvement of mine that made it back to the main line was the addition of
> another draw condition. The new one is bit board based.
I'm also thinking in this direction, Dave. OTOH, I wonder how long it's
going to take me to get comfortable with the code? (Shrug.)
> Dann Corbit's Modified Sources:
> ftp://cap.connx.com/pub/chess-engines/new-approach/gnuchess503.ZIP
>
> The nicest thing about 30f is that it is *tiny* and you could easily add
> sections to implement these heuristics.
Now THAT sounds great! :^). I'll look at the code right after I finish
this message.
In the long run, I believe the cognitive science folks are going to
determine that intellect is nothing more than mental associations,
such as two things being compared to eachother, with logical analysis
deciding whether things go together or not. Actually, it's my belief
that this can and will be programmed, if hasn't been already.
> >Oh...and don't forget that programming computers to play chess has a
> >MUCH better chance of making you a millionaire, if something like that
> >is your long term goal :^).
>
> I don't think I would have used Gnu for that purpose, at least the way I did!
Same here, although if I ever found a really, really strong heuristic,
I think I might actually decide to create a my own program from scratch
and see if I could make a few bucks via shareware or something. (Shrug.)
OTOH, knowing me, I'd probably tell eveyone about it and just write a
paper for the ACM or something :^).
> >So, most of us aren't strong players. Who cares! What is important,
> >IMHO, is that we can improve our game to the point where we're not
> >all that bad. Also, if a person decides to take a shot at programming
> >a computer to play chess, they might find some new heuristic that really
> >gets things fired up in tree pruning or something, and an advancement
> >like that just might ignite a whole new way of programming and really
> >shake things up. One thing I do know, though: this will never happen
> >unless some of us decide to say, "Screw this! I'm at least going to
> >give it a try!" :^)
>
> I can't recall the number of times I said something similar while initiating
> the 25 minute compiles that produced a new version of Gnu back on my XT!
LOL! I know the feeling, dude! :^).
Nice talking to you again, Dave, and take care. Oh...and thanks a ton
for the source to gnu. I'll go take a look at it and give it a compile
or two in the next few days. Actually, I'll start adding some code
on Saturday. I'll keep you informed via e-mail.