The number of legal chess positions is ~ 4.8 * 10^44

[abulmo2]

Eliminating such positions could be great to have an idea of the space of the chess game in order to solve it.

To determine the value of a game tree of depth d with uniform branching factor b, you basically need to look at at least 2 * b^(d/2) nodes. This minimum bound can be achieved by perfect move ordering. The total size of the game tree would be N = b^d, so 2 * b^(d/2) = 2 * sqrt(N).

So perhaps a very rought estimate for the size of a minimal proof tree would be 2 * sqrt(4.8 * 10^44) = 4.4 * 10^22.
Since chess is probably a draw, you would need a proof tree that shows that white is not losing and a proof tree that shows that black is not losing. But they could be solved separately and in parallel.

Howewver:
- The full game tree of chess does not have a uniform branching factor, which (I think) reduces the size of the minimal tree.
- To keep the size of the full game tree at 4.8 * 10^44, you need to deal with transpositions. I fear this is nearly impossible to get right (graph history interaction).
- We cannot hope to always guess the best move right.

I agree with what you say. What is annoying me is that the number of position is dominated with positions obtained after multiple promotions by both players. Without promotion, the number of positions is only 4 * 10^37, which is negligible compared to 4.8 * 10^44. But, in practice, promotion are rather rare, and multiple promotions even more.

[jefk]

although a digression of the pure math discussion about nr of positions..

mr 'towforce' wrote:

suppose for a moment that it's a win for white, though: the fact that we haven't yet found the win would imply that one or more of the moves needed to get the win are not obvious. The fact that these moves aren't obvious would imply that they look like bad moves.

forget it. it's like assuming that *maybe* after 1.g4! (first looking bad) in some
magical way White later is going to win. Well that's not going to happen.
Because Black has -continues to have -a choice (this sometimes is being forgotten (*) );
all ideas about zugzwang or so (maybe interesting for draughts) are ridiculous for chess.
There are two trees from the starting position, one the theoretical tree of all
moves, second a tree where Black would be mated in the end. But because Black
has a choice, it can be avoided to get into the losing tree. Yep it's that simple.
Kindergarten stuff (indeed), almost. It's a *draw* of course. Although not in
problem chess (strong solution required), but i'm not going to repeat myself).

(*) it's about perfect play; sure, Black may lose after 1.a4, or 1.g4, or whatever in a
game. Correct that, and look at theoretical perfect play and Black cannot lose in a
game of chess. That's not because of 'overwhelming evidence', its (imo) a fact (**).
guess why i added the (imo)

(**) talking about the kindergarten (in chess) it's comparable with the scholars mate,
kiddies may think they can win with Bc4 Qf3 and then bingo Qf7#. However they forget
that Black also has a choice, and you don't even have to have Magnus C's brain
(or having been educated in physics) to understand that.
In a similar way, in chess Black can always avoid being checkmated which i have
illustrated with many arguments (first of all in the KG part of this forum but
maybe later also elsewhere) thus it's a draw whereby i don't care whether someone
doesn't think this is an ultraweak solution or not. Mr Tromp a well respected mathematician
(unlike the SF coyotes) may well be able to understand my reasoning(s) if i would present
it in an academic way (instead of my earlier reasonings in the general topics forum (where i
had used an AI i admit, just for readability< and then, more in my own language KG forum).
Some facts of life (in game(***) theory_, whether you (or adjedrizta, or others) like it or not:
tictactoe = draw
connect4 (7*6) = win for first player
checkers = draw
internatl draughts is most likely draw
chess = draw
Go may be draw depending on komi and sharpness of the game
(unless the rules forbid a draw like for a new kind of
chess invented by larry K there's no draw); yes the nr of possible
positions in the game of Go is quite high, i know that


(***) yep life is a game, at least in simulation theory

[chesskobra]

I agree with what you say. What is annoying me is that the number of position is dominated with positions obtained after multiple promotions by both players. Without promotion, the number of positions is only 4 * 10^37, which is negligible compared to 4.8 * 10^44. But, in practice, promotion are rather rare, and multiple promotions even more.

Intuitively it can be explained as follows. All pawns are identical so if you just want to place 8 pawns on 48 squares you can do that in binom{48}{8} ways. But instead of 8 pawns if you had a variety of pieces, you would get many more positions. So now consider a very artificial game in which both sides promote as many pawns as possible with minimum other pieces leaving the board. Then at some point you will get lot of pieces on the board and no pawns. There will be a lot of positions of this type. Moreover, there will be a very large number of games starting from such positions.

There may also be different dynamics in practical human play. If both sides have a few pawns and both sides have promotion possibilities, then I think humans would find it very risky to think like I will try to promote my pawns and let my opponent promote his pawns also, because resulting pawnless multi-piece endgame is very risky for both sides because of the calculational difficulty of pawnless endings.

[syzygy]

Eliminating such positions could be great to have an idea of the space of the chess game in order to solve it.

To determine the value of a game tree of depth d with uniform branching factor b, you basically need to look at at least 2 * b^(d/2) nodes. This minimum bound can be achieved by perfect move ordering. The total size of the game tree would be N = b^d, so 2 * b^(d/2) = 2 * sqrt(N).

So perhaps a very rought estimate for the size of a minimal proof tree would be 2 * sqrt(4.8 * 10^44) = 4.4 * 10^22.
Since chess is probably a draw, you would need a proof tree that shows that white is not losing and a proof tree that shows that black is not losing. But they could be solved separately and in parallel.

Howewver:
- The full game tree of chess does not have a uniform branching factor, which (I think) reduces the size of the minimal tree.
- To keep the size of the full game tree at 4.8 * 10^44, you need to deal with transpositions. I fear this is nearly impossible to get right (graph history interaction).
- We cannot hope to always guess the best move right.

I agree with what you say. What is annoying me is that the number of position is dominated with positions obtained after multiple promotions by both players. Without promotion, the number of positions is only 4 * 10^37, which is negligible compared to 4.8 * 10^44. But, in practice, promotion are rather rare, and multiple promotions even more.

I think my (very very rough) estimate does take this into account. Positions with 8 knights are completely legal, but they will just not appear in minimal proof trees because they won't be reached if one side is playing "best" moves.

[Uri Blass]

Eliminating such positions could be great to have an idea of the space of the chess game in order to solve it.

To determine the value of a game tree of depth d with uniform branching factor b, you basically need to look at at least 2 * b^(d/2) nodes. This minimum bound can be achieved by perfect move ordering. The total size of the game tree would be N = b^d, so 2 * b^(d/2) = 2 * sqrt(N).

So perhaps a very rought estimate for the size of a minimal proof tree would be 2 * sqrt(4.8 * 10^44) = 4.4 * 10^22.
Since chess is probably a draw, you would need a proof tree that shows that white is not losing and a proof tree that shows that black is not losing. But they could be solved separately and in parallel.

Howewver:
- The full game tree of chess does not have a uniform branching factor, which (I think) reduces the size of the minimal tree.
- To keep the size of the full game tree at 4.8 * 10^44, you need to deal with transpositions. I fear this is nearly impossible to get right (graph history interaction).
- We cannot hope to always guess the best move right.

I agree with what you say. What is annoying me is that the number of position is dominated with positions obtained after multiple promotions by both players. Without promotion, the number of positions is only 4 * 10^37, which is negligible compared to 4.8 * 10^44. But, in practice, promotion are rather rare, and multiple promotions even more.

I can define chessX exactly as chess with the only difference that when white can win not only by checkmate but also by getting a position that white can promote next move to get 2 queens or 3 rooks or 3 bishops or 3 knights in chess or position that black can do the same.

Assuming chessX is a draw it is possible to prove that black does not lose in chess when you only have something of the order of 4*10^37 positions.

You can probably reduce the number of positions to less than it if you decide that some rare pawn structures that never appear in normal chess games are defined to be win for white.

Maybe chess is a draw even with more restrictions that also preventing part of the normal positions for example if you have a rule that pushing a pawn to the 7th rank by white or black is a win for white(I guess not in this case but I am not sure and we need to develop strong engines that play this game and see the result of the games to have a better opinion).

[jefk]

adding to my comment about towforce' statement

one or more of the moves needed to get the win are not obvious. The fact that
these moves aren't obvious would imply that they look like bad moves.

this often occurs, of course, in problem chess. Eg, in some mate in x problems, starting
with a quiet move, but then nevertheless going to force mate.
However, key in such - artificial- positions is some sort of zugzwang, whatever Black
does after such a 'non-obvious' move, a forced mate will follow nevertheless; which is
only possible if Black's nr of options (playable moves) are severely 'restricted'
(there may be more moves possible, but they all will be bad thus not 'playable' )

From the normal starting position in chess (and most likely also in chess960)
the situation is different, Black has a high nr of playable options every move,
and continues to have that when he doesn't play bad moves. So, as i said
before, the tree of moves where mate can be avoided, is growing faster
than the tree of move (sequences) where he can be mated. Which means
there is no forced win; simple as that; as confirmed in practice.
Note i also have looked at 'non-obvious' moves, to see if there maybe, just
maybe wasn't a possibility to get an opening advantage for White, first
years ago looked at 1.c4 (draw) then also at moves as 1.a3 or 1.g3 or
1.b3. All draw, 'best' still are the conventional moves as 1.e4, d4, or Nf3,
the only unconventional move which 'looks like a bad move' is 1.g4
and ... tadaa.. it also actually *is* a 'bad move'!

PS another way of getting to such an insight, would be maybe via 'proof games'
(there's software like Euclid or so) for that (although i haven't tried it):
http://lestourtereaux.free.fr/euclide/
Take a certain mate position, with minimum nr of pieces, and now go backwards to
find some possible move sequences which led to that mate. There will be many
possible games, ofcourse and i wouldn't care which one would be the shortest (other topic).
But anyway, subsequently, when inspecting such a game (ending in a win for White)
you will see (usually without much difficulty) that somewhere Black made a (big
) mistake (or more -small- mistakes), and it's relatively easy (certainly with a top
engine) to correct that mistake. I'm stating (conjecturing for the math people) that
this is an absolute truth in chess (not a revolutionary thought ofcourse most
chess experts know this), in other words there's no forced win for White.