Games and Mathematics by David Wells Read Free Book Online

the game stops.
    After agreement that the game has ended, each player removes any opposing dead stones from his territory and adds them to his prisoners.
    Prisoners are then placed in the opponent's territory, and the remaining points of territory are counted. The player with more territory wins.
    If both players have the same amount the game is a draw, which is called a ‘ jigo ’.
     
    Like chess pieces, the pieces at Go can also take any form. When I learned to play in the 1960s good stones and boards were hard to come by in the West so we used a kind of sugared almond, painting half of them black. The shape was close to Japanese standard stones which are made of shell or slate, but theweight, colour and feel were not right, but that mattered not at all because we used them as Go stones, so they were Go stones. This also works the other way round. When John Horton Conway was inventing the Game of Life with no computer to aid him, he used Go stones on a Go board to represent the state of the ‘game’.
    Figure 2.11 Opening position of Go game
     

     
    Because the Go board is so large that players have to rely more on intuition and judgement than chess players, efforts by artificial intelligence enthusiasts to program computers to play Go have been disappointing.
    The original game of choice for the Artificial Intelligence community was chess. In 1957, Herbert Simon, pioneer of cognitive psychology and artificial intelligence and later a winner of the Nobel prize for economics, predicted that a computer would be world chess champion within ten years. A bizarre blunder, based on the naive idea that computers would soon be able to imitate the thought processes of the human brain whose complexity Simon grossly underestimated. Forty years later, Gary Kasparov did lose a game to the computer program Deep Bluebut it did not play in the style of a human player. The artificial intelligence of Deep Blue was just that – artificial – and the goal of simulating the workings of the human mind proved much further away than Simon and his colleague Alan Newell realised [Wells 2003 : 159–60].
    Computer analysis of Go lags even further behind and there is no prospect in the near future of a Go program beating a top professional. From 1985 to 2000 when it lapsed, a prize of $1000000 was offered by Acer Incorporated and the Ing Chang-Ki Wei-Chi Educational Foundation for the first Go program to beat a Go professional. No way! The current strongest Go
    Combinatorial game theory (CGT)
    Some games are so simple, unlike chess and Go, that they can actually be solved completely by mathematical arguments. Nim is the most famous example. Your start with several piles of stones or other objects. Players take turns to select one of the piles and take any number of the objects in it, from a single object to the whole pile. Two rules exist for deciding the winner. Either the winner is the player who does not take the last object, or the player who does.
    Nim was completely ‘solved’ by Charles Bouton in 1901, meaning that he showed which player should win, given a certain set of piles to start with, and how that player should play to guarantee the win. Like the Tower of Hanoi, the solution involves binary numbers.
    Nim has the important feature, shared with all the games we have presented, that the position is completely open to both players, unlike card games or poker-type games whose analysis therefore involve probabilities. The latter have been analyzed by mathematical game theory which has been applied to economic competition between firms, a nuclear arms race, the sale of licences for mobile phones operators and other more-or-less realistic scenarios.
    Nim is important for another reason. In the 1930s Roland Sprague and Patrick Grundy proved independently that all impartial games – meaning that for every position of the game, the same moves are available to both players – are equivalent to some game of nim, so the variety of