Archive for the ‘Games’ Category

Computer Chess Software

August 26, 2007

The best chess playing entity in the world today is almost certainly the computer program “Rybka,” developed primarily by International Master Vasik Rajlich.

Rybka currently tops all the computer chess rating lists. Since Rybka is pretty clearly stronger than the Deep Fritz program that defeated World Champion Vladimir Kramnik 4-2 last year, there’s not much doubt that it is better than any human chess player.

Rybka is available as a plug-in chess engine, which means that you also need to have a chess graphical user interface (GUI) to use it. There are a variety of GUI’s available, including the free Arena GUI.

Rybka plays wonderful chess of course. It is free of all the problems that used to plague computer programs–for example it freely sacrifices material for positional compensation. Nevertheless, it’s not the program that I prefer, for a couple reasons.

First, it is only available for Windows (and Linux using Wine), and I wanted a program for Mac OS X. The strongest program for Macs is clearly Hiarcs 11, developed by Mark Uniacke. Although Hiarcs 11 seems to be somewhat weaker than Rybka, it is still stronger than Deep Fritz, and any human being.

gamewin.jpg

Most importantly, on Macs, Hiarcs is paired with the very nice chess “Sigma Chess” GUI. This GUI/engine combination sports the absolutely crucial feature, missing from any version of Rybka, that you can adjust its strength down to any level from world champion to amateur levels as low as 1250 Elo. If you don’t know what 1250 Elo means, you’re probably an amateur who will lose to a 1250–it’s the level amateurs typically reach after playing in tournaments for about one year. (Note: to obtain this feature on the Mac, you’ll need to spend $20 to get the “Pro” version of Sigma Chess, plus $50 for Hiarcs 11. You should also be able to adjust the level of Hiarcs on Windows GUI’s like Arena, although I have no personal experience with this.)

Amazingly, at whatever level you choose, Hiarcs plays a very human-like game. Previous computer programs, when weakened, played poorly strategically, but still did not make tactical errors. A weakened Hiarcs will make tactical mistakes that you can take advantage of, and will also play at an appropriate level of strategic understanding, so there is no particular reason to adopt anti-computer approaches when playing against it.

Of course, Hiarcs comes with many other features, including the ability to use it to analyze your games. Most grandmasters use these programs to aid in their training, and Hiarcs is well-known as one of the best engines to use.

Personally, I also enjoy just watching my Hiarcs 11.2 engine play blitz chess against the 11.1 engine that I previously used. It’s like watching a couple world champions duke it out. I think it’s worth appreciating, that at least for the game of chess, we now have $50-$70 software running on commodity hardware, that essentially passes the Turing test.

If you are a beginner, you might be better off choosing the mass-market Chessmaster, which comes packed with a lot of nice tutorials, as well as some very weak opponents to start with. However, I don’t like Chessmaster as much as Hiarcs because the weakened opponents in Chessmaster have the strong-tactics weak-strategy characteristics of computer programs that become so tiresome after a while.

“German” Games

August 19, 2007


pic149725_t.jpg

I’m a big fan of “German” board and card games. These are strategy games, that play very differently from games such as Monopoly, in that the players will have lots of interesting decisions to make and skill will usually determine the winner. Some German games are no-luck 2-player complete information games like Chess or Go, but most have some luck elements, and they often are designed for more than two players. Some games are big “heavy” games that last two hours (or more), others are small “light” games that finish in 15 minutes.

They’re called “German” games because many of them appear first or only in Germany, where they are particularly popular. They’re also sometimes called “Designer” games, because the designer of the game is always prominently noted.

My favorite designer is Reiner Knizia, who has by now published more than two hundred games. Knizia has a Ph.D. in mathematics, and his games tend to have simple rules and an abstract mathematical element. The picture above shows one of his finest games: “Through the Desert” (also known by its German name “Durch die Wuste.”)

“Boardgame Geek” is a great site for finding out information about games. Aaron Fuegi’s Game Room web-site is another place to find links to lots of useful German game sites, including his ranking list of the top 100 games, based on gamers’ reviews.

The “Amazon.com” for such games is www.funagain.com, where you can buy them or read many reader reviews.

To find people to play with, your best bet is probably to do some research on the internet for game clubs in your area, or to ask at a local game store. People who play German games tend to be very welcoming of newcomers. In the Boston area, there are many gaming groups, which you can find out more about at the “Unity Games” web-site.

A Simple but Challenging Game: Part II

August 15, 2007

Here’s Part I again:

My 15-year-old son Adam likes game theory. He invented the following simple game, and asked me about it when I got on the phone with him while I was away at a conference last month (I’ve simplified and formalized the set-up slightly):

There are two players, each of whom is given a real number which is chosen randomly from a uniform distribution between 0.0 and 1.0. The players know their own number but not their opponent’s. One player moves first and has the choice of passing or challenging. If he challenges, both players reveal their number, and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the first player passes, the second player has a choice of challenging or passing. If he challenges, again both players reveal their numbers and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the second player also passes, both players receive a payoff of 1/2. They play the game one time, and are interested in maximizing their expected payoff.

What is the right strategy? For example, if you received the number 0.17, would you pass or challenge if you were the first player? What about if you were the second player? What would you do if the number you received was 0.0017?

I’ll tell you more in a later post, but for now why don’t you think about it….

Here’s the promised followup:

It is clear that if any player has the advantage, it’s the second player, because he gets some information from the first player, and can use it to make his decision. Nevertheless, the first player can adopt the strategy of always challenging, and thereby guarantee that he wins half the time. So apparently he should always challenge. This is the answer that was given by “Optionalstopping” in the comments. The same answer was given to me by the evolutionary game theorist Arne Traulsen (who has recently worked on a ground-breaking theory for the emergence of punishment), after I asked him about the game at a lunch conversation.

There is another way to arrive at the same answer. Assume that each player chooses a strategy parameterized by a single value; if he receives a number above that value, he challenges, while if he receives a number below that value he passes. If you work out the Nash equilibrium (basically, that means that both you and your opponent pick the strategy that gives you the best payoff assuming that the opponent is maximizing their payoff), you’ll find (I won’t bore you with the math) that the value for both players is zero–they should always challenge. My son Adam gave an intuitive version of this argument, without the math. Of course it’s true that probabilistic strategies are also possible. I haven’t proven it, but I strongly doubt that introducing probabilistic strategies will change the result that the Nash equilibrium is to always challenge for both players.

So at first I thought the matter was settled. But still, there is something very weird about this result. Would you really challenge if you were the first player and you received a .001? Would you really?

And what if you were the second player, and the first player passed, and you had a .000001? You know that the first player is not “following the rules” of Nash equilibrium. Are you really going to challenge because Nash tells you to? It’s obviously a crazy result! There must be a hole in the arguments.

So what’s wrong with the above arguments?

First let’s start with the Nash equilbrium arguments. By the way, many authors use the term “rational” for players that use strategies dictated by Nash equilibrium arguments, but I think “rational” and “irrational” are excessively loaded terms, so I prefer to instead say that a player that follows a strategy dictated by Nash equilibrium arguments is a “Nashist.”

If you are the second player, and the first player has passed, you can deduce that the first player is not a Nashist. So in order to make a correct play (maximize your expected winnings) you need to choose some probability distribution for what the first player’s strategy is, and then compute whether you will win more or less depending on whether you challenge. There doesn’t seem to be any obvious way to choose the probability distribution for the first player’s strategy, but you can definitely say that he is not certainly a Nashist! A Nashist is stuck (by definition of being a Nashist) believing that all other players are always Nashists, even in the face of clear evidence that they are not (you see why I don’t like to call Nashists “rational”) and would choose the strategy that followed from that obviously wrong belief; he would always challenge as the second player.

A non-Nashist, on the other hand, can come up with a reasonable probability distribution for the first player’s strategy, and come to the conclusion that he should pass if he is the second player and he has a .000001.

OK, so we can see why the second player might want to pass if he receives a .000001. What about the first player: is it wrong to be a Nashist? Should you pass or challenge if you get a .001, or a .000001, or a .000000001? A Nashist would be compelled, by the force of his “idealogy,” to challenge in each case. But you can make a good argument that that’s wrong. Instead, let’s say I am the first player and I have a .000001. I know that if I pass, the second player will be able to deduce that I’m not a Nashist, and will go through the argument given above for the second player. Now “all” I have to do is form my probability distribution for what his probability distribution of my strategy will be, and compute whether I will have more chance of winning depending whether I challenge or not. Again there’s no obvious way to choose these probability distributions, but it seems pretty clear to me to that reasonable probability distributions will give a result that says don’t challenge if you are the first player and you have a sufficiently low number.

Well what about the other argument, that says that the first player should always challenge, since he is at a disadvantage and if he always challenges, he’ll win half the time? It seems paradoxical to think that there is a strategy that can do better than winning half the time for the first player.

Of course, all Nashists will always win exactly half the time, whether they play first or second. If you are playing against someone who you know is a Nashist, it actually doesn’t matter what you do! But suppose instead that you are playing against an ordinary human. You should play forming the best possible probability distribution of what they will do. Many humans will challenge if they have a number above .5 and pass otherwise, whether or not they play first (a very bad strategy by the way). It is perfectly possible, indeed likely, that playing against a population of ordinary humans, there exists a strategy that wins more than half the time for the first player. I can’t prove that strategy exists by arguing in this way (one would need to run experiments to determine the probability distributions of strategies, and then it would be easy to compute), but I’m actually pretty confident that it does exist, and I’m also pretty confident that the strategy involves passing when you are given a .000001 as the first player.

So I don’t believe either argument for always challenging holds up, which is comforting, because always challenging does seem intuitively wrong. Unfortunately, I can’t tell you exactly what the optimal strategy is either, at least until you tell me what the true probability distribution is for player strategies.

images1.jpg

By the way, Arne recommended that I pick up Game Theory Evolving, by Herbert Gintis, for my son. It’s a wonderful book, full of interesting games and solved problems in game theory. Adam and I both love it. Gintis gives other examples showing that Nashists (he calls them “self-regarding agents”) can choose bizarre strategies, including “Rosenthal’s Centipede Game:”

The players, Mutt and Jeff, start out with $2 each, and they alternate rounds. On the first round, Mutt can defect by stealing $2 from Jeff, and the game is over. Otherwise, Mutt cooperates by not stealing, and Nature gives Mutt $1. Then Jeff can defect and steal $2 from Mutt, and the game is over, or he can cooperate and Nature gives Jeff $1. This continues until one or the other defects, or each player has $100.

In this game, the Nash equilibrium, obtained by induction by working backwards from the end of the game, when it is clearly “correct” to defect, is that Mutt should immediately defect on his first turn. So that’s what a Nashist would do, but fortunately humans are much more “rational” than Nashists!

ChessVibes

August 10, 2007


persconfkramnik.jpg

ChessVibes is a great chess web-site/blog with lots of interesting content. A highlight from the past year is their coverage of the Wijk aan Zee tournament held in January 2007, where most of the strongest players in the world played. They have videos taken from the post-game press conferences; in each video, the winner explains his victory for some 20-30 minutes.

Here are links to a couple of the best videos:

Kramnik (the world champion) explains his victory over Anand (the highest rated player today).

Svidler (ranked #12 in the world, and one of the most entertaining of the world elite) wins against former world champion Topalov after Topalov cracks in a better position.

If you like these, you can easily find lots more (with Anand, Topalov, Aronian, etc. explaining their wins) from that tournament.

A Simple but Challenging Game, Part I

August 9, 2007

My 15-year-old son Adam likes game theory. He invented the following simple game, and asked me about it when I got on the phone with him while I was away at a conference last month (I’ve simplified and formalized the set-up slightly):

There are two players, each of whom is given a real number which is chosen randomly from a uniform distribution between 0.0 and 1.0. The players know their own number but not their opponent’s. One player moves first and has the choice of passing or challenging. If he challenges, both players reveal their number, and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the first player passes, the second player has a choice of challenging or passing. If he challenges, again both players reveal their numbers and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the second player also passes, both players receive a payoff of 1/2. They play the game one time, and are interested in maximizing their expected payoff.

What is the right strategy? For example, if you received the number 0.17, would you pass or challenge if you were the first player? What about if you were the second player? What would you do if the number you received was 0.0017?

I’ll tell you more in a later post, but for now why don’t you think about it….

Marvel Trading Card Game / Magic the Gathering

August 7, 2007


61uwcobzlql_aa280_.jpg

Are you looking for a challenging strategy game in a portable format? If so, this is the game for you. This is an example of a remarkable piece of work that is being seriously under-appreciated.

A little background is in order. Collectible card games (now called “trading card games”) began in 1993 with “Magic the Gathering,” a game designed by Richard Garfield, who was just then earning his Ph.D. in mathematics at Penn.

The basic idea of Magic the Gathering is that you build your own deck of cards (which set of cards you can select from depends on the precise rules of the format you are playing) and then “duel” against an opponent who has built his own deck.

In a duel, you start with 20 “life” points, and the objective is to reduce your opponent to zero points before they do the same to you. You play some of your cards as “creatures” which attack your opponent or defend you against your opponent’s creatures. There are other cards that act as “sorceries,” “instants,” “artifacts,” or “enchantments,” which are “spells” that you cast and have all sorts of different effects, like killing creatures, reducing your opponent’s life, making your creatures stronger, and so on. (There are many other possibilities–there now exist roughly 10,000 different cards, so you can appreciate that they do many different things.) Each creature or other spell is paid for with “mana” that you usually obtain from your “land” cards.

When you play a “spell” it is put on a “stack,” and your opponent has a chance to respond to it before it “resolves.” Much as in a computer stack, the spells can pile up, and are resolved in last in, first out, order. Since many of the cards have effects which violate the normal rules, it can be very complicated to keep track of what is going on.

The key to winning in Magic is to design a deck where your cards act synergistically with each other, and then to be able to take advantage of all the subtle interactions and timing effects. It’s incredibly difficult and challenging to play well, no less challenging than Chess, and like Chess, it can be played either casually or in serious tournaments.

If you want to learn more about Magic, you should visit www.magicthegathering.com, which has a vast amount of information. You should probably start with the “Magic Academy” articles, and this article in particular.

250px-magic_players.jpg

I personally played seriously between 2004 and 2006, and my highlight was reaching 2nd place in a rather serious “Pro tour qualifier” tournament in 2005 (see the picture above for what one of these tournaments is like) with my Blue-White Ninja deck (although in that link, the Mike Flores gives me too much credit for the deck design; I copied an obscure but brilliant deck I found on the internet, a practice referred to as “net-decking”). For the last year, though, I haven’t played much, and my son Adam has seriously surpassed me in in both playing and deck-designing ability.

Magic the Gathering has been fantastically popular for a serious card game, and has spawned many imitations because of its ridiculously successful business model. Because the cards that are legal to build your decks with keep changing, the game keeps evolving (which is nice), but that means you have to keep spending money to buy more cards (which may not be so nice for you, but it is certainly nice for the publishers.) Actually, it’s a little more complicated than that–they’ve cleverly arranged it so that your old cards are still legal for some formats, and since they are no longer printed, those old cards tend to hold their value pretty well. And many Magic players actually quite enjoy collecting and trading their cards.

Anyways, most of the imitations, like Pokemon card game, Yu-gi-oh, or Duel Masters, are vastly simplified games targeting a younger set. (Most Magic players are males between the ages of 15 and 30.)

One imitative game, which at least roughly equals Magic in complexity and interest, is the “Marvel Trading Card Game” (also known as “Versus System.”) The theme is a little different; it has superheroes battling villains instead of monsters fighting and wizards casting spells and so on, but it works very similarly. Forgetting about the theme, and judging them strictly as abstract games, there’s little to make one prefer one game very much over the other–they are clearly closely related, and the competitive Marvel scene is dominated by Magic players.

Unfortunately, no versions of Magic have come out for portable game systems. There was a computer game back in 1998, but its AI was really pretty bad. There is a version of Magic the Gathering that can be played online, but you need to buy the cards for the same price as you pay for real cards. (You are able to play for free against other beginners with simple starter decks.) You can also play for free online using the excellent Magic Workstation program, but Magic Workstation doesn’t enforce the rules, so you need to be a relatively experienced player to use it.

Probably Wizards of the Coast (the publishers of Magic) haven’t wanted to cut into their card sales with a computer or portable game that effectively gives you a huge number of cards to play with for a relatively small price, or possibly they don’t believe that it’s possible to program an AI that plays Magic competently.

There have been numerous Yu-gi-oh and Duel Masters games for Nintendo DS’s and Gameboys, but I find those games to be distinctly inferior to Magic.

Anyways, we now have “Marvel Trading Card Game” for the DS, PSP, or PC. I have the DS version for my DS Lite. To play the game on a DS, you hold your DS sideways like a book. The game board is shown on the touchscreen, and you poke at your cards with the stylus to play them. On the other screen the currently selected card is shown in detail so that you can read all of its rules.

You can follow two “paths” through the game, one where you play with superhero cards, and one where you play with villain cards. When you win duels, you are rewarded with new cards, which you can use to make a more powerful deck, which you will definitely need to do, because your opponents’ decks will get more powerful. The game includes about 800 different cards in all. There are also tutorials and very challenging puzzles.

In general this is an extremely challenging game! The AI is very impressive (and it gets some advantage from having slightly better decks than you). You can win, but you will need think hard and play very carefully. After the first couple opponents, you start facing good decks, and I started losing duels more often than winning them. But since I can always identify my errors when I lose, it doesn’t feel unfair, just challenging. Each duel will take about 40 minutes (Versus duels tend to last longer than Magic duels, which typically only take 20 minutes). You can also play online with other players, but I haven’t tried that, because if I wanted to play online, I would just use Magic Workstation.

The game has been getting mediocre reviews (they mostly complain that the game is so hard; another problem is that the music is pretty bad–I agree that you should turn off the sound), so my viewpoint is obviously a minority one. But nevertheless, if you like Magic, or want to see what serious trading card games are about, or want something that will make the time fly during a long plane or train trip, I recommend you pick this up.

Zillions of Games

August 2, 2007

Visit Zillions of Games

If you like abstract games, especially chess variants, you should enjoy Zillions of Games. It’s quite an amazing piece of software; a piece of AI technology that I actually would have not thought possible.

Games are defined using a rules file (written in a Lisp-like language), and then a generalized alpha-beta search engine is unleashed. Basically, it works best for Chess and its many variants, but it plays a really surprising number of games very well. It comes with over 350 games and puzzles, and you can download thousands more.

It’s not that hard to modify existing rules files to define new games; my son was interested in having an opponent for a game he invented and we were able to modify an existing rules file to play his game in less than an hour–and it played very well.

Naturally, it doesn’t play all games as well as humans, but it plays so many games so well (with adjustable levels to make a fair fight if it’s too good) that one can’t complain. Unfortunately, it’s only available for Windows computers.