A game is a conflict, with formal rules and a finite number of choices of what to do at each stage, between two or more players. The study of games belongs to a branch of mathematics and logic known as game theory.


If a game is simple enough, it can be solved for all possible outcomes. This is the case, for example, with tic-tac-toe and Nim. By harnessing the power of computers to check through vast numbers of moves, even more complicated games are succumbing to a complete analysis. In the 1990s, Nine Men's Morris was shown, by searching through billions of possible endgames, to be a certain draw if both players work to an optimal strategy. Checkers may be the next to be fully determined: its roughly 500 million trillion possible positions may soon be within reach of the most powerful supercomputers.