possible positions

[bentonharper3]

I read recently that the game of checkers had been solved, that is, computers working for over thirteen years had exhausted the 5x10 to the 20th possible positions that can arrise and a computer with this info downloaded would never lose and win against any error. This approach cannot currently be applied to chess, with its 10 to the fortieth possible positions (which would take approx. 3,000 years). Can anyone tell me how many possible positions can arrise in a game of Chinese chess? If possible can you give me a source to use in my research. Thanks.

[hgm]

According to http://en.wikipedia.org/wiki/Game-tree_complexity the state-space comlplexity would be 10^48.

Actually for Xiangqi the exact number is reasonably easy to calculate (compared to FIDE Chess) as in-check positions are not necessarily illegal (in Xiangqi one has to capture the King), and there are no nasty correlations between reachable Pawn structures and number of pieces that have to be captured.

So it would just be a matter of calculating the number of positions for one side for each posible number of promoted Pawns and number of present territory-bound pieces (King, Mandarins, Ministers and unpromoted Pawns), and combine these for te two sides keeping track only of the toatal number of pieces. (The number of positions for the promoted Pawns follows from the number of territory-bound pieces of the opponent.)

After that it is just a matter of adding the pieces that can go anywhere, for which the number of possiblities only depends on the number of pieces already present.

Note that the territory-bound pieces do not 'collide' too often, as Pawns can never reach their own Palace, while Ministers can only occupy 2 Pawn-accessible locations, and 1 location in the palace only accessible by the King (but not by Mandarins).

As a rough estimate count the number of positions with all pieces present and all Pawns promoted:

5*4/2 = 10 Mandarin positions in Palace
times 7 King positions = 70 Palace conformations
7*6/2 = 21 positions of two Ministers (ignoring collisions with King)
Total territory-bound conformations for one side = 21*70 = 1470 (5 pieces).

Five promoted Pawns on half-board containing the 5 territory-bound pieces:
40*39*38*37*36/(5*4*3*2) = 40!/(35!*5!) = Binomial(40,5) = 658008

The 6 pairs of other pieces that can be anywhere (Rook, Knights, Canons) on the remaining 70 squares we will have (70!/58!)/2^6 = 10^19.9.

So in total we have (1470*658008)^2 * 10^19.9 = 10^37.87.

Seems to me the numbers in the Wikipedia must be gross over-estimates, unless they also take the entire game history as part of the state spave (for the purpose of repeats). Of course I did not count any positions with unpromoted Pawns of captured pieces in above estimate, but an unpromoted Pawn has only 10 possible positions in stead of 40, and even with a missing Mandarin the number of Palace conformations reduces by half. So I can imagine being off a factor 2 here and there, but hardly 10^10...

[Uri Blass]

According to http://en.wikipedia.org/wiki/Game-tree_complexity the state-space comlplexity would be 10^48.

Actually for Xiangqi the exact number is reasonably easy to calculate (compared to FIDE Chess) as in-check positions are not necessarily illegal (in Xiangqi one has to capture the King), and there are no nasty correlations between reachable Pawn structures and number of pieces that have to be captured.

So it would just be a matter of calculating the number of positions for one side for each posible number of promoted Pawns and number of present territory-bound pieces (King, Mandarins, Ministers and unpromoted Pawns), and combine these for te two sides keeping track only of the toatal number of pieces. (The number of positions for the promoted Pawns follows from the number of territory-bound pieces of the opponent.)

After that it is just a matter of adding the pieces that can go anywhere, for which the number of possiblities only depends on the number of pieces already present.

Note that the territory-bound pieces do not 'collide' too often, as Pawns can never reach their own Palace, while Ministers can only occupy 2 Pawn-accessible locations, and 1 location in the palace only accessible by the King (but not by Mandarins).

As a rough estimate count the number of positions with all pieces present and all Pawns promoted:

5*4/2 = 10 Mandarin positions in Palace
times 7 King positions = 70 Palace conformations
7*6/2 = 21 positions of two Ministers (ignoring collisions with King)
Total territory-bound conformations for one side = 21*70 = 1470 (5 pieces).

Five promoted Pawns on half-board containing the 5 territory-bound pieces:
40*39*38*37*36/(5*4*3*2) = 40!/(35!*5!) = Binomial(40,5) = 658008

The 6 pairs of other pieces that can be anywhere (Rook, Knights, Canons) on the remaining 70 squares we will have (70!/58!)/2^6 = 10^19.9.

So in total we have (1470*658008)^2 * 10^19.9 = 10^37.87.

Seems to me the numbers in the Wikipedia must be gross over-estimates, unless they also take the entire game history as part of the state spave (for the purpose of repeats). Of course I did not count any positions with unpromoted Pawns of captured pieces in above estimate, but an unpromoted Pawn has only 10 possible positions in stead of 40, and even with a missing Mandarin the number of Palace conformations reduces by half. So I can imagine being off a factor 2 here and there, but hardly 10^10...

I do not know the rules of Xiangqi but I wonder if there are not illegal position for the simple reason that the pieces could not get there in the first place.

In chess the following positions are not legal even in case that the rules allow capturing the king

[D]3k4/8/8/8/8/8/2PKP3/3B4 w - - 0 1

[D]rnbqkbnr/pppppppp/8/8/8/7R/PPPPPPPP/RNBQKBN1 w - - 0 1

[D]rnbqkbnr/pppppppR/7p/8/7P/8/PPPPPPP1/RNBQKBN1 w - - 0 1

[hgm]

In Xiangqi it is not so easy to construct positions like that, because the line of Pawns is moved two ranks forwards compared to FIDE Chess, and already has a number of holes in it. (There is only a Pawn in every other file.) I, at least, could not think of one; every other piece seems to be alble to reach all the squares in principle accessible to it without moving a single Pawn.

Of course there are many squares an unpromoted Pawn cannot go to, (e.g. the first 3 ranks, like the first rank in FIDE Chess), as also in Xiangqi Pawns do not move backward. A Pawn stays in its file until it promotes by crossing the 'River' in the center of the board. The counting definitely would have to pay attention to that.

[d]rnbqkbnr/8/p1p2p1p/8/8/P1P2P1P/8/RNBQKBNR w
Xiangqi-initial-position-like Chess position

[bentonharper3]

H.G. if I'm reading you correctly the number of possible positions is comparable to chess but significantly fewer (by perhaps 100 times). let me know if this is roughly the case.

uri, the postions that pieces could never reach are labeled "impossible" rather than "illegal", but your point is significant. Illegal positions would be one such as where both kings are in check, which involves pieces moving to posible positions but done in violation of some rule. I don't know anything about Chinese chess or how the numbers for checkers and chess were devined. I have to let others crunch the numbers and trust to their expertise. Thanks for the help!!!!

[hgm]

H.G. if I'm reading you correctly the number of possible positions is comparable to chess but significantly fewer (by perhaps 100 times). let me know if this is roughly the case.

Well, I never calculated this number for Chess, but it seems intuitively correct. The total number of pieces is equal. The Chinese board is somewhat latrger (90 points in stead of 64 squares), but many pieces are confined to a small section of the board. (Kings to the 9-point Palaces, two Mandarins through a 5-point sub-section thereof, and two Ministers to 7 squares.) So on the average a piece has less freedom to move, despite the bigger board.

In addition promotion is only possible to one kind of piece, which can only access half the board. All PAwns can promote without anything being captured, though. In FIDE Chess you need at least one capture to allow 3 promotions, which potentially gives a factor 64 away (because of the missing piece). But you make up that factor by having 4 possible choices for each of the 3 promotions. So I guess that about evens out.