Archive for the ‘Games’ Category

Connect6

October 23, 2007

pic48005_t.jpg

I’ve been enjoying playing the game Connect6 with my son Adam. The game was invented and introduced by Professor I-Chen Wu, from National Chiao Tung University in Taiwan. Connect6 is played with a Go board and stones. The object is to place six stones in a row, diagonally, horizontally, or vertically. On the first turn, Black places a single stone; after that each player places two stones per turn. Because each player will always have placed one more stone than his or her opponent after each turn, the game appears to be balanced.

One potential concern about this notion of balance is that perhaps the second player should place his or her stones far from the first stone, to get a two-stone advantage somewhere else on the board, and possibly forcing the first player to follow in that part of the board. Fortunately, Wu and a colleague demonstrated that this initial break-away strategy is unlikely to be good for White in this paper.

Anyways, it’s not clear whether with perfect play the game should be a win for the first player, a win for the second player, or a draw (with neither player ever able to achieve six-in-a-row.) If I had to guess, I would venture a draw, even on an infinite board, but on the other hand my actual games have all ended in victory for somebody.

The game is very similar to Gomoku (also known as Connect 5), where one tries to get five stones in a row, but each player only places one stone at a time. Of course, that game favors the first player, and in fact it has apparently been demonstrated that the first player wins with perfect play.

Renju is an older and much less elegant approach to balancing Gomoku. In Renju, the first player is restricted from making moves which make certain types of threats. Looking at all the complications in the Renju rules, I find it surprising that it took so long for Connect6 to be introduced.

In fact, aside from the issues of fairness and elegance of rules, I also find that Connect6 has a more dynamic feel than Gomoku or Renju; I definitely prefer it.

Because of the large number of possible moves each side can make each turn, and the difficulty of evaluating a position, it’s not easy to program a computer to play Connect6 well; I don’t think any programs exist yet that play as well as humans. You can play Connect6 against some relatively weak bots and other humans at Vying Games, which also features other interesting turn-based strategy games (currently Checkers, Pente, Keryo-Pente, Phutball, Breakthrough, Othello, Kalah, Oware, and Footsteps).

Advertisements

Enhanced Chess

October 8, 2007

For a long time, Chess was considered the “ultimate test of cerebral fitness,” as the 1980’s song “One Night in Bangkok” proclaimed. Its popularity probably peaked in 1972, during the Fischer-Spassky world championship match which seemed to capture the interest of the entire world. Lately, however, its popularity has seriously declined, because of a number of factors:

1. Humans are no longer the best Chess players in the world. It’s somewhat depressing to study and play a game when you know that a program you can buy for $50 can out-play you, or any other human.

2. Chess opening theory has become extraordinarily detailed, and onerous to study. Very often, grandmaster games begin with 20 or more known theoretical moves. Moreover, nowadays most new theoretical novelties are suggested and analyzed by computer programs used by top players before their games. If a player does not keep up with opening theory, he will be at a disadvantage, but many people find the prospect of studying openings in this way increasingly dehumanizing.

3. Most games between top-flight Chess grandmasters end in a draw, simply because Chess is almost certainly a draw with best play. To take one example, Kramnik won his match against Kasparov in 2000 with 2 wins, no losses, and 14 draws.

I want to propose here a Chess variant, that I developed with my son Adam, that addresses all these problems. We call this variant “Enhanced Chess.” In Enhanced Chess, there are no draws, there is no opening theory (or endgame theory) to study, there is no advantage for the first player, and humans should out-class computers for a long time to come. The game is extremely skill-intensive; the more imaginative and “cerebrally fit” competitor will definitely win the game.

The game combines a couple existing Chess variants. The first of these variants is “Bughouse Chess.” Ordinary Bughouse Chess is played by two teams of two players each. On each team, one player plays White and the other plays Black. When you capture one of your opponent’s pieces, you hand it to your partner, who can drop it on his own board rather than making an ordinary move. Pawns may not be dropped on the first or eighth rank, but otherwise there are no restrictions on drops; you can even checkmate with a dropped piece. When a pawn reaches the eighth rank, it is promoted normally, but if the promoted piece is captured, it turns into a pawn again. The game ends when one of the kings is checkmated.

In ordinary Bughouse you may communicate freely with your partner. It is normally played with fast time controls (e.g. 5 minutes for each player for the game) as a very amusing social game with lots of trash-talk. Here’s a video of a typical Bughouse game, where the only unusual thing is that one of the players (at the back left) is Levon Aronian, one of the strongest Chess grandmasters in the world, and a participant in the 2007 World Chess Championship:

In Enhanced Chess on the other hand, a single player will control both the boards on his side, so that the game is again a two-player game. Moreover, the moves are made in a strict turn-based order. First Player 1 makes a move with White, then Player 2 makes a Black move followed by a White move, and then the players continue to alternate, always making a Black move followed by a White move. Notice that because Player 1 only makes one move on his first turn, and then Player 2 makes two moves, there is no obvious advantage to going first or second.

Time controls can be as slow as you like; Enhanced Chess is meant as a serious game.

Turn-based Bughouse is a good game, but if it became standard, it would quickly suffer from the problem of excessive opening theory. But that problem can be remedied by using the idea, proposed and popularized by Bobby Fischer for ordinary Chess, of randomizing the initial position. In Enhanced Chess, the initial random position must be identical on the two boards, as in the following diagram of an initial position:

enhancedchess001.jpg

Chess with randomized initial positions (sometimes called “Fischer Random Chess” or “Chess960” because of the 960 legal starting positions) is already a somewhat popular variant. Levon Aronian is the current “world champion” of this variant, having beaten Vishy Anand (the current world chess champion in ordinary Chess) in a short match in 2007.

One difficult point in Chess960 is how to handle castling. In Enhanced Chess, we propose to handle this problem by simply forbidding castling. Castling is usually of dubious utility in any Bughouse Chess variant in any case, and there’s no reason to carry all the complicated rules baggage. There would also be more than 960 legal starting positions, because while Chess960 tries to ensure that the kings start between the rooks, in Enhanced Chess that is not necessary. (We still required that the two bishops on each side start on opposite color squares).

It would in fact probably be sufficient if at the beginning of the game, the players alternated on deciding the positions of one piece at a time. For example, my first move would decide that the Kings go on b1 and b8. You then decide that one of the Knights should be placed on f1 and f8, and so on (one needs to forbid placements that place the bishops on the same color square or leave no option but for that to happen in the future). This version would remove any element of luck from the game, and I doubt that studying openings would pay with even this amount of “pre-processing.”

Making a pair of moves which repeats a position (on the combined boards) is forbidden in Enhanced Chess, and stalemate is a loss. These rules remove any theoretical possibility of a draw.

It is interesting to speculate on what the “correct” result would be in Enhanced Chess if God played against God. There is no obvious end to the game until positions start repeating. It’s clearly just idle speculation, but how many moves do you think would need to occur in the perfect game tree before one side won?

In practice, I don’t think that Enhanced Chess games would typically last any longer than ordinary Chess games, although a big difference is that players would definitely need to rely much more on intuition and much less on knowledge and calculation. One other big difference, which would definitely be a drawback for some players, is that reduced-material end-games would cease to exist. Enhanced Chess would be much like Shogi (Japanese Chess) on steroids, but maintaining all the familiar pieces (and removing the advantage of moving first).

Finally, I should address why I think computer programs will play Enhanced Chess poorly, at least in comparison to ordinary Chess. The main point is that programs basically use a search algorithm, that would be hobbled by the much larger number of possible moves in each position (remember that for each turn you get one move on each board, and all the drops mean many more possibilities as well, so for each turn there might be 10,000 possibilities for the computer to consider, instead of 30 or so). Evaluating a position will also much more difficult for a computer in Enhanced Chess compared to ordinary Chess, because material and mobility are less important. I would anticipate based on these points that Enhanced Chess programs would perform significantly worse than Shogi (Japanese chess) programs (where there are drops, but only one move per turn), and even in Shogi, computer programs still fall somewhat short of the top level.

In the 15th century, a series of major rules modifications were accepted into Chess (the modern Queen, Bishop, and Pawn moves, Castling, and en passant) that succeeded in reviving what had become a rather dull game. It seems to me that something similar will need to occur again before Chess can reverse its decline and regain its status as the King of Games.

 

Rock-Paper-Scissors Without the Luck

October 6, 2007

As I’ve mentioned before (click here for his “Duke and Pawn” game, or click here for a more game-theoretical type of game), my son Adam enjoys designing games. Here’s a game he designed, with very simple rules but complex play, on the theme of Rock-Paper-Scissors.

1. The two players are White and Black, and they each have three pieces, a Rock, a Paper, and a Scissors, that they set up on a 6 by 6 board as shown below.

rps2001.jpg

2. White moves first, and then the players alternate.

3. Normally, a player moves a single one of his pieces one square orthogonally (up or down or right or left) on each move. You may not place a second piece on the same square except to capture. (So for example, on the first move, White’s legal moves are to move his Paper up or to the left, or his Scissors up or to the left.)

4. Rocks can capture Scissors, Scissors can capture Papers, and Papers can capture Rocks (of the opposite color in each case) but no other captures are possible. A piece can be moved a second time on the same move if and only if it enables it to make a capture that move (e.g. if a Paper is diagonally below and to the right from an opposing Rock, it could move up and then move left in order to capture the Rock.)

5. The object of the game is to move one of your pieces to the square where the opposing Rock is placed at the beginning of the game. If you do so, you instantly win the game.

6. You may never repeat a position.

7. You must move each turn. If you have no moves, you lose.

The game has no draws. One important and non-obvious point of strategy: if you exchange your Rock for your opponent’s Scissors, you will have an important material advantage, because your Paper can safely rampage without worrying about any of his pieces, while his Rock still has to worry about your Paper, and his Paper still has to worry about your Scissors.

It might appear that the first player has a significant advantage, but our games haven’t worked out that way at all. By the way, we use Chess pieces for the pieces; rooks for rocks, pawns for papers, and bishops for scissors.

I like the irony that ordinary Rock-Paper-Scissors is a game of complete chance and Adam’s version has no chance. Have fun!

(EDIT: This game now has a name; it’s called “Cyclotron.”)

 

Beginning Go

October 1, 2007

If you’re interested in learning more about the game of Go, whether you’re an absolute beginner or already know something about the game, a good starting point is “Sensei’s Library”, a huge wiki (it currently contains 15722 pages) all about Go. There are many ways to explore the wiki, and tons of interesting topics to explore.

There are are many nice English language books on Go. I will just recommend, if you are a beginner, the excellent five volume “Learn to Play Go Series” by Janice Kim and Jeong Soo-hyun. (If you already know the rules and have played a couple games, you probably want to begin with volume 2).

Go-playing programs, unlike Chess programs, are no match for even moderately strong human amateurs, but for beginners or weak players like myself, they can provide an interesting challenge. I very much like the free Goban Go GUI for Mac OS X, which includes GNU Go, which is one of the best Go-playing programs. Goban also serves as a client for online Go servers and lets you replay Go games in the .sgf format.

Magic the Gathering: Lorwyn Prerelease

September 25, 2007

If your interest in Magic the Gathering has been piqued by one or another of the previous posts here, you might want to know that this coming week-end, September 29 and 30, is the perfect time to attend your first Magic tournament, because a new expansion, named Lorywn, is having its “prerelease.” A prerelease is a kind of opening day for the new expansion, when the cards are seen and played with for the first time (although they won’t be legal for other tournaments until the official release two weeks later.)

Prereleases are much more informal than ordinary tournaments, and beginners are very welcome (not that they aren’t at other tournaments). In the ones around Boston, typically 200 players will be there. You can arrive at any time on Saturday or Sunday, as new tournaments are started as players arrive. Your wait will be shorter if you arrive early on Saturday though.

You can choose to play in a “sealed deck” tournament, where you construct your deck from a pool of cards given to you, or you can play with a pre-constructed “theme” deck. If you’ve never played before at all, the theme deck option is a pretty good choice, and will also leave you with a deck that can be your starting point for constructed tournaments.

For all the details, you should go the this Lorwyn Pre-release primer page from the official Magic web-site, and this Prerelease schedule.

If you’re going, whether or not you’ve had Magic experience, you might want to check out the rules about “Planeswalkers,” a new card type being added in Lorwyn.

And if you want to know what all the cards in the Lorwyn set will be before you get there, there are spoilers available at MTG Salvation (some players love these spoilers, others hate the idea of them.)

If you can’t make it this weekend, there are also Release tournaments in a couple weeks (October 12-14), although those tournaments are on a much smaller scale.

Mindbusters for Magic the Gathering

September 16, 2007

Today we have a guest article from my son Adam, about a variant of Magic the Gathering that we enjoy playing. I wrote a post introducing Magic and other trading card games previously, so if you know nothing about them, you might want to read that first. Adam’s article is definitely addressed to the advanced Magic player.

There are a few problems with Magic that this variant addresses: in particular the luck of the draw and the expense of buying packs. This variant is essentially a no-luck version which just requires two packs of cards. This type of variant can also be used for other trading card games.

If you’re interested in other variants to games like chess, go, bridge, etc., or perhaps in learning how to design your own variants or games, I highly recommend R. Wayne Schmittberger’s “New Rules for Classic Games.”

And if you’re interested in adding some Magic-like luck to the no-luck game of Chess, rather than eliminating the luck from Magic to make it more like Chess, you should read this post.

Read about the “Mindbusters” variant of Magic the Gathering.

(One comment for those who try to follow the article without much Magic experience: “milling” is the strategy of trying to run your opponents out of cards to draw: if you can’t draw a card when you’re supposed to, you lose the game.)

Cards & Chess

September 10, 2007

If you enjoy Chess, but want to spice it up a bit, you’ll probably enjoy some of the games in this post, which introduce the random element of cards into the royal game.

kc2sm.jpg

The first game(s) you might consider are Knightmare Chess and Knightmare Chess 2 (there is also a slightly different French language version called “TempĂȘte sur L’echiquier”) designed by Bruno Faidutti. This game is a kind of mix between Chess and a trading card game like Magic the Gathering. You’ll hold a hand of cards which will let you do some special event each turn (e.g. “For this turn, any one of your pieces may move as if it were a Knight. You cannot capture a piece with this move.”)

Faidutti, a French historian and sociologist, is one of the best-known and respected game designers. His games tend to have a strongly chaotic element. His most popular game, which I highly recommend, is Citadels (“Citadelles” in French), which is best played with large numbers of players (up to seven, and the closer to that number, the better).

Faidutti has an exceptional web-site, particularly notable for his Ideal Game Library, reviewing hundreds of games.


pic21524_t.jpg

Returning to the subject of cards and Chess, the other set of games I want to recommend is Karten Schach, designed by Reiner Knizia, the prolific German mathematician and game designer whom I already discussed in this post. Karten Schach was a labor of love by Knizia (I can’t imagine he thought it would sell very well, and the rulebook is over 100 pages, mostly taken up by discussions of the game mechanics, with plentiful strategy tips).

It is actually collection of 16 games (plus variants) highlighting all sorts of different possibilities in game design; a kind of game design version of Bach’s variations. The names of the games give you a flavor of the possibilities: “Purist Chess,” “Liar’s Chess,” “Ducat Chess,” “Daredevil Chess,” “Gambler’s Chess,” “Psycho Chess,” “Cornucopian Chess,” “Feudal Chess,” “Generational Chess,” “Oracle Chess,” “Prophet’s Chess,” “Eunuch’s Chess,” “Doppelganger Chess,” “Wicked Witch Chess,” “Mysterious Stranger’s Chess,” and “Capitalist Chess.”

Without explaining the rules in detail, I’ll just briefly describe how a couple are played. In Oracle Chess, you must, at the end of each move, put a card face down which commits you to the piece you will move next turn. In Capitalist Chess, on each turn a card is chosen, and you bid chips to have the right to move the piece displayed on the card. Each game is defined by less than a page of brilliant rules, by the master of boardgame design.

I would recommend that you buy Karten Schach, but it has been out of print since 2001, and the publisher has gone out of business. So instead I will point you to the English translation of the rules by Christine Biancheria and a pdf file for the Cards necessary to play the game. (Thanks to Matthew Gray, for pointing me to the English rules translations when they came out.)

And just as I did for Faidutti, I’d also like to recommend one much more mainstream multi-player Knizia game (in case Chess variants are not your cup of tea). The Knizia game I’ll recommend is “Modern Art,”, one of the most highly rated of the German games; a classic in the auction game genre.

Duke and Pawn Endgames

September 3, 2007

Note: to understand this post, you don’t need to know anything about chess; I’ll explain everything necessary right here.

One of the best ways for a chess beginner to improve is to study king and pawn endgames, and one of the best ways to do that is to play a game with only kings and pawns. Just remove all the rest of the pieces, and have at it.

Unfortunately, while Chess with just kings and pawns is not trivial, as you improve you will eventually outgrow it, because between two good chess players, the game is very likely to end in a draw.

As I mentioned in an earlier post, my son Adam likes to design games, and he designed this very clever variant of the King and Pawn endgame that eliminates the possibility of a draw.

duke001.jpg

Rules:

Set up the pieces as above, with four pawns plus a King for both White and Black.

The players alternate moves, starting with White.

The pawns move as in chess: one square forward, or optionally two squares forward if they haven’t moved yet, and they capture a piece one square ahead of them diagonally.

Pawns may still capture en passant as in Chess, which means the following. If an enemy pawn moves two squares forward, and one of your pawns could have captured it if it had only moved one square forward, you may capture that pawn as if it had only moved one square forward, but only if you do so with your pawn on the turn immediately after the enemy pawn moves.

The Kings can only move one square up or down, or left or right; they cannot move diagonally. (Such limited versions of Kings are sometimes called “Dukes;” hence the title of this post.)

You win the game immediately if you capture the opponent’s King, or if one of your pawns reaches the other side of the board.

You must always move; if you cannot make a legal move, you lose the game. (This is different from Chess, where stalemate is a draw.)

You may not make a move which recreates a position that has previously occurred during the game. (This is also different from Chess, but such a rule exists in Shogi, the Japanese version of Chess.)

That’s all the rules. In this game, draws are impossible, even if only two Kings remain on the board. For example, imagine that the White King is on a1, and the Black King is on b2. If White is to move, he loses, because he must move to a2 or b1, when Black can capture his King. But if Black is to move, he must retreat to the north-east, when White will follow him, until Black eventually reaches h8 and has no more retreat.

So arranging that your opponent is to move if the two Kings are placed on squares of the same color (if there are no pawn moves) is the key to victory. This concept, known as the “opposition,” is also very important in ordinary Chess King and pawn endgames, which is why skill at chess will translate into skill in this variant, and why improving your play at this variant will improve your Chess. Of course, the pawns are there, and they complicate things enormously!

Naturally, one can consider other starting positions, with different numbers of pawns.

This game can be analyzed using the methods of Combinatorial Game Theory (CGT). Noam Elkies, the Harvard mathematician, has written a superb article on the application of CGT to ordinary chess endgames, but it required great cleverness for him to find positions for which CGT could be applied; with this variant, the application of CGT should be much easier.

Music in Computer Games and Windows on Macs

September 2, 2007

kennedycenter.jpg

For certain genres of computer games, such as grand strategy games, the music can make a huge difference in the experience. One of the reasons that Civilization IV has been such a great hit is its wonderful music, particularly composer Christopher Tin‘s beautiful menu track “Baba Yetu” and opening track “Coronation.”

This music has attracted considerable notice; the picture above, taken from Tin’s website, is of the National Symphony Orchestra and the Washington Master Chorale performing “Baba Yetu” at the Kennedy Center. Tin makes “Baba Yetu” and “Coronation” (actually remixed versions slightly different from the computer game versions) available for download at his samples page, along with other samples of his work. (To download, just right-click and “save link” instead of left-clicking.) If you’re curious, the lyrics for “Baba Yetu” are actually a version of the Lord’s Prayer in Swahili.

My son Adam really enjoys playing the historical grand strategy games produced by Paradox Entertainment (Europa Universalis II, Victoria, Crusader Kings, and right now especially Europa Universalis III.) These games also have excellent music, but there are some tracks that he prefers more than others, and the music sometimes gets too repetitive in Europa Universalis III because there’s not as many tracks as he’d like. Adam also told me would play Crusader Kings mostly for its excellent music, and he would read the “Civilopedia” in Civ IV because it would let him listen to “Baba Yetu.”

Well, to give him a little more control, we made a playlist in iTunes, and put in only the tracks he likes from the games we own, and now he’s completely set. He just turns off the game music and uses his iTunes playlist instead. Speaking of iTunes on Windows, this is a funny quote from Apple’s CEO Steve Jobs a couple months back:

And speaking of running Windows on an Intel iMac using Bootcamp, which is what we do to run Windows-only games, this is a very funny link, but it’s not really accurate. Honestly our iMac running Windows (we actually run Windows XP instead of Vista because it runs games better, and is more stable) is easily the fastest and most stable Windows machine I’ve ever seen, probably largely because it’s missing all the bloat that normally comes on a PC (and because I’m very careful about what gets installed on it.) Walt Mossberg from the Wall Street Journal also reports that an iMac running Vista is the best Vista machine he’s seen.

Combinatorial Game Theory

August 29, 2007

Combinatorial Game Theory (CGT) is a mathematical discipline that studies two-player, zero-sum games, where the players play sequentially, and there is perfect information and no chance. The aim of CGT is to build mathematical theories that will help players win such games! In practice, the ideas from CGT are of minimal help to the serious player in more complicated games like Chess or Go, but the theories are extremely helpful for simpler but still non-trivial games like Dots-and-Boxes.

9781568811307.jpg

The CGT bible is Winning Ways for Your Mathematical Plays, a four-volume set of books (for the 2nd edition from the early 2000’s; the first edition from 1982 was in two volumes), by the eminent mathematicians Elwyn Berlekamp, John Horton Conway, and Richard Guy.

The basic idea of CGT is to develop a calculus, which lets you assign a value to a position in the game. One normally considers games with the condition that a player who cannot move loses. If both players are without a move in a position (whoever moves loses), the position is assigned a value of 0. If the player on the right can make one move that transforms the position to one of value 0, and the player on the left cannot move at all, the position is assigned a value of 1 (if the roles are reversed, the position has value -1).

Now what happens if the player on the left has a move to a position of value 0, and the player on the right has a move to a position of value 1? What is the value of that position? It turns out to be worth 1/2, as can be seen by considering the position obtained by adding such two such positions together with a position of value -1, when one gets back to a position of value 0 where whoever moves loses (I’ll let you work out the details).

There are more different kinds of values than just fractions. Berlekamp, Conway, and Guy consider a multitude of different interesting games, which give rise to ever deeper mathematics, and game positions with strange values along with complex rules for combining those values.

The writing is informal, with constant punning, but the mathematics is serious. Still, one charm of the field is that there is no pre-requisite mathematical material needed to understand these books–bright high school students can launch right in.

After finishing “Winning Ways,” the ambitious student can move on to the two volumes “Games of No Chance” and “More Games of No Chance” (note that nearly all the papers in these books are available online), and then move onto the rest of the papers collected at David Eppstein‘s CGT page.

Also, take a look at Aaron Siegel‘s Combinatorial Game Suite software to help you do CGT computations.

There’s still much more to say, but I’ll leave that for other posts.