ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

The Gigatron project
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 21705
Location: Amsterdam

PostPost subject: Re: The Gigatron project    Posted: Sat Dec 09, 2017 1:16 pm Reply to topic Reply with quote

Well, one of the problems with programming in assembler is that it is quite error prone, and that there is an appreciable chance that you will make errors even when entering code for a trivial task. So even when you have something simple that works, it will be a poor stepping stone to the more complex thing you eventually want, if that requires replacing code that does things in a simple way by the complex code. In a sense you are starting from scratch all over.

So I want to have a road map along an evolutionary development, which can improve sophistication by adding code to something that is already working, with only minimal changes (if any) required in that working stuff. So if my eventual goal is to do staged capture generation from an incrementally updated attack map, I think it would be a waste of time to first write something that generates captures by making ray scans over the board, put them in a move list, and extract them MVV/LVA order. Even if you had the latter, and it worked perfectly with perft and all, it would not have brought you an inch closer to the final goal. What would make sense is to write code that does generate an attack map from scratch, for the current position, and initially run the staged move generation from there. Then you can later add code in MakeMove/UnMake to keep an incrementally updated attack map of the same format, and add code to compare the two in every node. And when all obvious bugs in the incremental update are cured, switch to using the incrementally updated map for capture generation, and after that limit from-scratch generation and comparison only to the root, and when the engine is fiished, throw it away altogether.

That means that in any case I want my loop over moves in Search() to look similar to what it should look eventually; this wil be the core of the engine, and I don't want to have to completely replace that later. The C code I presented above isn't especially complex. It relies on tables, which should be initialized without errors, though, in particullar stripBit, which would hold stripBit[index] = index & (index-1), and set2dir[(1<<d) + n*(2<<d)] = (&neighbor[d]) >> 8 (with d=0 to 7 and n all possible integer values that keep the table index in the range 0 to 255). And consistency between the attBit[piece] and set2slider[attackersSet].

But it definitely is a good plan to start by making a version that is stripped of almost everyting that is not absolutely essential. That would indeed be a perft-like thing, as that would do away with everything that has to do with evaluation and alpha-beta pruning. Initially I also don't want to bother with the complications of e.p. capture, castling and promotion, so the perft numbers would not be correct, but who cares? Then material evaluation, minimaxing of scores and alpha-beta pruning can be added. Then best-move tracking and IID, using the best move of the previous iteration as 'hash move'. Then tracking of the PV, using the PV move (when available) as hash move.

Promotions

The thing that is still most unclear to me is how to best handle promotion. Because the design at various stages uses bit sets to represent a collection of leapers or sliders, the number of these cannot be allowed to exceed 8. For the sliders that would leave room for 3 extra Q, R or B, (as you start with only 5 of those), and for the leapers 3 extra Knights (after K, N, N, left-P, right-P). The sets will be used in the lookup tables set2leaper[] and set2slider[] to find their index in the piece table. Eventually the value in this index will have a meaning in itself, because although the piece list is traversed as a linked list, following the links, and thus potentially visiting them in any order, I want to detect whether futile victims are reached just from that index, rather than having to consult a lookup table for the piece value to see if the piece at that index is below the futilityThreshold, for every potential victim. Instead I want to translate the (high byte of the) eval-alpha difference to a piece index through a lookup table at the top of Search(), which tabulates the index of the first piece capture of which would not exceed the futility threshold. So it is important that the indexes represent the pieces in order of descending value, and that the linked piece lists respect this order.

So I have to reserve some entries early in the piece list for extra Queens, which can be done directly behind the King. As the King is always present, it would also be easy to insert such a Queen in the piece list (and take out the Pawn that promoted to it) on promotion moves. But since there is only room for 3 extra Queens in the bit sets, that means I cannot reserve a 'promotion Queen' slot for every Pawn, so that the promotion slots should be organized in a way that makes it easy to assign a slot to the Pawn that happens to promote. I guess this can be done by linking the spare slots into a list (using the same links as normally used to make them part of the piece list), and just unlinking the first element of that list on promotion.

For underpromotions it is more trick, however. I am not sure I want to allow those, and even if I do, they would only come at the latest stage of development. But since the way they would be handled would affect the design of the piece list, I want to reserve the required assets for them now, so that I wouldn't have to change the handling of the piece lists for the other pieces later. Ideally pieces from under-promotion would be assigned indexes between Rook and Bishop, so that they are in the right place irrespective of whether they are Knight, Bishop and Rook. (I don't care about the order of Bishops and Knights). It would be difficult to insert them there in the doubly-linked list, however, as you don't know what the intended closest neighbor is that is still on the board. That would require you to run through the piece list, looking for pieces in the middle. (Well, perhaps not a big deal. Under-promotions will be very rare, not considered in QS. So who cares if their MakeMove is slow and cumbersome?)

An alternative is to put an always-present dummy cell in the piece lists, (linked) between Knights and Pawns. If the index of that cell is the highest of all, then even when Pawn capture is not futile, the futilityThreshold would be set to this dummy cell, so that the loop generating their capture would automatically terminate after the last minor. We then would have to test if Pawn capture was really futile (a simple compare between the futilityThreshold and the idex of the dummy cell), and if not enter a loop for the capture of the Pawns, starting with the successor of the dummy cell. A later advantage of doing capture of Pawns and pieces in a different loop is that a simplified MakeMove() could then be used for the latter, as capture of a Pawn will have ramifications for the passer accounting.

Such a dummy cell in the piece list creates the possibility to easily insert pieces just before or just after the cell. Before it the under-promoted pieces can be inserted. That would short-change a Rook obtained by under-promotion, as it would now be behind the minors, so that its capture in some cases could be considered futile, while in fact it isn't. Well, tough luck. In the root you could correct this on the next move. I am not even sure I would want to make the program ever search under-promotion to Rook. (Although you can bungle a drawn KBPK if you are unaware of it.)

It is also easy to insert pieces directly behind the dummy cell. This could be used by considering 7th-rank passers a different piece type from other Pawns. So 'pre-promote' Pawns already when they reach 7th rank, delete their original entry from the piece list, and insert a new entry for them just behind the dummy cell. This does justice to the fact their value is around 200cP, and futility pruning could then take heed of their elevated status. I this case it is possible to reserve a cell for every Pawn, as individual Pawns are never indicated by a bit in a set; they are included in the set of leaper attackers by the direction from which they attack, and in this respect there is no reason to distinguish pre-promoted Pawns from ordinary ones. Allocatig a cell in case of pre-promotion then ivolves simply subracting a constant to the piece-list index.

The dummy cell also offers a starting point for running through the Pawn list for the purpose of generating promotions. You could just run through the list until you encounter a Pawn with an index in the range of unpromoted Pawns. Every pre-promoted Pawn you encounter that way only has promotion moves. Typlically there would not be any, of course, but it is nice to have a quick way for establishing that (namely that next[DUMMY] >= ORDINARY_PAWN).

This leads to the following assigment of piece-list indexes:

Code:
index piece type                  next    attBit
0x10 King                         0x12       0xC0  start of piece list
0x12 Queen                        0x1A  0x10
0x14 promo-Queen                  0x14  0x20       <- qSlots
0x16 promo-Queen                  0x16  0x40
0x18 promo-Queen                  0x80  0x80
0x1A Rook                         0x1C  0x08
0x1C Rook                         0x34  0x04
0x1E
0x30 under-promotion slot         0x32       0xA0  <- nSlots
0x32 under-promotion slot         0x80       0x90
0x34 Bishop                       0x38  0x02
0x36
0x38 Bishop                       0x3A  0x01
0x3A Knight                       0x3C       0x88
0x3C Knight                       0x7F       0x84
0x3E pre-promoted Pawn (for 0x5E)
0x50        "               "
0x52        "               "
0x54        "               "
0x56        "               "
0x58        "               "
0x5A        "               "
0x5C pre-promoted Pawn (for 0x7C)
0x5E Pawn                         0x70              ORDINARY_PAWN
0x70    "                         0x72
0x72    "                         0x74
0x74    "                         0x76
0x76    "                         0x78
0x78    "                         0x7A
0x7A    "                         0x7C
0x7C Pawn                         0x80
0x7E DUMMY                        0x5E

Note they are all even: the corresponding odd values will be for the opponent pieces. Also note they all have the 0x10 bit set; this is a kludge for facilitating calculation of mobility. At some point we will want to count how many of the moves of a given piece will hit occupied squares with friends or foes. (The friends should not be counted towards the piece mobility, the foes give valid captures.) This can now be done by ANDing the index of the occupant with 0x11, and adding the lot. The upper nibble will then count total number of occupied target squares, and the lower nibble the number of white ones. This total can then be used in a lookup table to get the the number of captures amongst them, and add that to the mobility. The edge guards would mimic empty squares here (use code 0x80, with both the 0x10 and 0x01 bit at 0).

Also note that the MSB of the leaper set is reserved for indicating the tabulated attBit represents a piece, and not the direction of a Pawn attack. This limits the number of representable leapers to 7, and thus the number of Knight under-promotions to 2 (if no other Knights are captured).


Last edited by H.G.Muller on Sat Dec 09, 2017 1:44 pm; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
The Gigatron project H.G.Muller Tue Dec 05, 2017 6:32 pm
      Re: The Gigatron project H.G.Muller Tue Dec 05, 2017 7:12 pm
            Re: The Gigatron project H.G.Muller Tue Dec 05, 2017 9:45 pm
                  Re: The Gigatron project H.G.Muller Wed Dec 06, 2017 2:44 pm
                        Re: The Gigatron project H.G.Muller Wed Dec 06, 2017 11:05 pm
                              Re: The Gigatron project Rémi Coulom Wed Dec 06, 2017 11:51 pm
                              Re: The Gigatron project H.G.Muller Sun Dec 10, 2017 11:51 am
                                    Re: The Gigatron project H.G.Muller Sun Dec 10, 2017 10:10 pm
                                          Re: The Gigatron project Rasmus Althoff Sun Dec 10, 2017 10:20 pm
                                                Re: The Gigatron project H.G.Muller Sun Dec 10, 2017 10:30 pm
                                          Re: The Gigatron project Stefano Gemma Mon Dec 11, 2017 11:15 am
                                                Re: The Gigatron project H.G.Muller Mon Dec 11, 2017 12:15 pm
                        Re: The Gigatron project Rasmus Althoff Thu Dec 07, 2017 9:44 pm
      Re: The Gigatron project Stan Arts Tue Dec 05, 2017 7:23 pm
      Re: The Gigatron project Dann Corbit Tue Dec 05, 2017 8:11 pm
            Re: The Gigatron project H.G.Muller Tue Dec 05, 2017 8:58 pm
      Re: The Gigatron project Rasmus Althoff Tue Dec 05, 2017 9:04 pm
      Re: The Gigatron project Fulvio Benini Wed Dec 06, 2017 8:31 am
      Re: The Gigatron project Martin Sedlak Wed Dec 06, 2017 11:42 am
            Re: The Gigatron project H.G.Muller Wed Dec 06, 2017 12:15 pm
                  Re: The Gigatron project Martin Sedlak Thu Dec 07, 2017 10:48 pm
      Re: The Gigatron project Ian Osgood Thu Dec 07, 2017 12:17 am
      Re: The Gigatron project Rémi Coulom Thu Dec 07, 2017 9:58 pm
            Re: The Gigatron project H.G.Muller Fri Dec 08, 2017 8:45 am
                  Re: The Gigatron project Stefano Gemma Fri Dec 08, 2017 11:07 pm
                        Re: The Gigatron project H.G.Muller Sat Dec 09, 2017 1:16 pm
                              Re: The Gigatron project Stefano Gemma Sat Dec 09, 2017 1:44 pm
                                    Re: The Gigatron project H.G.Muller Sat Dec 09, 2017 2:21 pm
                  Re: The Gigatron project Rasmus Althoff Sat Dec 09, 2017 7:27 pm
                        Re: The Gigatron project H.G.Muller Sat Dec 09, 2017 8:29 pm
                        Re: The Gigatron project Charles Roberson Sat Dec 09, 2017 9:30 pm
                              Re: The Gigatron project Rasmus Althoff Sat Dec 09, 2017 9:36 pm
                                    Re: The Gigatron project Martin Sedlak Sat Dec 09, 2017 9:57 pm
                                          Re: The Gigatron project Rasmus Althoff Sat Dec 09, 2017 10:10 pm
                                                Re: The Gigatron project H.G.Muller Sat Dec 09, 2017 11:31 pm
                                                      Re: The Gigatron project Stefano Gemma Sun Dec 10, 2017 9:01 am
                                                            Re: The Gigatron project H.G.Muller Sun Dec 10, 2017 11:32 am
                                                                  Re: The Gigatron project Stefano Gemma Sun Dec 10, 2017 12:24 pm
                                                                        Re: The Gigatron project H.G.Muller Sun Dec 10, 2017 8:44 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads