Tuesday, August 11, 2009

Artificial Intelligence - Magic and Chess

Long before people were trying to program the computer to play a decent game of Magic, people were trying to teach it to play a decent game of chess. Computer chess programs are now very advanced and can crush the average player in the privacy of his home. I hope one day to develop a Magic AI capable of crushing most human players. (And then computers will naturally take over the Earth of course.)

According to Wikipedia the first chess program was written in 1958 but the first “credible” program didn’t appear until 1962. In 1967 was the first time that a computer beat a human player in a tournament.

Computer chess has advanced the field of artificial intelligence by producing the alpha-beta program which every chess program uses or a variation of it. Chess programs typically look very far into the future in order to make the correct move and also use a database for openings, plays at the beginning of the game, and endgames.

Even though checkers is relatively simple when compared to Magic and chess, it is still challenging to try to develop a good AI for it. In 2007 the computer program Chinook recently “solved” checkers. According to Chinook’s developers it will never lose a game and if no mistakes are made by either player, the game will always end in a draw.

Personally I’m not sure if Magic is more or less complicated than chess. In chess you seem to have more choices because you can move any of your 16 pieces and usually Magic doesn’t have that many choices. Although in my heart Magic will always be 100 times better than chess.

In 1997 the IBM chess computer Deep Blue did beat the reigning world champion Garry Kasparov but he “claimed that several factors weighed against him in this match. In particular, he was denied access to Deep Blue's recent games, in contrast to the computer's team that could study hundreds of Kasparov's.” “After the loss Kasparov said that he sometimes saw deep intelligence and creativity in the machine's moves, suggesting that during the second game, human chess players, in contravention of the rules, intervened.” [citation]

As I understand it Kasparov agreed to play Deep Blue if he was allowed to view Deep Blue’s game style, but the computer never played in any tournaments so Kasparov was denied and was forced to play against the computer in a shameless publicity stunt. So the IBM team deceitfully denied Kasparov a print out of Deep Blue’s games and might have cheated by allowing human intervention.

In 2003 Kasparov played the computer programs Deep Junior and X3D Fritz which both resulted in a draw. I consider this a victory for both Kasparov and computer chess.


William said...

Indeed. I really do believe the whole deep blue thing was cruel. He had even won the first match. The second match deep blue had been modified to play against him.

I like playing chess too. A surprising amount of chess concepts can be easily applied to magic. For example card advantage is just piece advantage.

Anonymous said...

The thing about that game was what the computer did is what made him made. The computer moved himself into a perpetual check which would of been a draw. And he said a computer would never draw that way. There was a funny movie about it the name just escapes me.

Bill Christian said...

There are significant differences between a Chess game and Magic. The presence of randomness by shuffling and drawing cards. And, the principle of imperfect information. Similar to poker, I doubt a computer AI can consistently win against a person in MtG.

Forge said...

Technically Magic has "private information" and chess does not. I think it would be ok if the AI could see your deck and the cards in your hand, although right now the AI is very primitive and wouldn't be able to effectively use that info.