Author: Guido
Date: 15:46:52 09/03/99
Go up one level in this thread
On September 03, 1999 at 12:53:23, Michel Langeveld wrote:
>If did a try to calculate the number of bytes of KQQKQQ and KQQKQP. I'm sure it
>can saved shorter than I tried. Please explain me where I made errors or missed
>something. Thx!
>
>Calculations of the number of bytes of KQQKQQ
>=============================================
>
>10 bytes for 1 king.
>
>+----+----+
>| | |
>| | |
>| | |
>| | |
>+----+----+
>| 1| |
>| 23| |
>| 456| |
>|7890| |
>+----+----+
>
>You can convert a random position with one king the king into this triangle.
>
>The Other king kan be on the folowing places:
>
>+----+----+
>| | |
>| | |
>| | |
>| | |
>+----+----+
>| 9| |
>| 99| |
>| 999| |
>|4666| |
>+----+----+
>
>4 = 60 other places for blackking
>6 = 58 other places for blackking
>9 = 55 other places for blackking
>
>So there are
>1 x 4 = 1 x 60 = 60
>3 x 6 = 3 x 58 = 174
>6 x 9 = 6 x 55 = 330+
> ---
> 564 positions for KK.
>
>KQK
>---
>For adding the next queen there are 62 pieces left.
>
>So you need for KQK 564 x 62 = 34.968 (for each color to move)
>
>Note: This number doesn't match with Namilov's number (It's bigger) of KQK can
>somebody tell me what's wrong??
>
>KQKQ
>----
>When adding the next queen you need:
>
>34.968 x 61 = 2.133.048 (for each color to move)
>
>This can be optimised more because if a king of one site is in check the king of
>the other site can't be in check...
>
>for example if you have the folowing position
>+----+----+
>|k | |
>| | |
>| | |
>| | |
>+----+----+
>| | |
>| | |
>| | |
>|q | K|
>+----+----+ white = lowcase) & black = upcase
>
>The folowing fields are valid for white to move(upcase).
>
>+----+----+
>|k | |
>| | |
>| | |
>| | |
>+----+----+
>| | |
>| | |
>| | |
>|q$$$|$$$K|
>+----+----+ white = lowcase) & black = upcase
>
>other field are not possible since black is else in check and can't move.
>
>KQQKQ
>-----
>
>For the endgame you need:
>2.133.048 x 60 = 127.982.880 bytes
>
>KQQKQQ
>------
>
>For this endgame you need:
>127.982.880 x 59 = 7.550.989.920 bytes for each color.
>So 15Gb will be enough for both colors for this endgame.
>
>KQQKQP
>======
>
>On the endgame a diffent calculation is needed because the pawn can only walk to
>one way. So If we begin with the king (maybe beginning with the piece with the
>most possibilities is better??).
>
>fields for the king (since we have a king we can't swap as much as without
>pawns).
>+----+----+
>| | |
>| | |
>| | |
>| | |
>+----+----+
>|1234| |
>|5678| |
>|9012| |
>|3456| |
>+----+----+ = 16 fields
>
>fiels for the other king =
>+----+----+
>| | |
>| | |
>| | |
>| | |
>+----+----+
>|6999| |
>|6999| |
>|6999| |
>|4666| |
>+----+----+ = 16 fields
>
>4 = 60 other places for blackking
>6 = 58 other places for blackking
>9 = 55 other places for blackking
>
>So there are
>1 x 4 = 1 x 60 = 60
>6 x 6 = 6 x 58 = 348
>9 x 9 = 9 x 55 = 495+
> ---
> 903 positions for KK (in a pawn endgame).
>
>fields for the pawn
>+----+----+
>|....|....|
>|1234|5678|
>|9012|3456|
>|7890|1234|
>+----+----+
>|5678|9012|
>|3456|7890|
>|1234|5678|
>|....|....| = 48 fields
>+----+----+
>
> KK P Q Q Q col.
>So we need 903 * 48 * 61 * 60 * 59 * 2 = 18.719.406.720 bytes
>
>So about 19Gb for KQQKQP
>
>Optimization
>============
>If you are only interested in win-draw-lose you might store can store 4
>positions in 1 byte. Then you only need (15Gb + 19Gb) / 4 = 8.5Gb. And I have a
>17Gb drive at home!!!
>
>We can also optimise these endgames more because the pawns are already advance
>to a certain rank!!!!!!!! I pawn can infact only move forward because if it
>hight a piece to the right the we convert to an endgame we already have!!!!!
>
>I've no idea how long it takes to generated this 2 endgames. I think if we
>optimize it for the Kasparov - World it can be much smaller and faster then if
>we generate them for general purpose.
>
>
>Kind regards,
>
>Michel Langeveld
>Email: rudolf@stad.dsl.nl
>Homepage: http://stad.dsl.nl/~rudolf
What does it mean the number of positions of KQQKQQ and KQQKQP?
IMO there are two possible answers:
1. The only positions allowed by the rules of the game, after eliminations of
simmetrically equivalent positions.
2. The number of positions in a tablebase, where the need of calculating an easy
index requests some positions more than necessary. I imagine that these
positions correspond to "broken position" in tbgen. Is it true?
I think that manual calculation of the number of positions as in case 1. would
be almost impossible for KQQKQQ and KQQKQP. Only a program can do this task
spending much time, checking symmetry and checks.
You start to calculate KK, but I'm sorry to say that IMHO you are wrong :-)
The number of positions should be 462, so evaluated:
1 x 4 = 1 x 33 = 33 white king in a1
3 x 6 = 3 x 58 = 174 white king in b1, c1, d1
3 x 9 = 3 x 55 = 165 white king in c2, d2, d3
3 x 9 = 3 x 30 = 90 white king in b2, c3, d4
----------
Total 462
When white king is on the diagonal a1-h8, position for the black king are
reduced by symmetry. This always happens when a piece is added to a symmetrical
disposition of the preceding pieces in respect to this diagonal. Therefore if
the two kings are in a1 and c3, also the positions of the first queen are
reduced and so on.
Values computed by my program are different, probably wrong, from those
obtained by Nalimov's tbgen, except for kpk and kppk, and I wrote to CCC
(Tablebases generation: help request - 8/30/99) asking help to solve this
problem, but perhaps who could answer was sleeping ... :-)
Guido
This page took 0 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.