Author: Dieter Buerssner
Date: 12:34:18 11/12/01
My estimation for the memory consumption of 4-men win/draw/lose tables. I hope, I have not done any major errors ... Two differnet sort of such bases would be needed. Where only one side can win, one can store 8 results in one byte. When both sides can win, one can store 5 results in one byte (3^5 = 243 < 256). In the estimation, I assume a rather unsophisticated indexing scheme. 1. For pawnless tables, restrict the K of the side to move onto the triangle a1-d1-d4, which is 8 squares. All other pieces may occupy any square. So this makes 10*64^3 positions. 2 cases, both sides can win a); or only one side can win b). 1a) 10 * 64^3 / 5 = 512 kB 1b) 10 * 64^3 / 8 = 320 kB 2. Tables with one pawn. Restrict the K of the side to move on a-d: 32 squares. The pawn is (of course) restricted to 48 squares. The other pieces can occupy any square. 2a) 32 * 48 * 64^2 / 5 = 1229 kB 2b) 32 * 48 * 64^2 / 8 = 768 kB 3. kpkp. K of side to move: a-d. 48 for both pawns 3) 32 * 48^2 * 64 / 5 = 922 kB 4. kppk. Similar. Worst case is with ep. For this reason, one more "square" could be used for the pawn. Both pawn indices the same could mean, that ep capture from left to right is possible, while the extra square could mean ep capture from right to left is possible. No doubt, more clever tricks could be found. 4) 32 * 48 * 49 * 64 / 5 = 941 kB So, for all the tables we get: kpkp: 3 knkp: 2a knkn: 1a kbkp: 2a kbkn: 1a kbkb: 1a krkp: 2a krkn: 1a krkb: 1a krkr: 1a kqkp: 2a kqkn: 1a kqkb: 1a kqkr: 1a kqkq: 1a kppk: 4 knpk: 2b knnk: 1b kbpk: 2b kbnk: 1b kbbk: 1b krpk: 2b krnk: 1b krbk: 1b krrk: 1b kqpk: 2b kqnk: 1b kqbk: 1b kqrk: 1b kqqk: 1b 10 * 512 + 4 * 1229 + 10 * 320 + 4 * 768 + 922 + 941 = 18171 kB For both sides to move 36342 kB or roughly 35.5 MB would be needed. In the above, I did not check, if some tables can be omitted. For practical games, certainly tables like knnk are not needed, because a mate cannot be achieved, but there are some mate positions. Also I did not check if there are mate postions for the weaker side in tables like krkb and krkn. A slightly more sophisticated scheme would save more than 10 percent. For case 1, there are only 462 legal KK positions, that can be enumerated. My simple scheme uses 640 positions for this. For case 2 - 4, there are 1806 legal KK positions, compared to 32*64 = 2048 in the more primitive scheme. Also, I did not take into account already occupied squares. Regards, Dieter
This page took 0.01 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.