Anti-computer tactics

Last updated
Deep Blue, a famous chess-playing computer that beat world champion Garry Kasparov in a human-computer match Deep Blue.jpg
Deep Blue, a famous chess-playing computer that beat world champion Garry Kasparov in a human–computer match

Anti-computer tactics are methods used by humans to try to beat computer opponents at various games, most typically board games such as chess and Arimaa. They are most associated with competitions against computer AIs that are playing to their utmost to win, rather than AIs merely programmed to be an interesting challenge that can be given intentional weaknesses and quirks by the programmer (as in many video game AIs). Such tactics are most associated with the era when AIs searched a game tree with an evaluation function looking for promising moves, often with Alpha–beta pruning or other minimax algorithms used to narrow the search. Against such algorithms, a common tactic is to play conservatively aiming for a long-term advantage. The theory is that this advantage will manifest slowly enough that the computer is unable to notice in its search, and the computer won't play around the threat correctly. This may result in, for example, a subtle advantage that eventually turns into a winning chess endgame with a passed pawn. (Conversely, attempting to lure an AI into a short-term "trap", inviting the play of a reasonable-seeming to humans but actually disastrous move, will essentially never work against a computer in games of perfect information.)

Contents

The field is most associated with the 1990s and early 2000s, when computers were very strong at games such as chess, yet beatable. Even then, the efficacy of such tactics was questionable, with several tactics such as making unusual or suboptimal moves to quickly get the computer out of its opening book proving ineffective in human-computer tournaments. The rise of machine learning has also dented the applicability of anti-computer tactics, as machine learning algorithms tend to play the long game equally as well if not better than human players.

Common aspects

One aspect of designing a classic AI for games of perfect information is the horizon effect. Computer AIs examine a game tree of possible moves and counter-moves, but unless a forced win is in the tree, it needs to stop exploring new possibilities eventually. When it does, an evaluation function is called on the board state, which often uses rough heuristics to determine which side the board favors. In chess, this might be things like material advantage (extra pieces), control of the center, king safety, and pawn structure. Exploiting the horizon effect can be done by human players by using a strategy whose fruits are apparent only beyond the plies examined by the AI. For example, if the AI is examining 10 plies ahead, and a strategy will "pay off" in 12-20 plies (6-10 turns), the AI won't play around the looming threat that it can't "see", similar to a person being unable to see "over the horizon" where a ship might be hid by the natural curvature of the earth. Similarly, to keep the horizon short, human players may want to keep as complicated a board state as possible. Simplifying the board by trading pieces lets the AI look "farther" into the future, as there are fewer options to consider, and thus is avoided when trying to exploit the horizon effect.

A tactic that works best on AIs that are very "deterministic" and known to play in one specific way in response to a threat is to force a situation where the human knows exactly how the AI will respond. If the human picks a situation that they believe the AI handles poorly, this can lead to reliably luring the AI into such situations. Even if the AI can handle that particular play style well, if the human is confident that the AI will always pick it, it simplifies preparation for the human player - they can just learn this one situation very closely, knowing that the AI will always accept an invitation to play into that kind of board.

Chess

In the 1997 Deep Blue versus Garry Kasparov match, Kasparov played an anti-computer tactic move at the start of the game to get Deep Blue out of its opening book. [1] Kasparov chose the unusual Mieses Opening and thought that the computer would play the opening poorly if it had to play itself (that is, rely on its own skills rather than use its opening book). [2] Kasparov played similar anti-computer openings in the other games of the match, but the tactic backfired. [3]

The Brains in Bahrain was an eight-game chess match between human chess grandmaster, and then World Champion, Vladimir Kramnik and the computer program Deep Fritz 7, held in October 2002. The match ended in a tie 4–4, with two wins for each participant and four draws, worth half a point each. [4]

Anti-computer chess games

Arimaa

Arimaa is a chess derivative specifically designed to be difficult for alpha-beta pruning AIs, inspired by Kasparov's loss to Deep Blue in 1997. It allows 4 actions per "move" for a player, greatly increasing the size of the search space, and can reasonably end with a mostly full board and few captured pieces, avoiding endgame tablebase style "solved" positions due to scarcity of units. While human Arimaa players held out longer than chess, they too fell to superior computer AIs in 2015. [5]

Related Research Articles

<span class="mw-page-title-main">Deep Blue (chess computer)</span> Chess-playing computer made by IBM

Deep Blue was a chess-playing expert system run on a unique purpose-built IBM supercomputer. It was the first computer to win a game, and the first to win a match, against a reigning world champion under regular time controls. Development began in 1985 at Carnegie Mellon University under the name ChipTest. It then moved to IBM, where it was first renamed Deep Thought, then again in 1989 to Deep Blue. It first played world champion Garry Kasparov in a six-game match in 1996, where it lost four games to two. It was upgraded in 1997 and in a six-game re-match, it defeated Kasparov by winning two games and drawing three. Deep Blue's victory is considered a milestone in the history of artificial intelligence and has been the subject of several books and films.

<span class="mw-page-title-main">Computer chess</span> Computer hardware and software capable of playing chess

Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training. Computer chess applications that play at the level of a chess master or higher are available on hardware from supercomputers to smart phones. Standalone chess-playing machines are also available. Stockfish, GNU Chess, Fruit, and other free open source applications are available for various platforms.

Brains in Bahrain was an eight-game chess match between World Chess Champion Vladimir Kramnik and the computer program Deep Fritz 7, held in October 2002. The match ended in a tie 4-4, with two wins for each participant and four draws.

Feng-hsiung Hsu is a Taiwanese-American computer scientist and the author of the book Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. His work led to the creation of the Deep Thought chess computer, which led to the first chess playing computer to defeat grandmasters in tournament play and the first to achieve a certified grandmaster-level rating.

<span class="mw-page-title-main">Junior (chess)</span>

Junior is a computer chess program written by the Israeli programmers Amir Ban and Shai Bushinsky. Grandmaster Boris Alterman assisted, in particular with the opening book. Junior can take advantage of multiple processors, taking the name Deep Junior when competing this way in tournaments.

<span class="mw-page-title-main">Deep Blue versus Kasparov, 1996, Game 1</span> Computer vs. human chess match

Deep Blue–Kasparov, 1996, Game 1 is a famous chess game in which a computer played against a human being. It was the first game played in the 1996 Deep Blue versus Garry Kasparov match, and the first time that a chess-playing computer defeated a reigning world champion under normal chess tournament conditions.

Arimaa is a two-player strategy board game that was designed to be playable with a standard chess set and difficult for computers while still being easy to learn and fun to play for humans. It was invented between 1997 and 2002 by Omar Syed, an Indian-American computer engineer trained in artificial intelligence. Syed was inspired by Garry Kasparov's defeat at the hands of the chess computer Deep Blue to design a new game which could be played with a standard chess set, would be difficult for computers to play well, but would have rules simple enough for his then four-year-old son Aamir to understand.

<span class="mw-page-title-main">Chess engine</span> Computer program for chess analysis and game

In computer chess, a chess engine is a computer program that analyzes chess or chess variant positions, and generates a move or list of moves that it regards as strongest.

Deep Thought was a computer designed to play chess. Deep Thought was initially developed at Carnegie Mellon University and later at IBM. It was second in the line of chess computers developed by Feng-hsiung Hsu, starting with ChipTest and culminating in Deep Blue. In addition to Hsu, the Deep Thought team included Thomas Anantharaman, Mike Browne, Murray Campbell and Andreas Nowatzyk. Deep Thought became the first computer to beat a grandmaster in a regular tournament game when it beat Bent Larsen in 1988, but was easily defeated in both games of a two-game match with Garry Kasparov in 1989 as well as in a correspondence match with Michael Valvo.

<i>Fritz</i> (chess) Chess software

Fritz is a German chess program originally developed for Chessbase by Frans Morsch based on his Quest program, ported to DOS, and then Windows by Mathias Feist. With version 13, Morsch retired, and his engine was first replaced by Gyula Horvath's Pandix, and then with Fritz 15, Vasik Rajlich's Rybka.

<i>Game Over: Kasparov and the Machine</i> 2003 Canadian film

Game Over: Kasparov and the Machine is a 2003 documentary film by Vikram Jayanti about the match between Garry Kasparov, the highest rated chess player in history, the World Champion for 15 years (1985–2000) and an anti-communist politician, and Deep Blue, a chess-playing computer created by IBM. It was coproduced by Alliance Atlantis and the National Film Board of Canada.

Advanced chess is a form of chess in which each human player uses a computer chess program to explore the possible results of candidate moves. Despite this computer assistance, it is the human player who controls and decides the game.

<span class="mw-page-title-main">Deep Blue versus Kasparov, 1997, Game 6</span> Chess game between human and computer

Game 6 of the Deep Blue–Kasparov rematch, played in New York City on May 11, 1997 and starting at 3:00 p.m. EDT, was the last chess game in the 1997 rematch of Deep Blue versus Garry Kasparov.

<span class="mw-page-title-main">Belle (chess machine)</span>

Belle was a chess computer developed by Joe Condon (hardware) and Ken Thompson (software) at Bell Labs. In 1983, it was the first machine to achieve master-level play, with a USCF rating of 2250. It won the ACM North American Computer Chess Championship five times and the 1980 World Computer Chess Championship. It was the first system to win using specialized chess hardware.

<span class="mw-page-title-main">Deep Blue versus Garry Kasparov</span> Chess matches between Deep Blue and Kasparov

Deep Blue versus Garry Kasparov was a pair of six-game chess matches between then-world chess champion Garry Kasparov and an IBM supercomputer called Deep Blue. Kasparov won the first match, held in Philadelphia in 1996, by 4–2. Deep Blue won a 1997 rematch held in New York City by 3½–2½. The second match was the first defeat of a reigning world chess champion by a computer under tournament conditions, and was the subject of a documentary film, Game Over: Kasparov and the Machine.

This article documents the progress of significant human–computer chess matches.

Computer Arimaa refers to the playing of the board game Arimaa by computer programs.

<span class="mw-page-title-main">AlphaZero</span> Game-playing artificial intelligence

AlphaZero is a computer program developed by artificial intelligence research company DeepMind to master the games of chess, shogi and go. This algorithm uses an approach similar to AlphaGo Zero.

The history of chess began nearly 1500 years ago, and over the past millennium and a half the game has changed drastically. No technology or strategy, however, has changed chess as much as the introduction of chess engines. Despite only coming into existence within the previous 70 years, the introduction of chess engines has molded and defined how top chess is played today.

References

  1. ↑ Daily Chess Columns-All the News That's Fit to Mock. 3) Anti-computer chess. Archived 2007-08-08 at the Wayback Machine (broken) from ChessBase
  2. ↑ Chess Life , Special Summer Issue 1997.
  3. ↑ How Much Longer Can Man Match the Computer? - The Fall of Man from ChessCafe.com
  4. ↑ ChessBase.com - Chess News - Fritz Defends to Draw Game 8 and the Match! Final score: 4–4
  5. ↑ Wu, David (2015). "Designing a Winning Arimaa Program" (PDF). ICGA Journal . 38 (1): 19–40. doi:10.3233/ICG-2015-38104.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.