solve for chess

Tags:
Last response: in Video Games
Share

I think maybe the undecidability of arbitrary chess game endings had to
do with a halting problem, like a stalemate with only the kings left on
the board.

I would like to pry further and understand how programmers represent
moves in code. Besides the 64 bit representations, how do programmers
represent games. Do they simply write down a representation in code
language or do they write the fundamentally/mathematically most
efficient representations. Anyone have examples. I'm very interested.

--
entropy

Each programmer represents the state of the board differently in their
own engine. Some use bits, some use an 8x8 method, etc. There has been
a great deal of work trying to make things more efficient, because it
is the internal representation of the board that gets manipulated the
most during a search (add a move, evaluate the resulting position, take
back the move, add a different move, etc.) and this can happen an
incredibly large number of times during the search for a single best
move. I don't know all of the details, never having written an engine
(although I've certainly spoken with many engine writers).

But, if you're looking for a good place to start, I suggest here:

http://www.seanet.com/~brucemo/topics/topics.htm

jm
Anonymous

JVMerlino@aol.com wrote:

>(although I've certainly spoken with many engine writers).

Next time try listening to what they tell you.

<JVMerlino@aol.com> wrote in message
> Each programmer represents the state of the board differently in their
> own engine. Some use bits, some use an 8x8 method, etc. There has been
> a great deal of work trying to make things more efficient, because it
> is the internal representation of the board that gets manipulated the
> most during a search (add a move, evaluate the resulting position, take
> back the move, add a different move, etc.) and this can happen an
> incredibly large number of times during the search for a single best
> move. I don't know all of the details, never having written an engine
> (although I've certainly spoken with many engine writers).
>
> But, if you're looking for a good place to start, I suggest here:
>
> http://www.seanet.com/~brucemo/topics/topics.htm
>
> jm
>

A good site.

Regards
Anonymous

entropy <entropy.1v9ffz@news.chessbanter.com> wrote:
> I think maybe the undecidability of arbitrary chess game endings had to
> do with a halting problem, like a stalemate with only the kings left on
> the board.

It has nothing to do with the halting problem and chess endgames aren't
undecidable because we know many algorithms that compute them, in
principle, at least. The fact that these algorithms require unfeasibly
large amounts of time and memory doesn't affect decidability at the
theoretical level.

Dave.
--
David Richerby Hungry Psychotic T-Shirt (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a fashion statement but it wants
to kill you and it'll eat you!