Author: Roberto Waldteufel
Date: 15:45:11 04/07/99
Go up one level in this thread
On April 07, 1999 at 17:09:52, David Eppstein wrote:
>On April 07, 1999 at 12:10:20, Roberto Waldteufel wrote:
>> I wonder how many here have programmed other games besides chess.
>
>I have written a non-chess game (Fanorona, see
>http://www.ics.uci.edu/~eppstein/180a/projects/fanorona/) and have run
>a project class where undergraduate groups program games like
>checkers, connect-4, go-moku, etc.
Yes, much of the basic look-ahead code is the same as it would be for chess, but
to produce a really strong program it is almost always necessary to pad it out
with a great deal of game-specific stuff that tends to obscure the similarity.
>On the other hand, I have never written a chess program -- I read this
>board primarily for programming tips that will help with other games,
>although I also like to play through the various computer-gm games etc.
>
>> In fact, I used bitboards for my first ever
>> attempt at checkers before knowing about their widespread use in chess, so
>> when I came to program chess I was naturally inclined to lean heavily in the
>> direction of bitboard representations of information.
>
>My impression is that bitboards work even better for other games than they do
>for chess, because of the lack of so many different kinds of pieces. My
>Fanorona program is bitboard based. It is hard to persuade the undergrads to
>use bitboards, because bit-parallel programming is so unfamiliar, but I think it
>is a powerful way of programming that can be used in many areas (e.g. I also
>recently wrote a bit-parallel graph traversal code as part of a fast cellular
>automaton spaceship searching code).
>
Yes, bitboards are really pwerful, and widely applicable too, but, as Bob Hyatt
puts it, you have to learn to "think bitboards" - I expect that is what your
students find difficult. My advice to them would be to persevere - it's well
worth the effort. However, if they won't listen to you, I'm sure they won't
listen to me either. This last application sounds very interesting.
>> On 24 April there is to be a match between my program
>> and Nexus99, one of the top commercial checkers programs.
>
>Please do let us know how this works out.
I am quite willing to post results and game scores here, but I am worried that
this might be considered off topic. Comments from moderators about this would be
welcome. If it is considered relavant, I will certainly oblige, but I don't want
to transgress the rules of this fine CCC.
>You're using the chinook endgame dbs?
Well, actually, no. My program does, however, have quite a lot of endgame
databases that I generated myself. My main problem with the Chinook databases,
and also with the Nalimov Chess Tablebases, is that I am virtually
"C-illitarate". I program with PowerBasic 32-bit compilers. All the code for
accessing the existing databases (both for chess and checkers) is in C, which is
unfortunately beyond my understanding, so I tend to concentrate on generating my
own tablebases, although of course I am quite well aware that I am re-inventing
the wheel, so to speak. There is an added bonus that the databases are
structured to fit in with the program's board representation, whereas with the
Chinook databases it would be necessary to convert the board to the "Chinook
representation" for each probe, which would slow things down somewhat, but if I
properly understood the access code I could probably write a translation program
that could convert the Chinook databases to a format more suited to my own board
representation, which would undoubtedly be quicker and easier than generating
the information from scratch.
>
>What sort of knowledge goes into your eval?
>My undergrads last quarter just counted pieces and kings but found that the
>program moved really erratically in the endgame when it ran out of trades --
>their program would really have benefited from some knowledge of the opposition,
>or space control, or both.
>
There are many things I use. Some of the more important ones:
1) recognition of several sorts of binds and holds
2) centre control/occupation
3) states of the respective king rows
4) possibility to pitch a piece (sometimes even 2 pieces!) so as to run for a
king. Very few (possibly none?) other programs do this.
Also, my program encorporates a limited learning facility that allows it to
learn from its losses, although now it is fully debugged it does not lose very
often. It can be quite effective though when I make the program play against
itself.
>> I think the same techniques that have proved themselves in computer chess are
>> applicable to several other games, such as Shogi, Go and of course checkers
>> too.
>
>Historically alpha-beta hasn't worked for go, but it does seem to work for many
>other games. The usual explanation is go's high branching factor, but I don't
>believe that because gomoku has the same branching factor and alpha-beta works
>ok for that game.
I suspect it is the high branching factor rather than alpha-beta itself that is
the problem. Probably a selective aplpha-beta search is quite a viable option,
but as always the selection of plausible moves is very problematic. It should
not be forgotten that in the very early days of computer chess the branching
factor was also considered to be impossibly high for full width searching,
although now, with improved algorithm enhancements and faster hardware, full
width is the norm rather than the exception. I am afraid I know practically
nothing about this most complex game, and I have never attempted to program it.
And finally, an invitation to those of your students who have dabbled in
checkers: I have found one of the greatest obstacles after debugging was
complete was finding opposition agianst which I could test the program. If any
would like to pit their creations against my own, I would be very interested in
playing some e-mail games between our respective babies. Please pass on my
challenge to any of your budding checker programmers. I can be contacted at
RWaldteufe@aol.com
Perhaps we could all learn something from such games. Wyllie (my program) has
already played several games in this way against both carbon and silicon
opponents, and is always on the look-out for more victims - oops - I mean
opponents!
Best wishes,
Roberto
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.