The Standing Invitation

Posts Tagged ‘Computers

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

Advertisements

Written by The S I

November 2, 2011 at 11:59 pm

A Toy Universe

leave a comment »

Conway’s Game of Life is truly a wonderful thing. It’s a computer program that models a whole universe, albeit a very simple one.

(There’s a Java version here. Have a play with it. If you want to do more, you might download Golly, found here.)

This simulated universe is two-dimensional, and consists of millions of cells arranged in squares. Each cell can be either ON (black) or OFF (white). At the start of the simulation, the user clicks some cells on or off in whatever pattern he likes, then presses ‘GO’. The computer does the rest, playing out the universe’s future step by step.

These black and white cells are governed by four simple rules:

1)   Any ON cell with fewer than two ON neighbours turns OFF in the next instant (underpopulation).

2)   Any ON cell with two or three ON neighbours remains ON in the next instant (survival).

3)   Any ON cell with more than three ON neighbours become OFF (overcrowding).

4)   Any OFF cell with three ON neighbours becomes ON (reproduction).

That’s all: these are the laws of physics of this simulated universe, much simpler than our laws about gravity and entropy. These rules are just as unbreakable in Life as in our world; it is a deterministic universe, and in that sense limited if you want to see it that way. But look what can be done within these limits.

Everything that happens is the result of these simple rules operating on cells, turning them ON or OFF, and on that level the game is uninteresting: we always know what will happen. But zoom out a bit and the cells become too small to see. Instead we see patterns of cells. Some of these patterns are not long-lived and disappear or change dramatically; but others, the interesting ones, preserve their identity, and have emergent properties of their own.

Take the ‘glider’ shown above. When this pattern appears, it cycles through four steps, eventually returning to its original shape but shifted one cell down and to the side. You could of course see it as individual cells turning ON and OFF, but it looks quite a lot like a persistent, self-contained object that flies diagonally across the screen until it hits something.

The parallels with our own world, our own lives, are striking. The atoms that make up our bodies come and go, and yet we remain. We are the patterns, not the atoms that we happen to consist of at the time.

There are people, both hobbyists and serious mathematicians, who spend their time charting the ecology of these toy universes. They have discovered or made ‘guns’ that periodically spit out gliders, or ‘puffers’ that move in one direction emitting a stream of debris.

What’s even more fascinating is that these ‘guns’ can send binary information to each other in the form of a string of gliders (a glider representing 1, the absence of one representing 0). The gliders can interact to produce logical operators – AND gates, XOR gates. In fact, it has been shown, mathematically, that it is possible to build a whole computer in Life.

Of course such a computer would be gigantic, consuming millions or billions of cells. But just think: this computer would itself be capable of running a version of Life. A simulated world inside a simulated world…

REFERENCES

http://en.wikipedia.org/wiki/Conway’s_Game_of_Life

Written by The S I

September 4, 2011 at 11:59 pm