## This issue's *Plus*chat topics

- The Fields Medals — Maths in the media
*Plus*new writers award — last chance to enter- Readers' corner — Why is nim easy and chess hard?

## The Fields medals: Maths in the media

Fileds medallist Grigory Perelman

This summer, with the award of the Fields medal and Grigory Perelman's refusal to accept it (see *Plus* article The Fields medals 2006), maths grabbed an unprecedented amount on column inches in the mainstream press. Understandably, most of the media coverage centered not on the maths, but on the human interest aspect of the story: a
maths genius, living unemployed with his mum, refuses the major honour in his field quoting his disillusionment with the maths community as a reason.

Fileds medallist Terence Tao

The precise reasons for Perelman's refusal are still shrouded in mystery and it is hard to tell what, if any, lessons the maths elite should draw from this snub. What is easier to analyse, and very interesting from the point of view of *Plus*, is the nature of the media coverage. Much of it hardly mentioned the other three medallists, Andrei Okounkov, Terence Tao and Wendelin Werner, let
alone their work. Luckily it is relatively easy to describe the Poincaré conjecture (for his contribution to which Perelman was partly being honoured) by looking at a lower-dimensional analogue and quite a few articles quoted this analogy (though one or two actually got some basics wrong). On the whole, though, most articles carefully circumnavigated the
actual maths. Instead they characterised it by applications, or by the amount of money that solving a problem could win you.

Fileds medallist Wendelin Werner

This may sound like a complaint against the media, but it's not. In truth it can be very difficult for journalists, even science journalists, to obtain information about maths. While news about newly proved theorems and other advances spread like wildfire among mathematicians, there are hardly any channels that bring them to the attention of the wider world. In contrast to other scientists,
most mathematicians, especially those working in pure maths, would never dream of putting together a press release or contacting the media about a new result. They simply are not aware that anyone outside their field might be interested, partly because such interest is seldom voiced by the media. And mathematics has experienced problems with media coverage in the past, when there has been
preemptive publicity of results before sufficient mathematical scrutiny (see *Plus* article Struggling for sixteen). Moreover, there are hardly any publications that summarise maths news in a way that is accessible even to other mathematicians working in other fields, let alone to mainstream science journalists.

Fileds medallist Andrei Okounkov

And without practice, communication between mathematicians and the media can be difficult. Apart from a few well-known names, many mathematicians have not learned how to tone down the technical aspects of their work and capture their bigger ideas in everyday language. This can be very difficult and it might not be possible to describe the ins and outs of all maths research, but, as *Plus*
shows, it can be done in many cases. Journalists are often fixated on applications and assume that these are needed to sell a result to the public. But maybe the public are being underestimated here. After all, many people can understand the fascination with abstract problems and may well take an interest in them for the very fact that they are esoteric.

The channels of communication between the media and mathematics could be improved. Mathematicians talking about their work to laypeople and being proactive when it comes to popularisation could become the norm rather than the exception. In fact, some change might be on its way, as the government bodies that fund maths increasingly require some element of popularisation. And representatives of
the media could signal their interest and willingness to cover maths more clearly, maybe by requiring some expertise in maths from their science editors. In other sciences, journalists can make use of established interfaces, such as news websites, to gain information about the field. In maths *Plus* seems to be the only resource covering news that is aimed at a general audience but gives
some mathematical detail.

The question remains whether the main stream media is the right place to talk about maths. Here at *Plus* we obviously think that the answer is "yes" and since you are reading this, we probably don't have to explain why. Not everyone will be interested, but quite a few people might be. After all, not everyone will read a review of a demanding play or book in a broadsheet; the point is
that it is there for you to read should you want to. If there were a little more authoritative maths coverage, then people might accept the fact that mathematical results may have no applications or may not even be explained in detail. They might still be interested in learning about them simply because maths is part of our culture.

*Plus* new writers award — last chance to enter

Here at *Plus* we know that maths is the language of the universe, and you have just a few weeks to tell us what you've got to say by entering our inaugural writers award. We want to find the people who can bring mathematics to life, so send us an article suitable for *Plus* about any mathematical topic you think the public needs to know about. The
winning entries will be read by an international audience of over a hundred thousand in the December issue of *Plus*, and the winners will receive an iPod, a subscription to *Nature*, and a selection of signed copies of popular maths books by some of the best science writers. The competition closes on September 30th 2006, sdownload your entry pack and get writing!

### Good luck!!

## Reader's corner

*Aviezri S. Fraenkel from the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science sent us his comments on Plus article Practice makes perfect and the book review of Luck, logic and white lies, which both discuss the complexity of chess compared to that of the game
of nim.*

In the game of nim, a finite number of piles of finitely many tokens is given. Two players alternate in selecting a pile and removing from it any number of tokens, possibly the entire pile. The player to take the last token or pile of tokens wins. Nim is easy. Why? Because it has an easy strategy.

Chess, on the other hand, is difficult. Why? Several recent publications, including two *Plus* articles Practice makes perfect and Luck, logic and white lies, have stated that chess is difficult, or *computationally intractable*, because the number of possible moves is astronomical.

The logic is flawed, however. The number of positions of a game of nim can also be very high indeed. In fact, the number of positions in a game of nim consisting of 140 piles of at most 140 tokens each is more than 10 times the number of estimated moves of chess. Yet it's easy to compute the strategy for any such nim game, and a computer can do it in at most a few seconds.

The point is that an efficient algorithm produces more intelligent playing strategies than a dumb search through all possible moves. It enables homing in onto the optimal moves without considering all possible moves!

This observation raises the question whether perhaps also chess has an efficient strategy, and we simply haven't yet found it. However, in the rest of this note we will show that this is highly unlikely.

### Some differences between nim and chess that have mathematical ramifications:

- In nim no repeated positions are possible, whereas chess admits cycles —the same position of pieces can be reached more than once.
- In nim there are no capture moves, which abound in chess.
- Nim is
*impartial*, i.e. the set of moves from any position is the same for both players, whereas chess is*partizan*: the black player cannot move any white piece, and conversely. - Nim has only one terminating state, when all piles are empty. But in chess, every checkmating configuration is a terminating state, and they abound.
- For solving any large system, we strive to decompose it into a number of smaller tasks, and solve each one individually. This can be done for nim, since the piles are distinct. But chess does not seem to decompose into disjoint parts (except some very simple configurations, such as those consisting of pawns and the two kings only).

### Chess has been proved to be *Exptime-complete*

This statement roughly says the following: define chess on a general *n × n* board in any reasonable way, with one white and one black king. Then every conceivable or inconceivable algorithm to decide who can win from an arbitrary mid-chess-position, must necessarily take exponential time in the size of the position!

An exponential function has the form *c ^{n}* where

*c > 1*is a constant. A polynomial function has the form

*n*, with

^{c}*c > 1*a constant. Exponential functions grow very fast with

*n*(exponentially), whereas polynomial functions grow at a moderate rate.

It may be helpful to view the difference between exponential and polynomial functions from a cosmological point of view. Estimates by astrophysicists of the number of particles in the observable universe are currently (as of 2005) on the order of *10 ^{85} < 2^{299}* (see Wikipedia), but

*299*is only 89,401.

^{2}These type of considerations motivate the following convention used in computational complexity. A problem that admits a polynomial time algorithm is called *tractable*; otherwise it is *intractable*.

In conclusion, the provable intractability of chess doesn't exclude the possibility that *8 × 8* chess has an easy *perfect* strategy, which somehow depends on the number 8 or other small numbers, though this seems unlikely. Moreover, it is likely that the world-wide efforts to improve the traditional *8 × 8* computer-chess programs will lead to more defeats of Gary Kasparov and
other world-chess champions.

Yet none of these Turing computer programs can ever determine with certainty who can win from an arbitrary mid-chess-position in *n × n* chess for general *n*. The reason for this is the inherent complexity of *n × n* chess as reflected by its Exptime-completeness — *not* the astronomical number of its moves. It is true that the high complexity of *n × n* chess implies
that it has a very large number of moves, but not conversely! In particular, the large number of moves of *8 × 8* chess, doesn't imply that it is highly complex, which is the main message of this note.

### Reference:

You can find out more in the article *Computing a perfect strategy for n × n chess requires time exponential in n* by A.S. Fraenkel and D.Lichtenstein in the Journal of Combinatorial Theory, Series A (1981), volume 31, pages 199-214.

**Aviezri S. Fraenkel**

If you have anything to say about these or any other topics that might be of interest to *Plus* readers, e-mail plus@maths.cam.ac.uk. Let us know if you are happy for your email and our response to be published in *Plus*. (We may edit emails before publication.)