Author: Uri Blass
Date: 03:59:15 11/18/02
Go up one level in this thread
On November 17, 2002 at 18:20:18, Christophe Theron wrote: >On November 17, 2002 at 13:06:04, Uri Blass wrote: > >>On November 17, 2002 at 12:52:00, Uri Blass wrote: >> >>>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). >>> >>>There is also an advantage for generating all the legal moves >>> >>>Chest (the best program to find the shortest mate) is generating only legal >>>moves. >>> >>>In order to be faster in generating legal moves I needed to generate my attack >>>arrays and my pin arrays and update them incrementally after every move. >>> >>>These arrays can be used in the search rules or in the evaluation. >>> >>>There are also cases when in generating moves I have not the extra work of >>>cheking if the move is legal(for example if my pin array tells me the knight is >>>pinned I know that no move of it is legal) but I admit that in most cases I need >>>to check if the piece is pinned so I have some small extra work. >>> >>>Uri >> >>Note that the latest post gives me ideas how to do my move generator faster but >>I do not know if I am not going to implement them in the near future. >> >>I should have the pinned pieces first or last in my piece list so I can have >>special generate move for pinned pieces and for pieces that are not pinned. >> >>The problem is that my list does not include all the pieces and there is a pawn >>list,a knight lise a bishop list,... >> >>I still think that it is possible to earn speed here. >> >>one idea is to remember the number of pinned pieces and in case that it is >>0(common case) to have a faster generate move. >> >>it can save me by one if a lot of if (pin[square]==-1) for pieces >> >>Uri > > > >In 1992-1993 I have tried several approaches to move generation. I have tried >the "attack boards", "update attack tables" and "update move lists". > >I had great hopes with these methods and spent a lot of time trying to optimize >them. > >For the reasons I have explained above (most of the time you get an alphabeta >cutoff early) I have found these approaches to be inferior to an incremental >move generator. > >The biggest problem then is to be able to generate an ordered move list. That >is, to be able to sort the move list in a reasonable order without generating >all the moves. For me another problem is that in case of incremental move generator I have less knowledge. For example I cannot use the number of moves for my decision if to extend or not to extend. > >It's very difficult to achieve a good move order. The worse is that it is >extremely difficult to experiment. Changing the order of generation means >changing everything in the incremental move generator. The incremental move >generator is nontrivial a state machine. On top of this add L1-cache >optimization and it becomes really difficult to write it. I think that this is another good reason for me not to spend time today about incremental move generator. I think that I can earn more from better pruning rules and better extension rules. I never did L1-cache optimization for movei. I have hopes that even without it better pruning rules and better extension rules may give me a big improvement to do movei tactically better than the commercial programs. Uri
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.