Author: Bob Durrett
Date: 09:22:05 11/17/02
Go up one level in this thread
On November 17, 2002 at 11:36:52, Christophe Theron wrote: >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 Thanks.
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.