Archive for the ‘Chess’ Category

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.

 

World Chess Championship 2007

September 24, 2007

Click on picture above to expand

The World Chess Championship is being held now in Mexico City. It began on September 12, and is scheduled to finish on September 30. Unlike some of the World Championships of the past, this one is a tournament between eight players rather than a match between two. The eight players are Vladimir Kramnik (the current world champion), Viswanathan Anand (the world’s highest rated player), Levon Aronian, Alexander Morozevich, Peter Leko, Boris Gelfand, Peter Svidler and Alexander Grischuk.

In the picture above Kramnik (to the right) is playing Anand (to the left), while Gelfand (between the players) and Grischuk (behind Anand) observe. All of these players play at a fantastically high level (the general level of human chess players has steadily improved with time), but sadly fewer people pay attention now that computers play even better.

The only one of these grandmasters that I’ve personally played against is Peter Svidler, in the 1995 New York Open. I was doing very well in that tournament, and had a chance to win a large prize, but then I played Svidler with the Black pieces, and he crushed me. The memory is actually not so bad, because it was very interesting to play him and to talk to him afterwards (he was 19, but it was already clear that he could potentially challenge for the world championship), and I nevertheless achieved a norm for my international master title in that tournament.

The World Championship tournament is a double-round robin, so it will last 14 rounds. After nine rounds, Anand leads with a record of 6-3, followed by Gelfand with 5-4, Leko, Grischuk, and Kramnik with 4.5-4.5, Aronian and Morozevich with 4-5, and Svidler with 3.5-5.5. Today Kramnik plays Anand with the White pieces; he’ll need to win to have much chance of catching him. But even if Kramnik does not win, he’s guaranteed a match against the world champion in 2008.

(UPDATE: Anand held Kramnik to a hard-fought draw in round 10, and then followed up with a win against Morozevich in round 11, so with three rounds to go, he holds a substantial 1.5 point lead over Gelfand, and looks likely to become the next World Champion.)

(UPDATE 2: Anand has won the world championship, with Kramnik and Gelfand tying for second place. The cross-table of the results is below):

WCh Mexico City MEX (MEX), 13-29 ix 2007               cat. XXI (2752)
----------------------------------------------------------------------
                                     1  2  3  4  5  6  7  8 
----------------------------------------------------------------------
1 Anand, Viswanathan     g IND 2792 ** == == == 1= =1 1= 1=  9.0  2848
2 Kramnik, Vladimir      g RUS 2769 == ** == =1 == 10 =1 ==  8.0  2799
3 Gelfand, Boris         g ISR 2733 == == ** == == 1= 11 =0  8.0  2804
4 Leko, Peter            g HUN 2751 == =0 == ** == =1 0= =1  7.0  2751
5 Svidler, Peter         g RUS 2735 0= == == == ** 0= == =1  6.5  2725
6 Morozevich, Alexander  g RUS 2758 =0 01 0= =0 1= ** == 01  6.0  2700
7 Aronian, Levon         g ARM 2750 0= =0 00 1= == == ** =1  6.0  2702
8 Grischuk, Alexander    g RUS 2726 0= == =1 =0 =0 10 =0 **  5.5  2675
----------------------------------------------------------------------

To learn more about the tournament, you might start with Macauley’s rather artistic coverage of the first game between Kramnik and Anand in round 3. More videos of this type head are at macauley.blip.tv. You might also head over to the excellent chess web-site The Week in Chess for news and annotated game scores, and the ChessVibes blog for many on-the-scene videos (often including instructive post-game interviews with the players) and the games in an easy-to-use Java player (I already pointed to some remarkable videos from earlier this year at ChessVibes in a previous post.) But perhaps the most interesting coverage of the World Championship tournament for intermediate or stronger chess players is by the Internet Chess Club, which has a team of strong grandmasters presenting annotated game videos.

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.

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.

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.

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.

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.