Author: Christophe Theron
Date: 08:36:52 11/17/02
Go up one level in this thread
On November 17, 2002 at 08:42:14, Bob Durrett wrote:
>On November 17, 2002 at 05:07:01, Ricardo Gibert wrote:
>
>>On November 17, 2002 at 03:15:15, Frank Schneider wrote:
>>
>>>On November 16, 2002 at 22:08:55, Christophe Theron wrote:
>>>
>>>>On November 16, 2002 at 22:00:27, Bob Durrett wrote:
>>>>
>>>>>
>>>>>I was thinking it might be *fun* to create a machine which does nothing more
>>>>>than create legal move sequences from some preset legal chess position. These
>>>>>sequences might be dumped into a large part of RAM for later copy to a hard disk
>>>>>or printout.
>>>>>
>>>>>The key idea I'm toying with is to represent a chess position by a listing of
>>>>>legal moves. Whenever a new move is made [by the person (or thing) playing
>>>>>against the machine, or by the machine if it's playing against itself,] then the
>>>>>machine would do nothing more than modify that listing (plus copy the move
>>>>>representation to a temporary storage place in RAM). The new listing of legal
>>>>>moves would then represent the new position. The key idea is to represent a
>>>>>position by a listing of legal moves. When a move is made, there is a "from"
>>>>>square and a "to" square. Only consequences of changes made on these two
>>>>>squares would have to be considered to modify the legal move list.
>>>>>
>>>>>Then, to make it more interesting, a really fast random number generator would
>>>>>be used to select one of the resulting legal moves. If the machine were playing
>>>>>against itself, the sequences of moves should be generated very quickly. How
>>>>>quickly?
>>>>>
>>>>>In the beginning, I am only interested in the time it would take to modify that
>>>>>listing. The machine could play both sides, removing the need for
>>>>>time-consuming input/output. After generating a legal move sequence ending in
>>>>>mate, it would then start working on the next legal move sequence. After a
>>>>>million or so moves were made, then the time required could be divided by the
>>>>>number of moves. That resulting time per move that I'm asking about. Rather
>>>>>than worry about the fact that some computers are faster than others, maybe the
>>>>>best bet would be to express it as number of clock cycles per move. A modern
>>>>>high-end processor should be assumed.
>>>>>
>>>>>Each sequence would be what two "really dumb" chessplayers would produce if they
>>>>>knew how to produce legal moves but knew NOTHING at all else about chess.
>>>>>
>>>>>P.S. Is there a better way?
>>>>>
>>>>>Bob D.
>>>>
>>>>
>>>>
>>>>Don't you need to prove first that two different chess positions will always
>>>>have a different legal moves list?
>>>
>>>Hi Bob,
>>>
>>>there are many different positions with the same move list, e.g.
>>>all stalemate-positions, all positions where e.g. Ke1xqf2 is the
>>>only legal move, ...
>>>
>>>Frank
>>
>>
>>He knows that. He wasn't asking the question for his own benefit.
>
>Christophe, you read me wrong. I really WAS asking the question for my own
>benefit. I wanted to understand something.
>
>At the time I wrote that, I didn't realize that the same legal move list could
>have multiple positions. However, that doesn't matter (!!) in the application I
>was asking about.
>
>What I was trying to do was to produce a machine which would generate sequences
>of legal moves. A move generator, if you wish. I wanted to know whether or not
>the method I was thinking about would be efficient.
>
>I would like to know how much time [expressed as processor clock cycles] a legal
>move generator ought to take, on average, to produce one legal move, i.e. if it
>were efficient. With that information, I could compare my method to determine
>it's efficiency.
>
>Sometimes I don't communicate very well. I apologize for that. : )
>
>Bob D.
There was no evil intend in my question. I do not know exactly what algorithm
you had in mind, but as you started to play with the idea to represent chess
positions by their move lists it seemed natural to ask the question about the
1:1 relationship.
I think you should not care about "legal moves" but only about "pseudo-legal
moves". That is, moves that are legal plus moves that would be legal if leaving
or putting the King in check was allowed.
Generating pseudo legal moves is more efficient than trying to generate only
legal moves. The reason is that the extra work needed to check the legality of
each move will be most of the time wasted in a real chess program, because most
move lists will not be searched fully (the search will stop after trying a few
moves, so the rest of the move list will not be used at all).
In general, it is a good idea to make as little work as possible in a chess
program, keeping in mind that the search algorithm can stop before reaching the
end of a move list (it happens really often).
For example in Chess Tiger I almost never generate complete move lists. I have
an incremental move generator that returns only one move (the next one) each
time I call it. The extra overhead of having to call the move generator for each
move and having to keep somewhere the state of the generator is by far
compensated by the fact that most of the time the search (at a given ply depth)
will stop typically after generating 2 or 3 moves (it stops because of what we
call an alphabeta cutoff).
So I believe that the move generator in Chess Tiger is slow if you compare it to
an experimental fastest-as-possible move generator, but I insist that it must be
one of the most efficient at the same time. If my evaluation and selectivity
system was not so slow, I could reach a very impressive NPS with that "slow"
move generator. Because it is better to generate 2 moves twice as slow than 35
moves twice as fast...
Now if you really want to produce the fastest move generator, which is pointless
if your ultimate goal is a top level chess program, here is an idea:
Write code that will generate assembly code. The assembly code will, for every
piece on every possible square, generate as quickly as possible the list of
moves (squares) that this piece can reach when it is on this square. Naturally
the code will check for blocking pieces.
I think the generated code will not be very cache-friendly, but I still think
that it might be the fatest move generator you can write on a general purpose
processor.
This idea has been found in 1992 by a friend of mine. It was not very practical
at that time because of the 64Kb limit of the 16 bits x86 memory model, but it
should be a no-brainer on the x86 32 bits flat model.
That said, I repeat that this will not help you to create a strong chess
program.
Christophe
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.