The Standing Invitation

Posts Tagged ‘Mathematics

Xiangqi

with one comment

We like board games here at the SI, and the latest craze sweeping the office is xiangqi – Chinese chess.

Xiangqi is played on a nine-by-nine grid, and is similar to Western chess in many ways: it is turn-based, zero-sum, and is won by checkmating the opponent’s king (or ‘general’). It is easy to see how the two games might share a common ancestor. Many of the pieces move in similar ways – the pieces called ‘chariots’ move exactly like castles, the ‘horses’ almost exactly like knights, the ‘soldiers’ and ‘elephants’ a little bit like pawns and bishops. Some pieces have no equivalent in Western chess – ‘fireworks’ capture by jumping over exactly one other piece, and ‘advisors’ protect the general – but, rather pleasingly, once the pieces’ moves have been learnt, the tactics and strategy of chess carry over very well. If you are good at chess, you’re not too bad at xiangqi either, even if you don’t know it yet.

One important difference is that the xiangqi’s general is confined to a small space – a three-by-three grid. This has the effect that checkmate is much easier to achieve in xiangqi than in chess.

We may define this exactly. Consider the set of all possible combinations of up to 32 pieces on an 8×8 chessboard ­– a huge number, call it C. Now imagine the much smaller (though still gigantic) set of possible combinations of pieces that are checkmates for back. Call this smaller number C+. Now consider the equivalent numbers in xiangqi – the set of all possible positions, X, and the subset of all possible checkmates, X+. When we say that checkmate is easier in xiangqi than in chess, we mean that (X+ / X) is much bigger than (C+ / C) – checkmates make up a much bigger proportion of the available positions.

We’re talking about huge numbers when we discuss X and C, but still finite – Dennett fans would call them Vast. The number of possible positions is an upper bound, a kind of mathematical worst-case scenario. In fact the number can be made smaller by realising that some positions are unreachable. In chess, the set of positions in which a pawn sits on the first row may be removed from C; likewise in xiangqi the positions in which the two generals illegally face each other. These legally accessible positions are called the state spaces of xiangqi and chess.

State space sizes are difficult to calculate. People begin with an upper bound, then whittle this Vast figure down by working out the mathematical consequences of the games’ rules. Exact answers have been obtained with simple games like noughts and crosses: 765. Chess’s has been estimated as 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, xiangi’s as ten times bigger, but take these as approximations. The set of all possible games, of course, is much, much higher.

Don’t bother playing draughts, by the way. It’s been solved. The entire decision tree of a game draughts has been worked out, in 2007. From the starting position, draughts will always end in a draw if played perfectly. The game only becomes interesting because people make mistakes.

REFERENCES

http://fragrieu.free.fr/SearchingForSolutions.pdf

http://en.wikipedia.org/wiki/Solved_game

Written by The S I

November 2, 2011 at 11:59 pm

Infinite Beauty

leave a comment »

In the last post I described one of the uses of large prime numbers, and added a link to the biggest yet known. It is a Mersenne prime, meaning that it is 2 to the power of another prime, minus one, and can therefore be written as 243112609-1; fully expanded, it is over twelve million digits long.

So large prime numbers are useful. And fortunately, they are an inexhaustible resource. When I say we know this for certain, I really do mean it. We are more certain of the infinitude of primes than we are of the size or age of the universe; more certain of it than we are that the Earth revolves around the sun.

Just as there are some books which everybody ought to read, there are some solutions to problems that are just so neat that it seems a shame not to know them. Euclid’s proof, devised over two thousand years ago, is a real glimpse of mathematical beauty.

How do we know that there are an infinite number of primes? Imagine that we don’t. We might think that the prime numbers stop after a while, and that every subsequent number is nonprime. If that were the case, there would have to be some highest-possible prime, the largest of them all. Call this ultimate über-prime P.

P stands at the head of a gigantic list of prime numbers, going all the way from P to the smallest prime, 2. We might arrange these numbers in order ­– write them down on a piece of paper longer than the universe.

2, 3, 5, 7, 11, 13 … and so on for millions of light years of paper until finally … P

This piece of paper contains an exhaustive list of every prime number that exists. Now imagine taking all the numbers on this list and multiplying them together, to give an even more unimaginably huge number, R.

2 x 3 x 5 x 7 x 11 x 13 … x P = R

R ends up being a number so huge that P seems tiny ­– but we know for a fact that R is not a prime number. We know this because R, divided by any prime number on our list, will leave no remainders. R is not prime because it is a multiple of 2 ­– and of 3, and of 5, and of 7, and even of P

Now take this mind-blowingly, egregiously vast number R and add 1.

R + 1 = Q

What do we know about Q? Well, we know that if we divide it by 2, we’ll get one left over ­– the one we’ve just added to R. And if we divide it by 3, we’ll get one left over. And by 5, one left over… all the way up to P. If we divide Q by P, we’ll get one left over.

Which means that Q is a prime number ­– much, much bigger than P, the number we assumed was the largest prime. And if we take Q to be the largest prime, essentially making it into our P, we know there will be an even bigger Q to dwarf it.

When it comes to arguments, what could be more decisive ­– or as elegant – as this?

 

 

REFERENCES

This proof and others are discussed in G H Hardy’s classic essay on mathematical beauty, A Mathematician’s Apology. The full text can be found here.

Written by The S I

August 29, 2011 at 11:59 pm

Critical Factors

leave a comment »

Prime numbers are the building blocks of integers. Any positive integer is either the product of two or more prime numbers, or a prime number itself.

6 is the product of 2 and 3.

943 is the product of 23 and 41.

44,467 is the product of 53 and 839.

These numbers each took about ten seconds to calculate ­– I just drew prime numbers out of a list and multiplied them together.

So tell me: which pair numbers did I multiply together to get the number 47,124,299?

There is only one answer to this question, and in one sense it is easy to find: simply divide 47,124,299 by each prime number in turn; if the result is itself prime, there is the answer. But armed with the same tool as me – a pocket calculator – it would take you days to find the answer to a number I generated in seconds. If you and I were in a race, I would have a clear advantage ­– and the bigger the primes I chose, the harder your job would be.

The fast factorisation of numbers has been a problem for thousands of years, and we still aren’t very good at it. Granted, my computer could find the prime factors of 47,124,299 in a nanosecond or two, but this is a measure of computational speed, not cleverness. It is still exhaustively checking off the primes, one by one, just as someone would have done on paper a thousand years ago.

This asymmetry is exploited in the area of public-key cryptography, one of the most powerful forms of encryption that exists that doesn’t involve weird quantum effects of spinning electrons.

If you want to use public-key cryptography, you choose two large prime numbers ­p and q – gigantic numbers, hundreds of digits long – and multiply them together to create an even bigger number, N. You would then be free to advertise this number N to anyone who wants it; one might list different people’s Ns in something like a phone book, free for people to look up.

To send you a message M, I would have to look up your N, and perform a simple calculation involving M and N. The outcome of this one-way function is the encrypted message. This can then be transmitted to you, and nobody ­– not even me – could convert the encrypted message back to M.

The only person who can read the message is you, because you know what p and q are. You alone on Earth know the prime factors of N, and that means only you can perform the reverse maths that decrypts the message.

Of course, N is public, and anybody could work out p and q from N simply by exhausting the possible primes. As we have seen, this is simple, but time-consuming: at present sizes of commercially available ps and qs, factorising an N would take the combined computing power of the entire planet several billion years.

REFERENCES

Simon Singh, The Code Book

At the time of writing, the largest known prime was 243112609 – 1. The number can be found written out fully here.

Written by The S I

August 27, 2011 at 11:59 pm