Author: Uri Blass
Date: 10:06:04 11/17/02
Go up one level in this thread
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
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.