7

My question concerns the total material available on the chess board (black+white pieces). At the very beginning of a game, there are 2 Kings, 2 Queens, 4 Rooks, 4 Bishops, 4 Knights and 16 pawns. These can be represented by an array (2, 2, 4, 4, 4, 16). As the game progresses, the total amount of material will change, thus the array will change. My question is as follows. Looking at all theoretically possible games played from the initial position, how many unique arrays are possible to reach? The fact that a pawn can be promoted to any light or heavy piece makes the problem even more tricky!

Initial Board

16 Pawns
 4 Rooks
 4 Bishops
 4 Knights
 2 Queens
 2 Kings

After a pawn capture

15 Pawns
 4 Rooks
 4 Bishops
 4 Knights
 2 Queens
 2 Kings

Only kings left

 0 Pawns
 0 Rooks
 0 Bishops
 0 Knights
 0 Queens
 2 Kings

But it get more complex when you include pawn promotion (to any piece excluding pawn and king).

So what is the total number of combinations?

I've listed 3 combinations above. Here a 6 more

 P  R  N  B  Q  K
32  4  4  4  2  2  Initial Position and remains the same until a capture
32  3  4  4  2  2  First capture frequency combinations.  
32  4  3  4  2  2
32  4  4  3  2  2
32  4  4  4  1  2
31  4  4  4  2  2  Pawn 
etc
etc
0  0  0  0  0  2  Only Kings

It get tricky at pawn promotion cos each of the 16 pawns can turn in one of 4 pieces (R B N Q). Which is why I curious to know the total number of (unique piece frequencies)

Laska
  • 10,710
  • 4
  • 37
  • 70
Adam Speight
  • 189
  • 1
  • 4

3 Answers3

4

It's :
numberOfPawnsPieces(=17) * numberOfRooksPieces(=5) * numberOfBishopsPieces(=5) * numberOfKnightsPieces(=5) * numberOfQueensPieces(=3) * numberOfKingsPieces(=1)
= 6375

I added one to each number of same piece in case there is no one of its kind(for queens for example, there may be two queens, one queen, or none), except for Kings where there always must be 2 kings on the board, so the number of combinations for kings number is only 1.

**

EDIT : In cas there is promotions of pawns

**
My idea to tackle this is to separate all possible cases, i.e. when there is promotion of 1 pawn, promotion of 2 pawns,...,promotion of 8 pawns. ( 8 pawns is the maximum number of possible promotions )
Generally speaking, when x pawns are promoted, we will proceed same as above, but the number of pawns will be in each case (16-x), plus an other group of 4 * x possibly created pieces. Finally we will sum all over the cases :

                17*5*5*5*3*1 + SUM[x=1-->16,(16-x+1)*5*5*5*3*(4*x)] = **1 230 375**

This is approximate, I may have forgotten some cases, or added some positions that are just impossible to happen in a chess game,...etc.

mounaim
  • 452
  • 2
  • 13
  • 2
    This is the correct number if you don't include pawn promotion. – Dag Oskar Madsen Jan 27 '14 at 12:38
  • @DagOskarMadsen would you please check my edit for the answer ? – mounaim Jan 28 '14 at 14:20
  • @Adam Speight check my edit for the answer :) – mounaim Jan 28 '14 at 14:21
  • Actually there can be 16 promotions: http://chess.stackexchange.com/questions/4128/shortest-game-with-18-queens, but in a legal game then some of the other pieces must have bee captured on the way. If you only consider legal games, then this becomes a very hard chess question rather than a mathematical question. – Dag Oskar Madsen Jan 28 '14 at 14:26
  • Thanks @DagOskarMadsen for this beautiful game with 16 queens, I thought this was just impossible ! – mounaim Jan 28 '14 at 14:48
  • Your answer now is much too large since you are counting the same piece distributions many times. Your answer would have been correct if promoted pieces were to be considered different from the starting pieces. For instance you are counting two kings and a queen as different from two kings and a promoted queen. – Dag Oskar Madsen Jan 28 '14 at 15:15
  • you're right @DagOskarMadsen, my answer may involve duplicated endgames, I will try to work on this :) – mounaim Jan 28 '14 at 15:55
2

Initialy I posted that only 8 promotions for both sides are posible because pawns are oposed in the same file and to promote one have to be taken.

Edited:

I think that for each promotion one pawn or a piece shoud be taken. Because pawns are in front of each other ,blacks and whites ,to promote one of both have to move to the side(take another piece or pawn) or be taken. then I recalculated the final result to 80094 diferent legal piece combinations. I created this script to show all (i modified thanks to the comments of lodebari)

(function (pieceset) {
    'use strict';
    var n = 0,
        cc = function cc(arr) {
            var temparr=arr.slice(0);
            while (temparr[0]>=0) {
                while (temparr[1]>=0) {
                    while (temparr[2]>=0) {
                        while (temparr[3]>=0) {
                            while (temparr[4]>=0) {
                                var maxp = 0;
                                var nump = temparr[1]+temparr[2]+temparr[3]+temparr[4]; 
                                if (temparr[1]>4) maxp+=(temparr[1]-4);
                                if (temparr[2]>4) maxp+=(temparr[2]-4);
                                if (temparr[3]>4) maxp+=(temparr[3]-4);
                                if (temparr[4]>2) maxp+=(temparr[4]-2);
                                nump = nump - maxp;
                                if ((maxp+temparr[0]<=16)&&((nump+temparr[0]+(maxp*2))<=30)) {
                                    n++;
                                    console.log(n,"->",temparr);
                                }
                                temparr[4]=temparr[4]-1;
                            }
                            temparr[4]=arr[4];
                            temparr[3]=temparr[3]-1;
                        }
                        temparr[3]=arr[3];
                        temparr[2]=temparr[2]-1;
                    }
                    temparr[2]=arr[2];
                    temparr[1]=temparr[1]-1;
                }
                temparr[1]=arr[1];
                temparr[0]=temparr[0]-1;
            }
            return 0;
        };
    cc(pieceset);
}([16,20,20,20,18,2]));

When you run it it print lines like this:

1 '->' [ 16, 4, 4, 4, 2, 2 ]

the fist number its the combination number followed by Pawns,Rooks,Knights,Bishops,Queens,Kings. The fist line corresponds the fist position with full board, and the last with the two kings alone.

You can try here : https://repl.it/xlO/4

girarvi
  • 21
  • 3
  • 1
    Actually, for a pawn to able to promote it is necessary that the pawn in front moves aside (taking a piece or another pawn) or is taken. – lodebari Oct 15 '15 at 06:02
2

I know that the upper limit can not be greater than 2304000 Which is the answer to the following

16 (Pawns) * 20 (Rooks) * 20 (Knights) * 20 (Bishops) * 18 (Queens)

But not all of those are possible, so doing a quick programming

 c:= 0
 p:= 0 .. 16
 r:= 0 .. 20
 b:= 0 .. 20
 n:= 0 .. 20
 q:= 0 .. 18
 if Sum( p, r, b, n, q, 2) <= 32 then c+=1

Calculates c to be 305090 combinations. (218 < c < 219)

If I just focus on end games (no pawns) I calculate c to be 3060 211 < c < 212

Is my algorithm producing the correct results?

Adam Speight
  • 189
  • 1
  • 4
  • There are some other restrictions. If there are 20 rooks, then there cannot be more than 4 knights, for instance. – Dag Oskar Madsen Jan 30 '14 at 02:54
  • @DagOskarMadsen Good point, which suggest the value is lower than these upper bounds. – Adam Speight Jan 30 '14 at 02:59
  • Adding the constraint __Sum(r,n,b,a)<= (20-p)__ reduces the combinations to **53068** and **3060** – Adam Speight Jan 30 '14 at 03:14
  • The question now says "...all theoretically possible games played from the initial position ....". If you have a large number of promotions, then there must have been several captures on the way. It is going to be very hard to calculate the exact answer, maybe an upper bound is the most we can hope for. – Dag Oskar Madsen Jan 30 '14 at 09:16
  • I think the constraint should be Sum(r,n,b,q)<= (30-p) – Dag Oskar Madsen Jan 30 '14 at 09:21
  • No, it's more subtle than in my previous comment. The constraint is max(r,4)+max(n,4)+max(b,4)+max(q,2)<=(30-p) – Dag Oskar Madsen Jan 30 '14 at 15:36
  • @DagOskarMadsen I suspect that constraint will produce the wrong value. Then can be less than 4 rooks on the board. – Adam Speight Jan 31 '14 at 17:36
  • Sure. There are 16 pawns that can promote, so from promotions we get max(r-4,0)+max(n-4,0)+max(b-4,0)+max(q-2,0)<=(16-p). This is equivalent to what I wrote. Trust me, I am a mathematician :) – Dag Oskar Madsen Jan 31 '14 at 17:43
  • @DagOskarMadsen I ain't. So could you explain (like I am 5) how you came that expression.eg max(q-2,0)? It's possible to have all the 16 pawns promoted to queens and still have the original 2 queen also. Which is 18 queens. Me Confused. :-( – Adam Speight Jan 31 '14 at 17:53
  • If you have 18 queens, then 16 of them must have been promoted. max(q-2,0)=max(16,0)=16. Similarly, max(r-4,0) counts the number of rooks that *must* have been promoted. For instance if there are 6 rooks, then at least max(r-4,0)=max(2,0)=2 of them must have been promoted. – Dag Oskar Madsen Jan 31 '14 at 17:57
  • The formula then counts on the number of pieces on the board that *must* be promoted pieces and compares with the number of missing pawns. – Dag Oskar Madsen Jan 31 '14 at 18:01
  • So I calculate the answers to be **164603** and **32275** (end game). @DagOskarMadsen Thank you for explaining it to me. Less confused :-) – Adam Speight Jan 31 '14 at 19:29
  • So for the number of different types of pieces on the board. The number of unique piece frequencies are:- **1:= 1** , **2:= 94** , **3:= 2168** , **4:= 19296** , **5:= 71628** ,**6:= 91416** – Adam Speight Jan 31 '14 at 20:07
  • @DagOskarMadsen Here is a link to a zip containing a csv of all the unique piece frequencies. http://sdrv.ms/1beLLxG – Adam Speight Jan 31 '14 at 20:47
  • Impossible. Some of those pawns have to take other things to clear the way for them to be promoted or they need to be taken for promotions to happen. – yobamamama Dec 26 '19 at 17:32