Wednesday, December 23, 2009
When computers finally managed to beat us at chess, a game of ingenious human invention, we did not say they were now officially smarter than us. What we did was give computers another game - another puzzle to struggle with.
Go is a board game that is a magnitude more complex than chess. Whereas computers could memorize well studied opening books for chess, such a strategy is unmanageable for Go, since there are 361 possibilities... for the first move alone. Today's fastest computers with the best Go algorithms are still beaten by human players with a few months of experience - mere novices.
I believe that computers will one day manage to beat us at Go. But that is a discussion for another time. Now I want to talk about what game, what puzzle we will toss future-computers after that, to assuage ourselves that NO - they are still not smarter.
Settlers of Catan is a board game that is a magnitude more complex than Go. Whereas future-computers only had to think about winning or losing for Go, a binary 1/0 that they are familiar with, such a strategy simply doesn't work for Settlers, since bartering between players involves the hazy variables of human psychology that computers are ill-equipped to define. First there is the game. It is played on a board, which has over a million different possible configurations - and that's before any player has had a turn.
Then there is the meta-game. It involves players bartering with each other, forming alliances, and knowing when to stab their former partners in the back. To give you an example of how complex the thought process can be, we need to take a quick diversion.
From personal experience, I've seen a human player propose an ingenious trade, that would have given her an enormous advantage. To fully understand the significance however, you first need to understand more about the game. Victory in Settlers is achieved when a player has 10 victory points. There is a longest road development card, which is awarded to whichever player has the longest road* of at least 5 segments. It is worth 2 victory points.
You also need to understand more about this particular instance of the game. There were four players. The human player and another player (let's call him the opponent) were both just mere points away from victory. One of the two other players currently held the longest road card. However the opponent had two large sections of road, and if he was able to connect them, held a good chance of gaining the longest road card for himself.
The human player proposed that she refrain from building a road at a position where it would block the opponent from connecting his two road sections in return for him giving one of his resource cards on every turn to her for the rest of the game (like a tax). Right as the opponent was about to agree to this outrageous deal (remember he still might not have gotten the longest road card), the human player realized it was better to take away all possibility of the opponent gaining the longest road card, and she built the road anyway.
What will happen when future-computers beat us at Settlers of Catan? That's when we can say they are officially smarter than us - and be right.
* The length of a road is the longest possible segment, not counting branches.
Posted by Andy Hou at 2:52 AM