Check, mate

I’ve been involved in an email exchange with a friend over the last few days. His premise was that it can’t be that hard for a computer to evaluate at the beginning of a game of solitaire every possible outcome to figure out whether the game is soluble, not in the mixing-with-liquid sense of course. And further, to report how well he did compared to the best possible outcome.

Without assuming any artificial intelligence or logic, I made some assumptions. Let’s assume that there are 50 binary decision points in a game—a point at which you can either put this 9 on the 10 or that 9 on the 10; or one where you move the top card on to a series or combine two series together. (I know that there are sometimes more than two options available, but let’s assume for the sake of calculation that each decision point has two and only two options.) I don’t know if 50 is in the right ballpark. If anything, it seems a bit low to me.

So assuming you get a total of 50 choices irrespective of what choices you made previously in the game, there are 2^50 ways in which the game can pan out. That’s 1,125,899,906,842,624 outcomes. If you evaluate one game every second, it will take you 20 billion years. With a 10GHz processor (assuming each option is a single operation—not likely but hey), it will take you 31 hours.

He didn’t like this, and compared it to his ZX81, which was able to look relatively quickly five moves ahead in chess and usually beat him in under 30 moves. But in this scenario, the computer only looking only five moves ahead makes a significant difference to the calculation time, even though there are far more options available in chess than in solitaire. In chess, there are a maximum of 141 different things you can do at any juncture. (Each pawn can have a maximum of four moves (move forward two, move forward one, take to the left, take to the right), each of the rooks and bishops has 14 possible moves, the knights have eight, the queen 28, the king eight, plus the castling option.) Usually, most of these options are made unavailable by the positioning of other pieces. (For example, at the beginning of the game, you only have 20 moves available. And if the bishop is on the side of the board, it only has seven moves available rather than 14. And taken pieces are out of the equation.) So let’s assume there are 50 moves available at each juncture.

Only looking 5 moves ahead rather than to the end of the game means that the computer evaluates 50^5 scenarios, or 312,500,000. At one operation per move, that would take our 10GHz processor 0.03 seconds, the ZX81 slightly longer. The fact that the number of possible moves is greatly increased is more than countered by the fact that we’re only looking a few moves ahead. If all games took 60 moves (30 for each player), then assuming 50 options at each point, the 10GHz processor would need 2.75 * 10^84 years to evaluate every possible game. That’s 27,500 years for every atom in the entire universe. Give or take.


Leave a Reply