[QUOTE=Christenson;258553]Hi SM88

I decided to do a poor man's enumeration of all the possible positions (really, configurations) of a pawn and 2 kings. I ended up listing out 43 special cases; thus Batalov's howl is quite appropriate. I have attached a PDF; I'll do the arithmetic after someone has checked it.
The decoder key is that only numbers that have a letter directly in front of them count; a is for the top level positions of the pawn; b is for the positions of the opposing king; c is for the positions of the friendly king, the one of the same color as the pawn.

Christenson (and thanks for running prime95!)[/QUOTE]
An exact enumeration of K+P vs K configurations seems indeed a worthwhile exercise and you've clearly put a lot of work in here. I would like to try and verify what you've done.

It is clear to me that you are placing the pawn first, next the opposing king and finally the friendly king. But - probably because I'm slower than most here - I'm having a tough time deciphering notation like "2 corners of 40 places" and "8 sides of 40 places" which you have used when placing the pawn. So I'm not really getting anywhere with the verification.

If others here find your notation clear and want to go ahead and verify your work, then let's leave it at that. But otherwise, could you perhaps modify the document with examples of what you mean by the verbose descriptions? I guess you're familiar with the standard notation for labelling the squares with a through h running left to right and 1 through 8 from White player to Black player: so a1 is the bottom left corner from White's point of view, for example. Naming the squares in this standard fashion would make it clearer. Thanks.:smile:

[QUOTE=Brian-E;258570]An exact enumeration of K+P vs K configurations seems indeed a worthwhile exercise and you've clearly put a lot of work in here. I would like to try and verify what you've done.

It is clear to me that you are placing the pawn first, next the opposing king and finally the friendly king. But - probably because I'm slower than most here - I'm having a tough time deciphering notation like "2 corners of 40 places" and "8 sides of 40 places" which you have used when placing the pawn. So I'm not really getting anywhere with the verification.

If others here find your notation clear and want to go ahead and verify your work, then let's leave it at that. But otherwise, could you perhaps modify the document with examples of what you mean by the verbose descriptions? I guess you're familiar with the standard notation for labelling the squares with a through h running left to right and 1 through 8 from White player to Black player: so a1 is the bottom left corner from White's point of view, for example. Naming the squares in this standard fashion would make it clearer. Thanks.:smile:[/QUOTE]

I was thinking of using the things found here: [url]http://en.wikipedia.org/wiki/Template:Chess_diagram[/url] on my wikipedia page or in this talk (it won't be as clear here though).

I think it would be worthwhile to enumerate the possibilities for a white and b black pawn with no more than c white captures and d black captures (that is, diagonal moves -- not reducing the number of pawns). That would go a long way toward a very precise upper bound on the number of total positions.

[QUOTE=Brian-E;258570]
<snip>
If others here find your notation clear and want to go ahead and verify your work, then let's leave it at that. But otherwise, could you perhaps modify the document with examples of what you mean by the verbose descriptions? I guess you're familiar with the standard notation for labelling the squares with a through h running left to right and 1 through 8 from White player to Black player: so a1 is the bottom left corner from White's point of view, for example. Naming the squares in this standard fashion would make it clearer. Thanks.:smile:[/QUOTE]

OK, I OWE A RE-POST. When I was first dividing things up, there were 5 rows by 8 columns (a3 through a7 through h7 through h3, assuming it's a white pawn) for 40 places, and the 2 corners of that space are a7 and h7. Hope this helps until I can get to the modification. Standard chess notation is a little unfamiliar to me, having come into vogue about the time I figured out chess was too much work for me to be really serious, so the reference definition above is helpful.

Incidentally, I'm by no means clear that this was the easiest ordering; it may be better to place two kings and decide where the pawns can and cannot go.

My upper bound gives: 94913952975460390436879153872778680534163376986304 or about 10^49.977, counting only the places for kings,queens, etc. in all squares (the pawns obivously can't be in all 64 squares and lots of them are unreachable in a chess game), so not regarding the en passant/castling/etc options for both sides. The code in pari-gp:

for white:
1 king
a pawns
b queens
c rooks
d knights
e bishops

For black use the same but uppercase letters. If there are a white pawns on the table, then you have got at most 8-a extra pieces on the table for queen/rook/knight/bishop.

[code]
v=vector(65,i,(i-1)!)
f(a,b,c,d,e,A,B,C,D,E)=v[65]/(v[a+1]*v[b+1]*v[c+1]*v[d+1]*v[e+1]*v[A+1]*v[B+1]*v[C+1]*v[D+1]*v[E+1]*v[63-a-b-c-d-e-A-B-C-D-E])

s=0;for(a=0,8,r1=8-a;for(b=0,1+r1,r2=r1-max(0,b-1);for(c=0,2+r2,r3=r2-max(0,c-2);for(d=0,2+r3,\
r4=r3-max(0,d-2);for(e=0,2+r4,print([a,b,c,d,e,s,log(s+1)/log(10)]);\
for(A=0,8,R1=8-A;for(B=0,1+R1,R2=R1-max(0,B-1);for(C=0,2+R2,R3=R2-max(0,C-2);for(D=0,2+R3,\
R4=R3-max(0,D-2);for(E=0,2+R4,s+=f(a,b,c,d,e,A,B,C,D,E)))))))))));s
[/code]

[QUOTE=R. Gerbicz;258658]My upper bound gives: 94913952975460390436879153872778680534163376986304 or about 10^49.977,
<snip>
[/QUOTE]
That's in line with internet-published numbers mentioned earlier in this thread as a provable upper bound. Now you ignored castling and en passant, how did you deal with promotion of pawns?

Now, back to the matter at immediate hand. Question 2 was: How many positions are there with 3 pieces on the board, exactly. Question 2b is: If there are two kings and a pawn, how many legal positions?

I've attached my cleaned-up, probably-suboptimal, enumeration, as promised.

[QUOTE=Christenson;258669]I've attached my cleaned-up, probably-suboptimal, enumeration, as promised.[/QUOTE]
Loads of effort here, very impressive!

I've delved into just a small part of it, found what I think are 2 errors in that, and left the rest because while the first error is merely one of failing to include a position of the opposing king, the second error might indicate that you've overlooked a subtlety which you might have repeated elsewhere in the document. For this last reason it might be over to you again to go back through your colossal work once more. (Aaaagh!)

(1)
Section I), white pawn on a7 (or h7). I don't think you have counted the instance of the opposing king being on b8. The numbers in A) to F) do total 63, but that's because I think F) should be only 33, not 34. In F) I assume you count c7-g7 in addition to the other squares you list.

(2)
More technical error: in section III) A) I reckon only 59 possible places for friendly king, not 60. I suspect you have erroneously counted b6 as a legal square for the white king. Can you see why it isn't legal? I suspect this error may be repeated throughout the document, because similarly in precious section II) B) you have lumped b7 with b5 and b6 for the opposing king, but in the case of b7 there are only 54 places for the friendly king, not 55, because it cannot legally be on a5.


What a hugely difficult problem this is, even just for K+P vs K positions!


Edit: I do appreciate you have already taken account of the "technical error" in that you handled the positions with the pawn on the second rank separately since the black king cannot then be in check. So it's only a question of remembering everything in all the different situations!

[QUOTE=Christenson;258669]That's in line with internet-published numbers mentioned earlier in this thread as a provable upper bound. Now you ignored castling and en passant, how did you deal with promotion of pawns?
[/QUOTE]

In the above code the promotion of pawns is considered: if you have "a" white pawns on the table, then there were at most 8-a promotions, and this results, that you can distribute these, so there can be at most 9-a queens, 10-a rooks, 10-a bishops, 10-a knights on the table, but in such a way that the number of extra pieces are at most 8-a. (and at most 8-A black promotion of pawns).

An updated estimation:
[code]

v=vector(65,i,(i-1)!);
g(a,b,c,d,e,A,B,C,D,E)=v[49]/(v[a+1]*v[A+1]*v[49-a-A])*v[65-a-A]/(v[b+1]*v[c+1]*v[d+1]*v[e+1]*v[B+1]*v[C+1]*v[D+1]*v[E+1]*v[63-a-b-c-d-e-A-B-C-D-E])

s=0;for(a=0,8,r1=8-a;for(b=0,1+r1,r2=r1-max(0,b-1);for(c=0,2+r2,r3=r2-max(0,c-2);for(d=0,2+r3,\
r4=r3-max(0,d-2);for(e=0,2+r4,print([a,b,c,d,e,s,log(s+1)/log(10)]);\
for(A=0,8,R1=8-A;for(B=0,1+R1,R2=R1-max(0,B-1);for(C=0,2+R2,R3=R2-max(0,C-2);for(D=0,2+R3,\
R4=R3-max(0,D-2);for(E=0,2+R4,s+=g(a,b,c,d,e,A,B,C,D,E)))))))))));s

gives: 23937533792747905898433845980097921846050276105440
[/code]
This is interesting, because it is exactly the same what Will Entriken found, see: [URL="http://homepages.cwi.nl/~tromp/chess/chess.html"]http://homepages.cwi.nl/~tromp/chess/chess.html[/URL].

Another estimation, if we consider also en passants and castling (and pawn promotions), and which side is to move then my upper bound:
[code]

ctpawns(a,A)=sum(a1=0,a,binomial(8,a1)*(1+A)*(48-a1)!/(a-a1)!/A!/(48-a-A)!)
P=matrix(9,9,i,j,ctpawns(i-1,j-1));

ctrooks(c,fr)=(fr>=c+1)*((fr-1)*binomial(fr-1,c)+(fr>=3||c==0)*binomial(fr-3,c)+(c>=2)*binomial(fr-3,c-2)*2^2+(c>=1)*2*2*binomial(fr-3,c-1))
R=matrix(11,65,i,j,ctrooks(i-1,j-1));

v=vector(65,i,(i-1)!);

h(a,b,c,d,e,A,B,C,D,E)=2*P[a+1,A+1]*R[c+1,65-a-A]*R[C+1,64-a-A-c]*v[63-a-A-c-C]/(v[b+1]*v[d+1]*v[e+1]*v[B+1]*v[D+1]*v[E+1]*v[63-a-b-c-d-e-A-B-C-D-E])

s=0;for(a=0,8,r1=8-a;for(b=0,1+r1,r2=r1-max(0,b-1);for(c=0,2+r2,r3=r2-max(0,c-2);for(d=0,2+r3,\
r4=r3-max(0,d-2);for(e=0,2+r4,print([a,b,c,d,e,s,log(s+1)/log(10)]);\
for(A=0,8,R1=8-A;for(B=0,1+R1,R2=R1-max(0,B-1);for(C=0,2+R2,R3=R2-max(0,C-2);for(D=0,2+R3,\
R4=R3-max(0,D-2);for(E=0,2+R4,s+=h(a,b,c,d,e,A,B,C,D,E)))))))))));s

gives: 202212266087257078277744885249689599696415528645202
[/code]

I don't understand the John's counting method that resulted a factor of ~4000 times smaller number of positions. For me it seems a huge gap.

[QUOTE=Brian-E;258680]Loads of effort here, very impressive!

I've delved into just a small part of it, found what I think are 2 errors in that,
<snip>

What a hugely difficult problem this is, even just for K+P vs K positions!

Edit: I do appreciate you have already taken account of the "technical error" in that you handled the positions with the pawn on the second rank separately since the black king cannot then be in check. So it's only a question of remembering everything in all the different situations![/QUOTE]

I'm not feeling well enough today to address these points, but it's precisely why I didn't actually do the arithmetic until someone had looked it over. As I said, there are 43 cases, 43x2 opportunities for mistakes in a way that humans are generally GOOD at making mistakes.

I'm thinking as a check on whatever we come up with, we place the two kings first and see what happens to the pawn. This will be our double-check.

Does anyone have a handle on how to count the number of K + Q + Q + K positions that are illegal? For example, I'm pretty sure that black K on a1, white Q on b1, black Q on c1, and white K on d1 is illegal, being impossible to move into. So should black K on a1, white rook on a8, white K on h8, and white rook on h1, for the same reason.

Brian:
Thank you, both of your points are on target.
In the first section, I screwed up the coordinate system, which I was in considerably more practice at the end of the document than the beginning. I have corrected the coordinates listed in the document.

In the second point, my document considers that if the pawn is white, having the white pawn attack the black king and the white king directly behind the white pawn is legal. I'll leave it to SM88 to prove that these positions are unreachable. To make it cncrete, we are saying that with the white pawn on b7, the black king on a8, and the white king on b6 is unreachable and therefore are not legal chess positions. [I didn't think I was going to have to deal with this kind of problem until we got to 4 pieces on the board; it also means that we need to check K + other piece + K for illegal positions]

As to what to do about it, I *could* go through and correct each case, or we can simply note that there are 5 rows for the pawn where this could be a problem, multiplied by 14 combinations of pawn attacking the opposing king on the next row, multiplied by exactly one position for each of these where the friendly king cannot be, for 70 positions to subtract from the origianal total.

However, this analysis begs the question: Are there others? I need to think a bit; examples like yours are appreciated!

[QUOTE=Christenson;258748]To make it cncrete, we are saying that with the white pawn on b7, the black king on a8, and the white king on b6 is unreachable and therefore are not legal chess positions.[/QUOTE]

If white pawn on c6 captures black pawn on b7?