Author: Christophe Theron
Date: 19:52:48 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
And what do you think we are trying to do???
However I think you are right. Trying to optimize it right now is not a
priority. You will optimize when you have a stable program with good
performances. In the meantime, being able to experiment is your priority.
Christophe
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.