8

If both sides make moves completely randomly but legally, how many different games are there? Since the 50 move rule applies, this number should be finite (but HUGE).

For example, there are 20 possible first moves for white to start with. If we include the first move for black, there will be 400 different positions.

Among all these different games, how many of them will be win for white? Black? Draw?

I guess very few (in term of percentage) game will end with a draw. And the winning percentage will be roughly the same for white and for black.

Improve this question
  • 2
    There are two different questions. The number of games has been asked before, but the result of playing random moves hasn't as far as I know. This can be estimated through running random simulations. The most common result is a draw because random moves are rather incompetent at mating. I can post more detailed stats as an answer if the question is reopened. – itub May 3 '19 at 1:41
  • 6
    My stats from one run with 1000 simulated games: 'is_insufficient_material': 500, 'can_claim_fifty_moves': 157, 'can_claim_threefold_repetition': 147, '0-1': 75, '1-0': 72, 'is_stalemate': 49. ('0-1' and '1-0' are all termination by checkmate, since there are no random resignations in my model :-) – itub May 3 '19 at 2:52
  • Thank you @itub! You understand that my question is not completely a duplicate and you answered it well. Thank you for conducting the experiments! – Zuriel May 3 '19 at 11:09
  • 2
    @itub Why don't you add your results as an answer? Since an exhaustive is impossible, random rollouts are a reasonable way to get an approximate result. Did you use python-chess to perform the rollouts? – Fabian Fichter May 25 '19 at 10:47
  • 1
    Note that even if it weren't for the 50 move rule, the number would still be finite (because eventually a position would be repeated 3 times or all the pieces get exchanged off to a draw). – Inertial Ignorance Feb 24 '20 at 0:21
8

The number of games is huge but finite, and estimates have been made based on a number of assumptions. But that question has been asked before already, so I won't go into the details here. A short answer given on Wikipedia is at least 10123, based on an average branching factor (moves per position) of 35 and an average game length of 80; after only 10 plies (5 full moves) the exact count is 69,352,859,712,417. See Is the number of possible chess games infinite? for more answers.

The probable outcomes of a game with random moves can be estimated "experimentally" by running random simulations. I wrote a program to do just that, had it play 1000 games, and these were my results:

Outcome                        Count  Avg. #moves
-----------------------------  -----  -----------
Draw by insufficient material    500          179
Draw by fifty-move               157          208
Draw by threefold repetition     147          164
Black wins by checkmate           75           87
White wins by checkmate           72           78
Draw by stalemate                 49          138

I think that the most common result is a draw because random moves are rather incompetent at mating, which requires the interaction of at least three pieces (counting both colors, including kings), in contrast with capturing, which is much easier to do by chance, only requiring the interaction between two pieces. After enough captures occur, you end up with insufficient material, which is the most likely outcome, occurring 50% of the time.

Alternatively, if you don't luck into a capture for long enough, you are also somewhat likely to bump into the fifty-move limit or threefold repetition. (My program assumes that these draws are claimed as soon as possible, even though they are not automatic per the rules, unlike 75-move or fivefold repetition.)

I don't expect a color advantage in random games. My sample had a few more wins with Black than with White, but I think that's within statistical noise.

For anyone who is interested, here's my program, written in Python and using the python-chess module:

import chess
import collections
import random

terminations = ['is_stalemate', 'is_insufficient_material', 'is_checkmate',
    'can_claim_fifty_moves', 'can_claim_threefold_repetition']

def get_termination(board):
    for termination in terminations:
        method = getattr(board, termination)
        if method():
            return termination

def game():
    board = chess.Board()
    for i in range(10000):
        moves = list(board.legal_moves)
        move = random.choice(moves)
        board.push(move)
        result = board.result(claim_draw=True)
        if result != '*':
            termination = get_termination(board)
            print(result, board.fullmove_number, termination)
            return result, termination

stats = collections.Counter()
for i in range(1000):
    result, termination = game()
    if termination == 'is_checkmate':
        stats[result] += 1
    else:
        stats[termination] += 1

print(stats)
Improve this answer
  • 2
    The problem with random moves is that short games are more heavily selected. Say all you have left is a pawn on the 7th with the 50 move counter at 49. Too many games to count could be played from there, perhaps in the neighborhood of 10^100 (assumes a branching factor of 4-5 for the weaker side and 20-25 for the stronger side, playing 50 moves each). But if you're selecting a move randomly, most of the time the king will move and the 50 move rule triggers, and half the time the pawn does promote, it will promote to a knight or bishop and the game instantly ends due to insufficient material. – D M May 25 '19 at 17:33
  • 4
    You are right, I answered a different question: "if both players move randomly, what is the probability of each outcome?" instead of "out of all possible games, what is the distribution of outcomes?" To drive that point further I should note that one of the mates I saw was in three moves! That game will probably appear repeatedly if you run the simulation longer, unlike the longer games which you probably will never see again! – itub May 25 '19 at 19:09
  • @itub, "I should note that one of the mates I saw was in three moves" makes me think that your program is just counting short helpmates. – hkBst May 28 '19 at 10:48
  • @hkBst, nope, as you can see from the table the average checkmate took about 80 (full) moves. Still, a fool's mate has a pretty high probability of happening randomly, since it only takes a couple of moves and there are many variants. It would be interesting to compute the exact probability but I guess it might be one in a few thousand. – itub May 28 '19 at 11:26
7

It would seem that the longest games would end up being the most numerous, by far. On any particular move, if you end a game, that's one game, but if you let it continue, it's many games. It would seem, therefore, that the greatest number of games would continue until one side had a single piece left. The remaining piece should not be a knight or bishop, as that would end the game via insufficient material, and a rook would have fewer possible moves than a queen - over the course of the next 50 moves, the number of possible games involving a rook would fade into insignificance compared to the number of possible games involving a queen. If the remaining piece is a pawn, it must eventually promote to something to continue the game, and it may as well promote to a queen. So we're left with the overwhelming number of games ending with king and queen vs king - we can pretty much ignore all other games as insignificant.

Imagine the board after 49 moves looking like this:

[FEN "8/6Q1/8/8/8/8/8/5K1k w - - 0 1"]

In this position, White to move has 26 possible moves, out of which 5 are checkmates. So that would be a 5/26 chance of a checkmate, which is about 19.2% I think this has the highest checkmate probability of any king and queen vs king position.

However, it's obvious that it's rather unlikely for this position or a similar one to come up at the end of the game. There are 4 corner squares on the board, and 24 non-corner edges, and these are the only places where the king may be checkmated. If the black king is placed randomly, there is a 1/16 chance he will end up in a corner, and if the white king is then randomly placed on a legal square, there is a 1/12 chance he will be on a square where checkmate is possible. There is also a 3/8 chance that the black king would be placed on a non-corner edge, and a 3/58 chance that the white king would then be placed on a square allowing checkmate. If you add those probabilities, that's less than a 2.5% chance that the kings would be on squares even allowing for checkmate. Even if you assume the maximum 19.2% chance that the queen can deliver checkmate (which is unlikely), that results in less than a 0.5% chance of checkmate.

But it gets worse. That assumed the kings were placed randomly. But, of course, kings are not actually placed randomly on a board; they must move to their locations. The branching factor is going to be higher when the kings have more possible moves (especially the weaker side's king), and the kings have more possible moves when they are away from each other and not on the side of the board (and if they're in the corner of the board with the other side's king nearby, they have very few possible moves.) So, more games are going to have the kings in no position to allow a checkmate on that last move than you'd expect from random placement.

Although a checkmate could happen earlier than move 50, earlier checkmates are going to become exponentially rare in comparison the farther back you go, and this will have only a small effect. (And even this small effect is partially offset because there's also the possibility of a draw via stalemate, capturing the queen, or repetition before move 50.)

So we've determined that checkmates are rare. But who gets more of them and by how much? That's unclear to me. Nevertheless, we can determine an upper bound on the ratio between the number of White checkmates and the number of Black checkmates.

There are going to be many games that start with the knights and perhaps the rooks moving, before any pawn is moved. Because up to 49.5 moves can be played this way without triggering the 50 move rule, the number of these games will quickly dwarf the number of games that open any other way. After 49.5 moves, Black must make a pawn move or capture, or else the game will end prematurely. The fact that Black must do this first is the relevant difference between White and Black at this point.

But what if, instead, White is the one to move a pawn or capture, one ply early? White and Black essentially switch roles, and we will lose one ply of possible non-capture non-pawn moves. But the branching factor at this stage of the game is relatively low. In positions where no pawn has been moved, there are at most 6 squares each of the knights can reach without capturing anything, and the rooks can also reach one square each. That's 14 possible moves, which would be lost by having White make the first pawn move or capture. So the number of games where one side checkmates cannot exceed the number of games where the other side checkmates by more than a factor of 14.

Improve this answer
  • Good albeit heuristic reasoning (+1). I wonder how rigorous it could be made. Your reasoning that most games are the longest possible seems suspect because not all non-terminal positions can be extended to a game of maximal length, so your statement that "if you end a game, that's one game, but if you let it continue, it's many games" doesn't by itself establish that most games have maximal length. Nevertheless, the argument you give makes it very plausible that most legal games end in a draw. – John Coleman Jun 4 '19 at 19:02
  • @JohnColeman Perhaps I should have said "longer" instead of "longest". I wasn't trying to claim that 5898.5 move games (or whatever the absolute maximum is) would be in the majority. – D M Jun 5 '19 at 2:29
  • Say that a game is "maximal" if it has the property that the only legal moves in the penultimate position were ones that ended the game. In terms of the tree of all possible games, these correspond to leaf nodes which have no niece/nephew nodes (all of its siblings are also leaves). It is clear (for the reasons that you give) that the overwhelming majority of games are maximal in this sense (though proving it is tricky, since it isn't a general fact about trees per se). Furthermore, it seems clear that most maximal games have 3 pieces on the board (as you said). – John Coleman Jun 5 '19 at 11:55
  • This answer is an amazing work. – Pedro A Apr 26 '20 at 4:07
0

Nobody knows. It is beyond our ability to count even with computers. The best you can do is statistically over all players to try to estimate the final result. Note that bad play which patzers make will tend to make the numbers move towards a more even black-white split and I suspect fewer draws.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.