Author: Wayne Lowrance
Date: 06:59:58 11/19/02
Go up one level in this thread
On November 19, 2002 at 06:36:19, Uri Blass wrote: >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 Uri i am all for you. Nice fighting spirit. 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.