Author: Wayne Lowrance
Date: 13:35:21 11/18/02
Go up one level in this thread
On November 18, 2002 at 06:59:15, Uri Blass wrote: >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 Ummmmm, ohhhh, okey dokie thanks Wayne
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.