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: 21477
Location: Amsterdam

PostPost subject: Re: The Gigatron project    Posted: Wed Dec 06, 2017 2:44 pm Reply to topic Reply with quote

Basic operation

The design I have in mind will use a neighbor table, which for each occupied square will hold the square number of the nearest neighbor in each of the 8 principal directions. This nearest neighbor can be an edge guard, when there is nothing between the square and the board edge. So the table will have to contain 10x10 elements, although for any particular direction the final element along that direction (always just beyond the board edge) will not have a further neighbor.

Then there will be an attack map, for each square holding bit flags to indicate attacks on it. There will actually be 4 such board size tables, for white and black attackers each a set of slider and a set of leaper attacks. The slider attacks will be flagged by direction, 1 bit for each direction of movement. The leaper attacks will be flagged by piece for King and Knights, (3 bits, perhaps 4 if we want to allow for a 3rd Knight), but by direction for Pawns (4 bits, one for each diagonal direction).

For the update of the attack map it will be handy to also record attacks on the edge guards, so that these can be treated exactly the same as on-board attacks. This means the slider attack maps will have to be 10x10. For leapers it would also be inconvenient having to test all the time whether a potential attack goes off-board or not, and the map will even have to be 12x12 to make sure it catches all Knight jumps. Leaper attacks will be valid for any square; we will just apply or remove them to the map whenever the leaper resposible for them gets moved or captured. Slider attacks will only be faithfully recorded on occupied squares, to limit the cost of updating (as sliders can attack very many unoccupied squares).

The piece list will be set up as a doubly-linked list, so that captured pieces can be easily removed from them. (And then re-inserted on UnMake().) The neighbor tables are in fact also a collection of doubly-linked lists, one for each ray, so that each occupied square is aware of its two neighbors on the ray through its forward and backward links. Evacuating a square will just remove if from the lists for all 4 rays it is on, and re-occupying it during UnMake will re-insert it, based on its old neighbors, which it still remembers.

Generating captures will be done by running through the piece list, which is kept in order of decreasing piece value. The piece numbers produce the piece locations, the locations produce the set of attacks on it, all through lookup in the appropriate table. The attacks will be extracted from the set also by table lookup. For leapers this would result in a piece number for the attacker (K or N), which finally is used to look up the location of the attacker. This leaves all 4 descriptive elements of the move (fromSqr, toSqr, piece and victim) known, so the capture can be made and searched. A Pawn would result in a recognizably invalid piece number (like negative or beyond the end of the piece table) when its turn comes up to be extracted. In this case the number would be used to index a table that contains the board step of the Pawn capture, which, added to the to-square, would produce the from-square, and finally through lookup on the board the number of the attacking piece (a Pawn).

Code:
victim = nextPiece[victim]; // step through piece list
toSqr = location[victim];
leaps = leaperAttacks[stm][toSqr];
while(leaps) {
  piece = set2leaper[leaps]+stm; // extracts in order Pawns, Knights, King
  leaps = stripBit[leaps]; // clears lowest set bit, for next iteration
  if(piece <= MAXPIECE) {
    fromSqr = location[piece];
  } else {
    step = pawnSteps[piece - MAXPIECE]; // 4-entry table
    fromSqr = toSqr + step;
    piece = board[toSqr];
  }
  if(SearchMove()) goto cutoff;
}
// go on with slider attackers

For sliders the situation is a bit more complex. Because their attacks are kept by direction, we canot be sure they are extracted in LVA order, and it will be necessary to sort the attacks. This will be done by first converting the direction-wise attack set to an attackers set, where each bit corresponds to a particular slider. The latter will then be extracted in the order B,B,R,R,Q. to make the actual captures. So the data flow here also starts from victim to location to sliderAttacks, but then it extracts direction, neighbor, attacker, attackerBit to OR that ito the attackers set. nI the second pass then attackers -> piece -> fromSqr. Again, all through sequential table lookups:

Code:
slides = sliderAttacks[stm][toSqr]; // we already had determined toSqr and victim
attackers = 0;
while(slides) {
  direction = set2dir[slides]; // actually we tabulate &neighbor[direction]...
  fromSqr = neighbor[direction][toSqr]; // ... so we can do fromSqr = direction[toSqr] here
  piece = board[fromSqr];
  attackers |= attBit[piece];
  slides = stripBit[slides];
}
while(attackers) {
  piece = set2slider[attackers]+stm;
  fromSqr = location[piece];
  attackers = stripBit[attackers];
  if(SearchMove()) goto cutoff;
}

This generates captures very fast, just 6 or 7 table lookups and an occasional ADD or OR. And most of that is what you would normally do anyway to fetch and/or unpack a move from a move list, to get fromSqr, toSqr, piece and victim, in order to perform a MakeMove(). And you ca stop generating as soon as you reach the futile victims, i.e. if victim > futilityThreshold (which you would determine in advanced based on the high byte of alpha - curEval, through another table lookup).

Non-capture generation could be done in the usual mailbox way, by running through your own piece list, and for each piece through a list of directions, and for each direction along the ray until you hit a non-empty squere (for a slider) or just one step (when it is a leaper). I am not sure if it would have any benefits to use history to order the non-captures; this would definitely cause a lot of complication. Maintaining a list of a dozen or so 'hot moves', and checking if these are possible in the current position, similar to what is done with killers, and then do them before non-capture generation might be faster than putting all non-captures in a move list, assigning them a history score, and sorting the lot.
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