42
$\begingroup$

Imagine a game of chess where both players generate a list of legal moves and pick one uniformly at random.

Q: What is the expected outcome for white?

  • 1 point for black checkmated, 0.5 for a draw, 0 for white checkmated. So the expected outcome is given by $$\mathrm{Pr}[\text{black checkmated}]+0.5\ \mathrm{Pr}[\text{draw}].$$
  • Neither player resigns, nor are there any draw offers or claims.

As a chess player, I'm curious if white (who plays first) has some advantage here.


I'm not expecting an exact answer to be possible. Partial results (e.g. that the expectation is >0.5) and experimental results are welcome. (The expectation is not 0 or 1, since there are possible games where white does not win and where black does not win.)

I'm guessing this has been looked at before, so I decided to ask first (rather than implement a chess engine that makes random moves and hope to find something other than "draw, draw, draw, draw, ..."). Searching for "random game of chess" lists Chess960 and other randomized variants, which is not what I want.


Technicalities:

  • En passant capturing, castling, pawn promotion, etc. all apply as usual.

  • The FIDE Laws of Chess will be updated 1 July 2014 with the following:

    9.6 If one or both of the following occur(s) then the game is drawn:

    • a. the same position has appeared, as in 9.2b, for at least five consecutive alternate moves by each player.

    • b. any consecutive series of 75 moves have been completed by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence.

    This means that games of chess must be finite, and thus there is a finite number of possible games of chess.

$\endgroup$
  • 1
    $\begingroup$ I'm only guessing here, but I would expect the average game to be very long, because it is difficult to checkmate by random moves. For the same reason, I suspect that most such games will end in a draw. And moreover, because games become so long, simulating enough of them to get reliable data will take a long time. For simulation purposes, it might be easier to adopt high speed chess rules, in which it is not illegal to move the king into a threatened square (or leaving it there), and the game is won by actually capturing the king. $\endgroup$ – Harald Hanche-Olsen Jun 24 '14 at 5:16
  • $\begingroup$ I don't know of any such result, or any easy way to calculate one. The two shortest possible games, and thus intuitively the modal (most common) sample paths, would be fool's mate (1.f4 e5 2.g4 Qh4# and 1.f4 e6 2.g4 Qh4#, with transpositional possibilities, i.e. 1.g4 before 2.f4), which has black winning in both cases. But the probability of either these paths is still pretty small, at around $\left(\frac{1}{20}\right)^4$, assuming each side has roughly 20 legal moves during the opening stages. Black would be around 20 times less likely to suffer a similar fate so early. $\endgroup$ – user105475 Jun 24 '14 at 5:57
  • 1
    $\begingroup$ @Bhoot. There are more variations to obtain mate in 2. Both Qh4 and g4 are required moves by black and white respectively. But, black can play either e6 or e5 on their first move and white can play f3 or f4 on either move 1 or 2(so long as the other move is g4). Your examples did take transposition into account, but not f3. Total, you'd get 8 different move orders to reach mate in 2. $\endgroup$ – Vincent Jun 24 '14 at 7:31
  • $\begingroup$ @Rebecca Do you play on ICC by chance? $\endgroup$ – Vincent Jun 24 '14 at 7:37
28
$\begingroup$

I found a bug in the code given in Hooked's answer (which means that my original reanalysis was also flawed): one also have to check for insufficient material when assessing a draw, i.e.

int(board.is_stalemate())

should be replaced with

int(board.is_insufficient_material() or board.is_stalemate())

This changes things quite a bit. The probabillity of a draw goes up quite a bit. So far with $n = 5\cdot 10^5$ samples I find

$$E[\text{Black}] \approx 0.5002$$ $$E[\text{White}] \approx 0.4998$$ $$P[\text{Draw}] \approx 84.4\%$$

A simple hypotesis test shows that with $P(\text{white})=P(\text{black})=0.078,~P(\text{draw})=0.844$ and $N=5\cdot 10^5$ samples the probabillity to get $|E[\text{Black}] - 0.5| > 0.002$ is $25\%$ so our results are perfectly consistent with $E[\text{White}]=E[\text{Black}]=0.5$. The "hump" remains, but is now easily explained: it is due to black or white winning. Either they win early or the game goes to a draw.

enter image description here

Here is one of the shortest game I found, stupid black getting matted in four moves:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Nice catch, chalk this one up to the power of peer review! To be honest, this library was simply the easiest to install and get up and running, I imagine that a C library may be much faster to run long simulations. Also, mate is possible with two moves. $\endgroup$ – Hooked Jun 25 '14 at 14:17
  • 1
    $\begingroup$ I don't understand why the change you made altered the results. After all, in any case where there is insufficient material to mate, the result must eventually be a draw by one of repetition, stalemate, or the 50 (or 75) move rule. How did adding that explicit condition increase the probability of a draw? $\endgroup$ – mjqxxxx Jun 25 '14 at 14:22
  • 1
    $\begingroup$ @mjqxxxx, I think it's because the chess library considers the game to be over when neither player has enough material to mate, and so breaks the loop, but doesn't consider it to be a stalemate, so it wasn't being counted correctly. $\endgroup$ – Peter Taylor Jun 25 '14 at 14:37
  • 3
    $\begingroup$ Hehe, I was supposed to do peer-review for an acctual paper...but did this instead. I used the library myself (and also your code) as a blackbox in the beginning, just by accident I tried to output the FEN code to see the positions that I noticed it. Yes, c++ should be much faster, python is sloooow:) I agree, I will try to make this more precice when I get some time. $\endgroup$ – Winther Jun 25 '14 at 14:37
  • 1
    $\begingroup$ Okay, I see. So the final game states were all correct, but just weren't being analyzed correctly, because their state (win vs draw) was not being written to file correctly. $\endgroup$ – mjqxxxx Jun 25 '14 at 14:58
25
$\begingroup$

Update: The code below has a small, but significant oversight. I was unaware that a stalemate would not be counted the same way as a board with insufficient pieces to play and this changes the answer. @Winther has fixed the bug and reran the simulations. That said, there is still value to the code being posted so I'll leave it up for anyone else to repeat the experiments (and find more bugs!).


Slightly rephrasing your question,

Is the expected outcome for EX[white] = 1/2 in a random game?

To test this, I simulated 10^5 games using the library python-chess. The code is posted below for those wishing to repeat the numerical experiment (this takes about 4 hours on an 8-core machine). In the 100000 games, 46123 came up as wins for white and 6867 games were ties. This puts the expected value of the game at

$$ \text{EX}[white] = 0.495565 $$

Using the 2-sided normal approximation to the binomial test of a fair game, we get a p-value of 0.00511. Therefore, we can reject the null-hypothesis that the game is fair. This was surprising to me.

In other words, $\text{EX}[white]<1/2$ looks to be statistically significant, however the advantage for black is very small.

Personally, the more interesting question is the distribution of game length, hence a plot of it is included below.

import chess, random, itertools, multiprocessing
simulations = 10**5

def random_move(board):
    return random.choice(list(board.legal_moves))

def play(game_n):
    board = chess.Bitboard()
    ply = 0
    while not board.is_game_over():
        board.push( random_move(board) )
        ply += 1

    # board.turn == 0 -> White, == 1 -> Black
    return game_n, int(board.is_stalemate()), board.turn, ply

P = multiprocessing.Pool()
results = P.imap(play,xrange(simulations))

with open("results.txt",'w') as FOUT:
    for game in results:
        s = "{} {} {} {}\n".format(*game)
        FOUT.write(s)

enter image description here

There is much to be mined out of this dataset, but I am not a chess-aficionado. I'm not sure why the distribution contains two "humps", comments are welcome.

$\endgroup$
  • 1
    $\begingroup$ Very nice, ++i. It would also be cool to see 'where' blacks extra wins comes from, i.e. what is the game length distrbution for white's wins compared to blacks wins. $\endgroup$ – Winther Jun 24 '14 at 21:05
  • $\begingroup$ It would be nice to see an update based on @Winther's answer - it really doesn't make any sense that white has a disadvantge, however small. $\endgroup$ – nbubis Jun 25 '14 at 7:13
  • 1
    $\begingroup$ @nbubis I'm going to let Winther take the credit for finding the flaw in the code above. I happy enough, my initial answer, flawed as it was, was enough to spur a better investigation. I'll update my answer and point to his, IMHO he answers the question correct and should get the check. $\endgroup$ – Hooked Jun 25 '14 at 14:10
4
$\begingroup$

full code and results

from queue import Queue
import chess, random, _thread
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import scipy.stats

def outcome(board):
    if board.is_checkmate():
        if board.turn:
            return "Black"
        else:
            return "White"
    else:
        return "Draw"

#calc total moves
def moves(board):
    if board.turn:
        return board.fullmove_number * 2 - 1
    else:
        return board.fullmove_number * 2 - 2

def play(i):
    board = chess.Board()
    while not board.is_game_over():
        board.push(random.choice(list(board.legal_moves)))
    return i, outcome(board), moves(board)

def thread_wrapper(i, func, stat, q):
    def run():
        q.put(func)
        stat[i] = True
    return run

workers = 500000
status = [False for i in range(workers)]
q = Queue()
for i in range(workers):
    _thread.start_new_thread(thread_wrapper(i, play(i), status, q), tuple())

while not all(status):
    pass

results = []
while not q.empty():
    results.append(q.get())
results_df = pd.DataFrame(results, columns=['game_n', 'outcome', 'moves'])
#TODO process the results

results_df.to_csv('my_file.csv')

black = results_df.loc[results_df['outcome'] == 'Black']
white = results_df.loc[results_df['outcome'] == 'White']
draw = results_df.loc[results_df['outcome'] == 'Draw']
win = results_df.loc[results_df['outcome'] != 'Draw']

Total = len(results_df.index)
Wins = len(win.index)

PercentBlack = "Black Wins ≈ %s" % ('{0:.2%}'.format(len(black.index)/Total))
PercentWhite = "White Wins ≈ %s" % ('{0:.2%}'.format(len(white.index)/Total))
PercentDraw = "Draw ≈ %s" % ('{0:.2%}'.format(len(draw.index)/Total))
AllTitle = 'Distribution of Moves by All Outcomes (nSample = %s)' % workers

a = draw.moves
b = black.moves
c = white.moves

kdea = scipy.stats.gaussian_kde(a)
kdeb = scipy.stats.gaussian_kde(b)
kdec = scipy.stats.gaussian_kde(c)

grid = np.arange(700)

#weighted kde curves
wa = kdea(grid)*(len(a)/float(len(a)+len(b)+len(c)))
wb = kdeb(grid)*(len(b)/float(len(a)+len(b)+len(c)))
wc = kdec(grid)*(len(c)/float(len(a)+len(b)+len(c)))

total = wa+wb+wc
wtotal = wb+wc

plt.figure(figsize=(10,5))
plt.plot(grid, total, lw=2, label="Total")
plt.plot(grid, wa, lw=1, label=PercentDraw)
plt.plot(grid, wb, lw=1, label=PercentBlack)
plt.plot(grid, wc, lw=1, label=PercentWhite)
plt.title(AllTitle)
plt.ylabel('Density')
plt.xlabel('Number of Moves')
plt.legend()
plt.show()

ExpectedBlack = "EV Black Wins ≈ %s" % ('{0:.2%}'.format(len(black.index)/Wins))
ExpectedWhite = "EV White Wins ≈ %s" % ('{0:.2%}'.format(len(white.index)/Wins))
WinTitle = 'Distribution of Moves by Wins (nWins = %s)' % Wins

plt.figure(figsize=(10,5))
plt.plot(grid, wtotal, lw=2, label="Wins")
plt.plot(grid, wb, lw=1, label=ExpectedBlack)
plt.plot(grid, wc, lw=1, label=ExpectedWhite)
plt.title(WinTitle)
plt.ylabel('Density')
plt.xlabel('Number of Moves')
plt.legend()
plt.show()

print("Most frequent moves of All:", grid[total.argmax()], round(max(total), 4), "for", Total, "games")
print("Most frequent moves of Draws:", grid[wa.argmax()], round(max(wa), 4), "for", len(draw.index), "games")
print("Most frequent moves of Wins:", grid[wtotal.argmax()], round(max(wtotal), 4), "for", Wins, "games")
print("Most frequent moves of Black wins:", grid[wb.argmax()], round(max(wb), 4), "for", len(black.index), "games")
print("Most frequent moves of White wins:", grid[wc.argmax()], round(max(wc), 4), "for", len(white.index), "games")

All results:

All Results

Non-draw results:

Results of Wins

Most frequent moves of All: 368 0.0036 for 500000 games

Most frequent moves of Draws: 370 0.0035 for 422856 games

Most frequent moves of Wins: 135 0.0008 for 77144 games

Most frequent moves of Black wins: 133 0.0004 for 38546 games

Most frequent moves of White wins: 137 0.0004 for 38598 games

$\endgroup$
  • $\begingroup$ Your answer doesn't seem to give anything more than the already existing ones. $\endgroup$ – Arnaud D. Apr 11 '17 at 15:31
  • $\begingroup$ @ArnaudD. Disagree. It verifies the existing answers, reducing the possibility that there were further bugs. It would be more useful if it were code in a new language (not python) and/or specifying the rules from scratch, but it is still useful. $\endgroup$ – 6005 Jun 7 '18 at 5:12
1
$\begingroup$

@Winther, @Hooked, @yaoster I don't have enough reputation to comment, I noticed that your code assumed board.turn==1 to mean Black's turn, but please correct me if I'm wrong, it seems the opposite is true as I checked python-chess documentation (ie. board.turn==1 means White's turn).

If this is true, your analysis would suggest White has a slight advantage, which is what most people would expect?

From python-chess documentation:

chess.WHITE = True

http://python-chess.readthedocs.io/en/latest/core.html?highlight=turn#chess.WHITE

$\endgroup$
  • 2
    $\begingroup$ Not sure why the downvotes, it seems like a useful comment if true! $\endgroup$ – 6005 Jun 7 '18 at 5:16

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.