maksimKorzh wrote: ↑Sun Sep 23, 2018 11:18 pm
Mr. Muller, I feel so excited finishing the move generator and greatly appreciate your help, many many thanks! Now it's time for me to take a hard decision of how to proceed. I really need your guidance now, could you please describe the pros and cons of keeping all-in-one search() compare to separate move generator from search. I'm tempted to choose the second approach just because that's pretty well-known territory, I mean I've done that before, but keeping the inlined style is for sure the way to learn something completely new. I really really doubt of how to proceed, what would you kindly suggest me?
It depends on what your goals are. 'All-in-one' search is not an all-or-nothing characteristic; there are several aspects to this. One is the omission of maintaining a move list to separate move generation from their search. That eliminates a lot of overhead, space as well as timewise. But it is likely to lead to a sub-optimal move ordering, and move ordering is the dominant factor in determining how deep your engine can search. So if the goal is to make a really strong engine, you should never compromise the move ordering. Poor move ordering is probably the major factor that limits micro-Max' strength.
Even advanced engines can use designs that have less separation of move generation and Search. With so-called 'staged' move generation there is no routine to generate all moves at once, but moves are instead generated in small batches, such as all captures, or even all captures on a set of pieces of equal value, killer moves, all non-captures. These are then produced 'on demand', whenever the Search() routine needs them. The advantage is that when a beta cutoff occurs, you will not have wasted too much time on generating moves you are never going to search. In a good engine more than 95% of all beta cutoffs are caused by the first two moves that are searched. The staged move generation in a sense has moved the 'master control loop' of the move generator back to the Search() routine again.
Another issue is how much redundancy you are willing to put in the board representation to speed things up. Micro-Max only uses a board array. This makes it easy to find the piece for a given square, but hard to find the square for a given piece. So to find its own pieces for move generation it has to scan the board, which is pretty inefficient. To figure out whether it is in check it must do a full move generation for the opponent, which is efficient code-wise (as it can use the Search() routine itself for it), but horrible speedwise. Tricks to do this faster only work if you kow where your King is, and having to scan the entire board just to find a single piece is prohibitively expensive.
So a less minimalistic design would, in addition to the board, keep a 'piece list', which keeps track of the location of each piece. This is in principle redundant information (and thus opens the possibility for bugs that cause the representation to become inconsistent, the piece list describing another position than the board). But it makes the piece -> square question a simple lookup. So you never have to search for pieces anymore. The board would have to encode pieces by a unique number to upate the piece-list, otherwise, when you move a Pawn, you would have to search the Pawn section of the piece list to find the Pawn in question and update its location, defeating the purpose. I sometimes still use a 'piece-type list', which keeps track of the location of the last-moved (or un-moved) piece of a given type. For pieces where only a single copy is on the board, such as the King, this would reliably track their location. But for others it would just give you the location of a sort-of randomly picke one of that type. It could still be useful in combination with a 'material key', (telling you wich material is on the board). E.g. when the material key tells you that there is only one Pawn on the board (i.e. you are in KPK), you can use the piece-type list to know where that Pawn stands in your special KPK evaluation. My semi-minimalistic engine ' KingSlayer' (the source of which can be found as the 'simple' project in my on-line repository at
http://hgm.nubati.net ) uses this technique.
A completely independent issue is how to organize the code that sill do whatever you finally decide should be done. I have the tendency to violate the common (and no doubt very useful) practice of keeping routines simple by subdividing their tasks, and delegating those to other subroutines (such as MoveGen(), MakeMove(), UnMake()) which it then calls. The advantage of not having a separate MakeMove() is that you have immediate access to all variables in Search(), which you would otherwise have to pass as parameters (which is extra overhead). The disadvantage is that you would need a separate MakeMove() for the moves at game level, unless you use some quirky 'exit from the upper floor' trick like micro-Max. In my more recent engines I limit parameter passing by locating (nearly) all local variables of Search() in a struct declare locally. Subroutines then have access to all of those without the need to make any copies, by just passing them a pointer to that struct. This makes the barrier for splitting tasks into separate sub-routines much smaller. And you can also pass such a pointer in the recursive call to Search(), so that all variables of the parent node are also accessible.
E.g. in the engine I am currently working on (for the 'Gigatron', an 8-bit retro computer) I use a routine SearchMove(), which performs the task of MakeMove(), (recursive call of Search(), UnMake() and the score minimaxing (so baiscally the entire boy of the loop over moves, except for providing the next move), an returns whether there was a beta cutoff or not. This can then be called in several places in Search(), as
if(SearchMove(&f)) goto cutoff;
(where f is the pointer to the struct with variables). This makes the staged move generation much more straightforward as you can just sequentially write the code for generating the various classes of moves (hash move, promotions, loop over capture victims, killer moves, non-captures), and call SearchMove() from each of those sections. This way Search() again starts to look like the 'master control loop' of the move generator, and in most cases can immeiately search the next move that is generated (without using a move list as an intermediate). For non-captures some sorting (e.g. by history score) can be desirable, though, so they would all have to be generated before any can be searched. It is questionable whether this should be done in a convetional move list, though; to get fast sorting it woul be better to bin them by history score (keeping a linked list for each score bin), and then simply search them bin by bin.
