A few more thoughts on game theory, intended to form an addition to elem_125's excellent write-up above.

It is important to understand that game theory applies beyond the bounds of what one would usually consider "games". Certainly game theory has something to say on games like Chess and Go, but it applies equally well to any system where parties are in potential competition. I say potential because game theory also handles ideas like the emergence of co-operation! You will perhaps now be getting a feeling for how broadly game theory is actually spread.

An example of a 'game theory' emerging in a situation which is certainly not considered a game by most affected would be in the recent firemen's strike here in the UK. This is certainly a game according to our earlier definition, having competing parties - firemen and the government - and a number of end results. Yet it is of the utmost seriousness! Note also that it needn't be a zero-sum 'game'; had it been resolved earlier, both parties might have come out of it better off. As it is, both parties will probably lose public favour.

It is these non-zero-sum games that most interested the great John Nash, subject of the film A Beautiful Mind. There's a fair amount about that great hero of game theory under his node, but within the topic of this one I'd like to point out just how far-reaching his ideas were. In nature, non-zero-sum games are just as common as zero-sum ones - unlike humanly constructed games, where we would usually consider it quite strange for both sides to lose! His work on Nash equilibrium had huge implications for an array of topics. To borrow a quote from that node, Nash equilibrium was described as "the most important idea in noncooperative game theory... whether analyzing election strategies, or causes of war."

That was the first point I wanted to make. Game theory is everywhere. It makes enough sweeping assumptions to satisfy any physicist, and yet it does have applications in the real world and provides us with much interesting mathematics to study.

The second thought that I think is important in relation to game theory is the idea of "solving" games. In this context, I use "game" to mean what is more traditionally considered a game - board games, card games et al. But to solve a game often has two meanings, and I will discuss both since they are both rather interesting.

Often we are satisfied that a game has been solved when a computer can be programmed to play it to a level comparable to the best humans. This is tricky for two reasons. Firstly, because people often find it difficult to articulate exactly what processes they use in choosing a next move, and this explicite explanation is obviously necessary when designing an algorithm. Also, a number of sub-concious checks are performed by humans that discard many theoretically possible moves without much consideration. These checks are more complex to translate to declarative heuristics.

A large number of games have been solved in this way. A simple example is chess. With Deeper Blue, a computer has finally beaten a Grand Master and the chess algorithm has been advanced to such a stage that it surpasses any human player. Quite how it got to that stage is a story in itself, and indeed Kasparov has claimed that the computer was given 'human assistance' at key points in the match. That's for another node, though.

On the other hand, there are games which have not been solved even in this fairly weak sense. Perhaps the classic example of this is Go. The best algorithms for Go can, I understand, still be soundly thrashed by a reasonably highly-ranked Go professional. There are a number of reasons for this weakness in the Go playing standards. As mentioned before, Go is often played on 'instinct' and players with much experience get a feel for good moves quite unconciously. Clearly, there is no such analogue when creating computer programs; further, such a player will find it hard to describe as a procedure the processes involved in selecting a good move. A furthur problem with Go is the fairly ill-defined goal. While the game is in motion, "Territory" is a rather fuzzy notion and, as any programmer will tell you, computers do not get on well with fuzziness. Chess, by constrast, has a very well defined goal - capture the king. Certainly, positional strength in chess is comparable in complexity to that of Go, but at least the end target in chess is somewhat better defined. Therefore chess lends itself, at least in this respect, to being made into a program - Go, however, does not. In addition, the space of possible outcomes is unimaginably large - a 19 x 19 board, with potentially hundreds of stones in play, cannot be over-run by brute processing power. Go does not succumb well to pure 'crunching power', which inevitably increases with each generation of computer - it needs a rather more subtle approach. If a Go program is to ever rival a professional human, many advances in our programming approach will have to come first.

Let us now look at the other sense in which a game is 'solved'. This sense is a much more rigorously defined one, and is therefore favoured by mathematicians, and it is also strongly related to Nash equilibrium. In this use, to solve a game means to define an algorithm that will play absolutely the best strategy all the time. This is often phrased as "an algorithm that cannot be beaten", and in a game devoid of probabilistic elements (as in chess) this is quite true. However, a perfect player of, to take an extreme example, Snakes and Ladders can certainly be beaten. That is not a reflection of the quality of the algorithm; it is an inherent flaw in trying to solve any game with random elements.

For most games, this is quite a huge undertaking. In the simple example of Tic Tac Toe, the space of possible outcomes is relatively small - but it is still a fairly difficult and certainly time-consuming task to devise a perfect strategy. Of course, Tic Tac Toe has long sinced been solved in this strictest of senses, but many other games - even those of perfect knowledge - have resisted attempts to do so.

Returning to the popular topic of chess, we are certainly nowhere near a perfect strategy. The space of possible outcomes is simply too large, and despite the smaller board, may be comparable to that of Go. There is still much argument among chess players as to the best first move, let alone the several hundred that frequently follow. Even simplified versions of chess - discounting complicating technicalities such as en passant and promotion of pieces - are far beyond the computative power available today. Such deep-rooted uncertainty as to 'best strategies' is undoubtedly part of the appeal of chess, and explains how professionals of similar skill can play in vastly different ways.

That said, other games have been solved. To give a recent example, scientists published just this year a solution to the African game Bantumi. This was done in what I consider to be a rather inelegant fashion - in short, the researchers compiled a 17GB database of all possible game scenarios and the best move to follow them. I don't doubt that creating a program to discover these 'best moves' required much skill and effort, but it is perhaps symptomatic of the future of mathematics - likewise the solution to the four colour map problem. Nevertheless, Bantumi has been solved and we know it is possible to create an unbeatable algorithm - genuinly unbeatable in this case, Bantumi being a game of perfect knowledge.

There is one final aspect to this game-solving business. As was recently published in the New Scientist, it has been mathematically proven that Tetris is a 'hard' game. That is to say, even knowing the pieces to be given in advance, there is no algorithm to play the game perfectly. Brings some respite to those of us whose Tetris skills leave much to be desired.

So there we have it. Games that can be solved - Bantumi. Games that can't be solved - Tetris. And finally, games which are as yet unallocated to either category - Chess.

I hope this has broadened your mind of the fascinating topic of game theory. That is all.

Well almost. A quick thanks to JerboaKolinowski, who raised some excellent points about my slightly unfair comparison between chess and Go. That probably arose since I am much less familiar with Go than chess, but I've tried to embrace his insight without having to completely re-write this whole node.