Author: Uri Blass
Date: 04:05:02 10/25/02
Go up one level in this thread
On October 25, 2002 at 06:26:39, Uri Blass wrote: >On October 24, 2002 at 15:37:51, Alessandro Damiani wrote: > >>On October 24, 2002 at 14:45:57, Uri Blass wrote: >> >>>On October 24, 2002 at 12:27:29, Alessandro Damiani wrote: >>> >>>>On October 24, 2002 at 07:09:17, Uri Blass wrote: >>>> >>>>>How many function do you have in an incremental move generator? >>>>> >>>>>If I understood correctly programs use >>>>> >>>>>1)Generatehash(generates nothing if the hash move is illegal or null) >>>>>2)Generategoodcaptures >>>>>3)Generate killer1(generates nothing if the first killer is illegal) >>>>>4)Generate killer2(generates nothing if the second killer is illegal) >>>>>5)Generating rest >>>>> >>>>>I think that 1,3,4 may be the same function because in all of them I need to >>>>>check if a move is legal when I have the move(includes the from square the to >>>>>square and more information in case of promotion). >>>>> >>>>> >>>>>I first think only to have generatehash and generaterest but generaterest >>>>>already means that I have to change my move generator. >>>>> >>>>>I doubt if generating rest is faster than generating all because I need to check >>>>>for every candidate move that it is not a previous move that I already >>>>>generated. >>>>> >>>>>Uri >>>> >>>>What do you exactly mean by "incremental move generator"? My definition is that >>>>one only generates the difference in the move lists between the previous node >>>>and the current one. >>>> >>>>Do you really mean this approach? >>>> >>>>Alessandro >>> >>>I am not sure exactly what do you mean. >>>Node for me is only a position after moves that I make. >>>During generating moves there are not new nodes. >>> >>>I thought about generating part of the moves. >>> >>>Today movei has no function to generate part of the >>>moves. >>> >>>I have only generating all the moves and >>>even my qsearch does not have generating >>>only captures. >>> >>>I generate all the moves and continue to search >>>only captures and also checks in the first plies. >>> >>>I also use the number of legal moves for >>>my evaluation so I need >>>at least to count the number of moves in the >>>qsearch if I want to have the same program. >>> >>>I first want to have the same program faster and >>>only later to test changes in the algorithm. >>> >>>I cannot avoid counting the number of legal moves >>>at the last plies without changing the evaluation >>>because the number of legal moves is used for >>>evaluation not only in the leaves. >>> >>>Uri >> >>I thought of "parent node" and wrote "previous node". Sorry. >> >>Ah, ok, by "incremental" you mean "in chunks". That's what (all) bitboarder do, >>since it is in the nature of bitboards that captures can be generated at the >>minimum cost. >> >>First of all: did you consider to determine your mobility by attack detection >>without counting moves? I ask you this because the biggest cost in searching and >>evaluating is at the horizon and below. So, generating all moves there just to >>count legal moves is not optimal in my eyes. Additionally you only need a subset >>of all moves there. So, your mobility costs a lot: you could evaluate other >>aspects of a position more accurately instead. >> >>The implementation of generating moves in chunks is easily done by encapsulating >>all work in a method that returns the next move: >> >> Move nextMove(int ply, ...) >> >>The value 0 is returned, if there is no move anymore. >> >>The method nextMove() has a state for each ply: in which generation phase it >>currently is. For instance, our move ordering is >> >> 1. hashmove >> 2. winning captures >> 3. killer 1 >> 4. killer 2 >> 5. equal captures >> 6. non captures >> 7. losing captures >> >>We define the following phases: >> >> PHASE_HASHMOVE 0 >> PHASE_GENCAPTURES 1 >> PHASE_POSCAPTURES 2 >> PHASE_KILLER_1 3 >> PHASE_KILLER_2 4 >> PHASE_EQUALCAPTURES 5 >> PHASE_GENNONCAPTURES 6 >> PHASE_NONCAPTURES 7 >> PHASE_NEGCAPTURES 8 > >Today I also have phases nit clearly less phases than you. 1)It should be but and not nit(*ni* are close to *bu* in my keyboard and this is my excuse for this mistake) 2)The question that I ask myself is how to do the change to do movei faster. The point is that I want to do one change and test and not to divide the move generator to a lot of functions. I do not like the idea of a function that is only for generating next move. The problem is that in case that I generate few moves and they do not help then I may need probably to generate all of them so I do not save a lot of time by this and I suspect that I use more time in that case because I need to check that the next move that I generate is not in the list that I already generated. Generating the last move is espacailly slow and can take o(n^2) because after doing the steps to generate a move I need to compare it with average number of about n/2 moves only to find that the move alreasy appeared in the list. It may be possible to do it faster by having a big array for the moves that appeared but I do not like having some big array and it seems more complicated. I wonder how people who use incremenatal move generator(one after one) can make it fast when there is no rules for the previous moves(hash, killers,captures). The only case when I understand how it can work fast is if you simply generate pawns moves and later knight moves,..bishops move,rook moves,Queen moves,King moves when you have only few moves that you remember but with all the phases that are defined in this post it does not seem to be the case. 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.