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

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

Memory allocation

The Gigatron has only one addressing mode where it combines a constant from the instruction with a register, and in that case the register will deliver the high byte of the address. As we will need to access many tables indexed by square or piece numbers, and it would be a pain to have to load the fixed part of the table address into a register, the best way to do this is to store the pages 'vertically', i.e. let the low address byte determine the table, and the high byte the index. Because there is only 32KB RAM, and not 64KB, the high 'byte' of the address actually is just 7 bits; the 8th bit is ignored. This means that vertically stored tables can contain at most 128 bytes.

Now this is (barely) large enough for a board plus the surrounding band of edge guards. The square number of a square (x,y) (where (0,0) = a1) can be made sqrA1 + 10*y + x. Knight moves made from h8 can end up at (9,8), which gives sqrA1 + 98, while from a1 they hit (-2,-1), which gives sqrA1 - 21. This spans 120 bytes in total, which will fit vertically in memory with only 8 pages to spare. The leaper attack maps for black and white will also have this size. We will allocate such tables in the high bytes of of the memory pages. E.g. the board at addresses $xxFF ($ meaning hexadecimal), with xx = 08...7F, the black attack map at $xxFE, etc.

This means that there are only 8 memory pages that are only 8 memory pages still completely empty; all others will have to suffer some table bytes at their upper end. Tables that would need more than 128 bytes can only be stored horizontally, and tables >= 256 bytes would really be problematic. But fortunately we do not need the latter. We do need some tables of exactly 256 bytes, though. They must be stored horizontally, and only 8 pages are still available to do this.

These 'full-size' tables are a table to extract the directions from a slider attacks set, which can have all bits, and the table containing the index with the lowest bit cleared. Other sets of attackers do not use the upper bits, so bit extraction from those could in principle be done with tables of 128 bytes or smaller. Now perhaps I am exaggerating here, because it seems not possible that slider attacks come from all 8 directions at once. Since Bishops will be on different colors, at most 4 sliders can be aimed at the same square, and the highest code with four 1 bits is $F0. And there is room to be smart here: we can assign the upper 4 bits to diagonal directions, and the lower 4 bits to orthogobal directions. There can be at most 2 diagonal slider attacks on the same square. So the largest possible code is then $CC = 204. This leaves 51 bytes at the top of the page unused. Which should be enough for all vertically stored tables.

Now there is still another matter for which we will need full-size tables, which is related to 16-bit arithmetic for scores. Unfortunately the Gigatron has no condition codes, and cannot detect whether an addition or subtraction produces a carry. This makes multiple-precision arithmetic problematic. One way to solve that problem is to use a 2-byte score format where the lower byte only uses the lowest 7 bits, i.e. stores values ranging from -64 to +63, so that overflow can be detected from the 8th bit being unequal to the 7th bit. In the case of such an overflow 128 would have to be added or subtracted to get the lower byte back in range, and 1 would have to be subtracted or added to the upper byte to compensate that. To make that fast it can be done by lookup tables indexed by the low byte, one table to get the correction for the upper byte (0, 1 or -1), the other the corrected value of the lower byte. This would require two full-size tables. But this is not fatal, as 8 empty pages were still available.
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