Author: Uri Blass
Date: 03:36:19 11/19/02
Go up one level in this thread
On November 18, 2002 at 16:35:21, Wayne Lowrance wrote: >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 I do not understand the last comment(I guess that you are surprised that I hope to be better than the commercial programs in tactics) only some comments 1.I guess that being better than the commercial in tactics is not going to happen in the very near future. I believe that I have the right ideas but but human time in programming and computer time are needed to implement my ideas. Other programmers may implement my ideas in less human time but I plan to try to implement them by myself. 2.I expect tactical improvement in movei in the future but I also can expect it not to be better than the commercial programs in tactics in the next 12 months. 3.I only expressed my hope. No promise. I believe that there are good chances for it but I do not know and only the future will tell more information. I believe that my ideas about pruning and extensions can give the commercial programs a push of at least 100 elo but again it is only a guess and I do not know. In the near future I only plan to improve my pruning rules and not to improve my extension rules and I do not guess that only improving the pruning rules is enough to become better than the commercial programs in tactics. 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.