Home 
Search 
Today's Posts 
#1




Positions krkendgame wo symmetry
I have thought about how many (really) different positions there is in a
say K+R vs K endgame. It is okay to include the inpossible (king next to king), but a symmetrical position should only be counted once. I.e. ka1, Rb2, Kc2 = ka1, Rb2, Kb3 and also in the other corners. Jonas 
#2




Positions krkendgame wo symmetry
Jonas Forsslund wrote:
I have thought about how many (really) different positions there is in a say K+R vs K endgame. It is okay to include the inpossible (king next to king), but a symmetrical position should only be counted once. I.e. ka1, Rb2, Kc2 = ka1, Rb2, Kb3 and also in the other corners. For symmetry's sake, we may assume that it is White who has the rook. White's king could be on one of 64 squares, which leaves 63 for his rook and 62 for the Black king. So, that's 64x63x62 basic positions. Now we need to take symmetry into account. The board has four mirror symmetries (the line between the d and e files, the line between the fourth and fifth tanks and the two long diagonals) and rotating the board by ninety degrees is also a symmetry so there are four rotational symmetries. The total, then, is 64 x 63 x 62  = 15,624. 4 x 4 That's physical arrangements of the pieces on the board, including illegal positions. If you're ultrapedantic and want to include information about whether the player with the rook can castle, add two (one extra for Ra1 Ke1, White can castle long, the other for Rh1 Ke1, White can castle short) If you want to count positions as different if the other player has the move, multiply by two. Actually legal positions will be a little bit less but rather harder to count. Dave.  David Richerby Incredible Smokes (TM): it's like www.chiark.greenend.org.uk/~davidr/ a pack of cigarettes but it'll blow your mind! 
#3




Positions krkendgame wo symmetry
"David Richerby" wrote in message ... Jonas Forsslund wrote: I have thought about how many (really) different positions there is in a say K+R vs K endgame. It is okay to include the inpossible (king next to king), but a symmetrical position should only be counted once. I.e. ka1, Rb2, Kc2 = ka1, Rb2, Kb3 and also in the other corners. For symmetry's sake, we may assume that it is White who has the rook. White's king could be on one of 64 squares, which leaves 63 for his rook and 62 for the Black king. So, that's 64x63x62 basic positions. Now we need to take symmetry into account. The board has four mirror symmetries (the line between the d and e files, the line between the fourth and fifth tanks and the two long diagonals) and rotating the board by ninety degrees is also a symmetry so there are four rotational symmetries. The total, then, is 64 x 63 x 62  = 15,624. 4 x 4 According to your formula you can restrict lone king to 64  = 4 squares 4 x 4 using mirroring and rotations. I somewhat doubt that :) Thanks, Eugene That's physical arrangements of the pieces on the board, including illegal positions. If you're ultrapedantic and want to include information about whether the player with the rook can castle, add two (one extra for Ra1 Ke1, White can castle long, the other for Rh1 Ke1, White can castle short) If you want to count positions as different if the other player has the move, multiply by two. Actually legal positions will be a little bit less but rather harder to count. Dave.  David Richerby Incredible Smokes (TM): it's like www.chiark.greenend.org.uk/~davidr/ a pack of cigarettes but it'll blow your mind! 
#4




Positions krkendgame wo symmetry
In article ,
"Eugene Nalimov" writes: "David Richerby" wrote in message ... 64 x 63 x 62  = 15,624. 4 x 4 According to your formula you can restrict lone king to 64  = 4 squares 4 x 4 Let's see where the problem is: Start with the full board. Mirroring along the vertical between d and e file halves the positions. 32 left. Mirroring along the horizontal between 4 and 5 halves again. 16 left. (e.g., the a1a4d1d4 square). Mirroring along the diagonal projects the four fields a1d4 onto themselves, reducing noting. The other 12 fields boil down to 6, leaving a total of 10. There is no other symmetry operation, since the long diagonal a8h1 is not independent: it can be generated from combinations of the already used operations. Thus you can restrict the king to 10 fields, a1d1d4 triangle. BTW, if I'm not mistaken Eugene's indexing scheme actually exploits the fact that kingnexttoking is not possible, thus reducing the 63 somewhat. (More precise, this should leave you with only one factor for both kings, and it's somewhat smaller than 10x63). Werner 
#5




Positions krkendgame wo symmetry
I am not convinced that you can reduce the positions only by looking
at the mirrors. (That is, for more than one piece) For example, there is eight positions of (ka1, Rb2, Kc2) (= ka1, Rb2, Kb3 and also in the other corners.) but only four of (ka1,Rb2,Kc3). I belive this must be taking into count. The reason I became curious is that I am reading discrete mathematics right now at university. A similar problem we learned about (In book "Biggs, Norman: Discrete Mathematics" SE) is "How many identity cards of size 3x3 with two holes can we make, so that they can be rotaded and fliped over"? The answere is 8. The theorem used is: Number of orbits of G on X is ___ _1_ \  F(g) G /__ g{G Or, the number of orbits is equal to the average size of the sets F(g) We have 8 symmetries I belive, as in the cardproblem: identity (card: 9 over 2, chess 64*63*62) clockwise rotation 90' (card 0, chess ?) clockwise rotation 180' (card 4, chess ?) clockwise rotation 270' (card 0, chess ?) Reflection diagonal 1 (card 6, chess ?) Reflection diagonal 2 (card 6, chess ?) Reflection in perpendicular bisector a1a8 (card 6, chess ?) Reflection of perpendicular bisector a1h1 (card 6, chess ?) I do belive this is a way to count, or is it too hard to figure out those numbers? Werner Mühlpfordt wrote: Let's see where the problem is: Start with the full board. Mirroring along the vertical between d and e file halves the positions. 32 left. Mirroring along the horizontal between 4 and 5 halves again. 16 left. (e.g., the a1a4d1d4 square). Mirroring along the diagonal projects the four fields a1d4 onto themselves, reducing noting. The other 12 fields boil down to 6, leaving a total of 10. There is no other symmetry operation, since the long diagonal a8h1 is not independent: it can be generated from combinations of the already used operations. Thus you can restrict the king to 10 fields, a1d1d4 triangle. Yes I agree, there is 10 fields for one king. Is it possible to use this method to extend it with another piece? If so, how? /Jonas Forsslund Msc Comp. Sci. Student, Sweden 
#6




Positions krkendgame wo symmetry
In article ,
Jonas Forsslund writes: I am not convinced that you can reduce the positions only by looking at the mirrors. (That is, for more than one piece) There are several ways ("representations") to combine symmetry operations to yield the same reduction. Some of the include rotations. But you will always end up with the same twodimensional point symmetry group. It has 8fold symmetry for the "normal" case, and 4fold symmetry for diagonal fields (for a really central field, it would be only 1  but there is no d..e 4..5 ;) Thus: 16 diagonal fields divided by 4 yields 4, 48 normal fields divided by 8 yields 6. Same result. For example, there is eight positions of (ka1, Rb2, Kc2) (= ka1, Rb2, Kb3 and also in the other corners.) but only four of (ka1,Rb2,Kc3). I belive this must be taking into count. You can pick any piece  but I believe for an indexing scheme you must pick the same all the time. Yes I agree, there is 10 fields for one king. Is it possible to use this method to extend it with another piece? If so, how? You could apply further symmetry in case of an ondiagonal "first" piece. I.e., with white King on a1, black king on h7 or g8 is the same position. Put the white king on a2, however, bKh7/g8 are different. This can be extended: with wKb2, bKd4, the positions with Ra8 and Rh1 are identical. And so on. Werner 
#7




Positions krkendgame wo symmetry

#9




Positions krkendgame wo symmetry
Thanks alot, I got the exact same numbers by calculating like this:
KK is 3612 positions (identity) on the two diagonal reflection there is 42. so there is 1/8(3612+42+42) = 462 KK as Diepeveen mentioned. if we add a rook, the identity is 3612*62, and diagonal reflection is 42*6. so we have 1/8(3612*62+42*6+42*6) = 28056 Nice :) Benjamin Jordan wrote: (Werner Mühlpfordt) wrote in message ... In article , Jonas Forsslund writes: There are several ways ("representations") to combine symmetry operations to yield the same reduction. Some of the include rotations. But you will always end up with the same twodimensional point symmetry group. It has 8fold symmetry for the "normal" case, and 4fold symmetry for diagonal fields Sounds good to me. So just looking at arrangements (white with the rook), there are 64*63*62 total, with 16*7*6 of them along diagonals right? Diag: WK*BK*WR 16* 7* 6 = 672 (WK*BK*WR  diag) / 8 + diag / 4 (64*63*62  672) / 8 + 672 / 4 = 31,332 To eliminate kingbyking positions, there are 4 corners where the WK takes away 4 squares, 24 edge squares where he takes 6, and on the remaining 36 squares he takes 9. On the diagonals, he has 4 corners where he takes away 2, and 12 squares where he takes away 3: Diag: 4*(82)*6 + 12*(83)*6 = 504 positions with only 4fold symmetry (4*(644)*62 + 24*(646)*62 + 36*(649)*62  504) / 8 + 504 / 4 = 28,056 Assuming that the computer played the game up to the position, it shouldn't need to consider draw by repetition or 50move rule, but there would be the two additional positions where white has castling rights (but would it matter?). So I get 28,058 unique positions with Black to move. White to move is a lot more complicated because any position where Black is in check by the Rook would be illegal. Benjamin Jordan 
#10




Positions krkendgame wo symmetry
Hi
Is it for implemention purposes you stay with 28644 instead of 28056? (28058 with oo and ooo) The winning is not much, just curious. For KNNK i would say we have id = 3612*(62*61)/2 = 6830292 diagonal reflection = 52*(6*5)/2 + 42*28 = 1806 1/8( 6830292+1806+1806) = 854238 positions. Jonas Forsslund Vincent Diepeveen wrote: Hi, without pawns there is 462 king  king positions. you can also mirror on the diagonal i don't reduce for checks in diep. egtb command (or help): list NR NAME KEY #ENTRIES EXISTS (disk,ram) 1 kpk 00008000 84012     2 knk 00040000 28644     3 kbk 00200000 28644     4 krk 01000000 28644     5 kqk 08000000 28644     6 kppk 00010000 1912372     7 knpk 00048000 5124732     8 knnk 00080000 873642     9 kbpk 00208000 5124732     10 kbnk 00240000 1747284     11 kbbk 00400000 873642     12 krpk 01008000 5124732     13 krnk 01040000 1747284     That's why i have 28644 positions for KRK. so if you reduce with symmetry and such then it's pretty small egtb. 62 * 462 = 28644. 
Reply 
Thread Tools  
Display Modes  


Similar Threads  
Thread  Forum  
Bishops are definitely better than knights  rec.games.chess.analysis (Chess Analysis)  
Who was better in this endgame?  rec.games.chess.analysis (Chess Analysis)  
Rook and pawn endgame  analysis requested  rec.games.chess.analysis (Chess Analysis)  
My first endgame study (intermediate)  rec.games.chess.analysis (Chess Analysis) 