Chess
da...@panix.com
Hi. I'm interested in writing a chess playing computer program
using minimax. I know I could probably get complete source somewhere,
but I would like the pleasure of doing it on my own. I'm interested in
the algorithm itself and not some of the overhead associated with a
game of chess (the pictures of all the pieces, the board, etc)
Is there somewhere where I can get source code to a game that already
has a nice graphical setup?
Also, is there a PD chess game that will output the computer's
best move given some kind of input from a file or command line?
(This way I could get my game to play against another implementation)
Lastly, a minimax question: How can I avoid analyzing duplicate game
trees? In other words, a board could end up the same exact way although
the moves to get there were different. How do I avoid rechecking the same
game scenario?
Thanks for any help
-Dan
Christopher Kashinath Patil
> [...]
>Lastly, a minimax question: How can I avoid analyzing duplicate game
>trees? In other words, a board could end up the same exact way although
>the moves to get there were different. How do I avoid rechecking the same
>game scenario?
Analysts of chess call this situation a "transpose" -- i.e., if one series
of moves leads to the same board as another, it is said to transpose to that
line of moves. Note that in addition to the configuration of the board (which
is essentially a string of 64 characters), an additional piece of information
is required, namely, which side is to play: each configuration of the board
is actually two positions, which can be distinguished by an additional bit
that indicates whether black or white is to play from that position. Obviously
this is irrelevant at the starting position, less important during the opening,
but crucial during middlegame and endgame.
It strikes me that since each position is str(64) plus 1 bit, one could
keep track of positions that have been analyzed in a tree by simple string
matching, i.e., has this string arisen before? If yes, then refer to the
previous analysis; if not, analyze de novo.
This is a fascinating project (other readers -- refer to the initial post).
To the original author: I beseech you to keep us posted on your progress!
--
Chris Patil Stanford University
cpa...@leland.stanford.edu Department of Biological Sciences
"That in our day such giant shadows are cast by such pygmies only shows
how late in the day it has become." -- Chargaff, referring to Watson & Crick
Bruno Wolff III
]
] Analysts of chess call this situation a "transpose" -- i.e., if one series
] of moves leads to the same board as another, it is said to transpose to that
] line of moves. Note that in addition to the configuration of the board (which
] is essentially a string of 64 characters), an additional piece of information
] is required, namely, which side is to play: each configuration of the board
] is actually two positions, which can be distinguished by an additional bit
] that indicates whether black or white is to play from that position. Obviously
] this is irrelevant at the starting position, less important during the opening,
] but crucial during middlegame and endgame.
Chess actually has other information that is relevant to positions.
You need to know which castling options are still available.
You need to know how many times this position has been repeated.
You need to know how many moves have occured since the last pawn move or
capture.
For tournament games the clock situation is also relevant.
Johanes Suhardjo
> Also, is there a PD chess game that will output the computer's
> best move given some kind of input from a file or command line?
Try gnuchess.
> Lastly, a minimax question: How can I avoid analyzing duplicate game
> trees? In other words, a board could end up the same exact way although
> the moves to get there were different. How do I avoid rechecking the same
> game scenario?
Use a hash table. Look at a book such as Levy's "How Computers Play Chess"
or look at the source code of gnuchess.
BTW, I'm not a(n established) chess programmer, if you want more specific
pointers, you should cross-post to rec.games.chess, there are many chess
programmers reading that newsgroup.
Johanes Suhardjo (joh...@farida.cc.nd.edu)
--
When the weight of the paperwork equals the weight of the plane, the
plane will fly.
-- Donald Douglas
David Boll
: Lastly, a minimax question: How can I avoid analyzing duplicate game
: trees? In other words, a board could end up the same exact way although
: the moves to get there were different. How do I avoid rechecking the same
: game scenario?
This is a question with no easy answer. Typically, you're only storing
2 boards at the current ply: the current-move board, and the best-so-far
board. So, in order to do what you suggest, you must store some information
that you otherwise wouldn't. Three options come to mind:
1) Store the entire board + some kind of hashed value + score for that
board. Now, use the hash to see if you've encountered a position before.
If so, compare the boards. If a match, pull the score.
Problems: memory intensive.
2) Put a lot of effort into move sorting. If a position is really good, it
will be in the best-so-far board, if it isn't it will hopefully get pruned
away. So, check against only the best-so-far board.
3) Store only the score and a couple very different hash values for the
board. Hope you never have hashing problems!
In addition to these, you have the default options of not worrying about
it, or looking only 2 ply deep (with a seriously good scoring function!).
It's been a while since I've messed with Chess, but with a variety of other
games, I've experimented with move sorting using the current scoring
function. I was surprised at how much this improves the search! Initially,
I thought that the scoring function was so slow (relatively) that it would
not be good to sort with. But, pruning buys you so much that it more than
makes up for it.
---------------
Dave Boll db...@hp-vcd.vcd.hp.com
"The speed of time is one second per second"