Computer AI researchers hit the headlines earlier this year when a Go program, Zen19, won a game with a 4-stone handicap against Takemiya Masaki 9p (ninth dan professional). Zen’s positional awareness is good; it’s the least bot-like AI to watch. There are many proprietary Go programs, but much cutting- edge AI research can be found in open source Go programs – and there’s an opportunity to get involved at many levels.
What is Go?
Go is a board game developed in China, where it is called Wei Qi, 2,500 years ago. It combines the simplest of rules with incredibly complex strategy. Two players alternately place black and white stones on a grid of 19×19 lines (smaller boards are used by beginners, and often by Go programs), starting with black. The weaker player may have several stones’ head start (handicap), in which case these black stones are placed on special strategic points.
The game is won by controlling territory. Adjacent stones of the same colour form strings, expanding or joining until they surround empty areas. If the four cardinal points around a stone are surrounded by the other side, the stone is removed from the board. Otherwise the stones stay on the board until the end, when surrounded territory is counted up.
The vast majority of the world’s 40 million Go players are in East Asia, but Go features regularly at Mind Sports Olympiads, and Go clubs can be found across the UK and elsewhere. However, for many people in Europe and America, regular games can only be played thanks to Go servers running on the internet – where as well as other people of all levels, examples of all the current AIs can be found playing.
Geto GOing
Get started with Go on Linux
UNIX users are used to modular programs plugging together. In Go the AI and board are usually separate. The board often works with human and AI players and internet Go servers.
Ubuntu users can open a terminal and type:
sudo apt-get install gnugo cgoban
Alternatively, the Fuego tarball is on SourceForge, along with the GoGUI board.
All modern Go programs can communicate via the Go Text Protocol, and as well as playing against an AI, you can pit two AIs against each other. This can be done either through the GoGUI or the KGS Go Server.
If you want to play against human beings, and not just over the internet, the British Go Association has a list of UK clubs – most big cities and towns have one.
Strategic thinking
While the rules may be simple, the strategy is extremely difficult to quantify. Indeed, it’s not really possible for a computer to reliably assess whether a given position is a winning one or not – although stones may have been removed from the board, this is not as important as the points- based tally in chess.
The challenge is to approach the human ability in pattern-matching. Go is a game of balance. Libraries of blocks enable AIs to make local judgement, but the influence of many nearby weak groups on a string involves matching and discarding too many possible moves.
To put this in perspective, there are 361 points on a Go board – 361 different places where the first stone may be placed; by the fourth move in, there are 16 billion possible board positions, which makes brute force – perfectly suited to chess’s limited board positions – an inadequate tool even with today’s supercomputers. In fact, a 1000 teraflop computer would require more than five days to assess all possible combinations of the next eight moves in order to make a single play [see the ‘Number Crunching’ on Reference link below for more details].
Reference
http://www.linuxuser.co.uk/features/ai-research-goes-open
No comments:
Post a Comment