Does White have an advantage in chess?

It seems likely, doesn’t it? After all, as White, you get to develop your pieces first, putting them in position to better attack Black, or at least defend against his/her attacks. And the statistics seems to bear this out (at least, according to Wikipedia, my source for all things true). Though it could turn out that Black has an advantage – it might be that any move by White fatally weakens his/her position, so that they are at a comparative disadvantage to Black.

Whatever the outcome might be, it turns out that if either side has an advantage, that advantage is necessarily complete. Put more formally: either (a) there exists a strategy profile for White that guarantees victory, or (b) a strategy profile for Black that guarantees victory, or (c) strategy profiles for both White and Black that guarantee a draw. It sounds somewhat trivial, but it’s not: for example, if (a) is true, this means that no matter what Black does, the outcome of the game is not in doubt – White will win.

Results such as these are common among many games without exogenous uncertainty, and many games have been solved, so we know which of the analogues to the above possibilities are true. For example, checkers was recently shown to have strategy profiles for both players which guarantee a draw. So that this holds true for chess as well should not come as a surprise.

To show that one of these three possibilities must hold, we can draw a game tree which contains all the possible move sequences in chess[1]. This is because chess ends in a finite number of moves: a draw is automatically declared if the same position is reached three times, or if fifty moves have gone by without a pawn move or a piece capture. Since there are only a finite number of possible pawn moves (given the size of the board) and piece captures (since there are only 32 pieces), the game is finite.

Next, we can use backward induction (as in my post on tic-tac-toe) from each possible ending of a game to determine the outcome from the beginning. At each node, the player involved (White or Black) deterministically selects the branch that leads to the best final outcome for him/her (using tie-breakers if necessary if several outcomes are equally good). We proceed in this manner all the way up to the initial node, corresponding to the starting position of the game. We can then go back down the tree, and since we have already determined the best response to any position, we can deterministically get to the best outcome for Black or White. This automatically yields a win for one of them, or a draw.

Unfortunately, while this works well in theory, in practice it is virtually impossible. Given the combinatorial explosion of positions in chess, the computing necessary to determine which possibility is correct is infeasible. I guess we’ll be stuck with just a good game of chess.


[1] That is, theoretically; the actual game tree is WAY too big to actually depict

Advertisements

Picking off the runner

You gotta keep him close to first. Otherwise he might as well walk to second. Don’t give him anything for free.

But what’s the best way to do that? How often should one throw over to the first baseman to make sure that he doesn’t steal?

Let’s model this through the payoff to the pitcher and the runner. The runner, obviously, wants to steal second, or advance an extra base on a ball put in play. The pitcher wants the exact opposite: he wants to prevent that from happening. To do so, he will attempt to pick off the runner at first if he gets too greedy.

So let’s now assign values to this, as a function of how big a lead that the runner takes (x), and how often the pitcher throws the ball over to first (t). We say that the runner gets payoff  from gaining an extra base, and does so with probability F(x), with \frac{\partial F(x)}{\partial x}>0. Meanwhile, the pitcher gets payoff v from picking off the runner, which occurs with probability P(x,t), where \frac{\partial P(x,t)}{\partial x} > 0 and \frac{\partial P(x,t)}{\partial t} > 0 for x>0, while P(0,t)=0. In other words, the probability you get picked off is greater the bigger a lead you take, and the more often the pitcher throws over to first, assuming you’re not actually standing on first. Finally, since you win in baseball if and only if the other team loses, we model this as a zero-sum game.

If this were our entire expression, it would be obvious that the pitcher should throw to first base as much as possible. In other words, he should try to pick off the runner at first at literally every single moment, and ignore the batter at home. So why don’t we see this?

The reason is because the pitcher is only human. Every time he throws the ball to first, there’s a chance that it will get away from him and sail over the first baseman’s head. If so, the runner will get his extra base anyway as the team on the field scrambles to recover the ball. This means that by throwing more frequently, there are more opportunities to screw up. Assuming the probability of throwing the ball away is the same each time, this gives the runner an additional payoff of  given how often the ball is thrown. Thus, our expressions for the payoffs of the runner and the pitcher are:

\pi_{r}=uF(x)+ut-vP(x,t)

\pi+{p}=vP(x,t)-uF(x)-ut

A Nash equilibrium will occur whenever the pitcher cannot make it better for his team to throw more frequently, and the runner cannot improve his chances anymore of taking an extra base without risking himself too much. Thus, in equilibrium:

u\frac{\partial F(x)}{\partial x}-\frac{\partial P(x,t)}{\partial x}=0

u-v\frac{\partial P(x,t)}{\partial t}=0

Of course, it’s possible that the pitcher is so good at picking people off that the runner doesn’t dare step off the bag, in which case we have an equilibrium which doesn’t satisfy the above two equations. Alternatively, the runner could be so good that no matter how often the pitcher tries to pick him off, he gets the extra base anyway, in which case the equations don’t hold either. But these cases are not normally found in the big leagues, so we’ll leave it as is.