Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. It was notably included in Microsoft Windows from 1.0 to XP, where it is simply known as Reversi.
There are many Othello programs such as NTest, Saio, Edax, Cassio, Pointy Stone, Herakles, WZebra, and Logistello that can be downloaded from the Internet for free. These programs, when run on any up-to-date computer, can play games in which the best human players are easily defeated. This is because although the consequences of moves are predictable for both computers and humans, computers are better at exploring them.[1]
Search techniques
Computer Othello programs search for any possible legal moves using a game tree. In theory, they examine all positions / nodes, where each move by one player is called a "ply". This search continues until a certain maximum search depth or the program determines that a final "leaf" position has been reached.
A naive implementation of this approach, known as Minimax or Negamax, can only search to a small depth in a practical amount of time, so various methods have been devised to greatly increase the speed of the search for good moves. These are based on Alpha-beta pruning, Negascout, MTD(f), and NegaC*.[2] The alphabeta algorithm is a method for speeding up the Minimax searching routine by pruning off cases that will not be used anyway. This method takes advantage of the fact that every other level in the tree will maximize and every other level will minimize.[3]
Several heuristics are also used to reduce the size of the searched tree: good move ordering, transposition table and selective Search.[4]
To speed up the search on machines with multiple processors or cores, a "parallel search" may be implemented. Several experiments have been made with the game Othello, like ABDADA[5] or APHID[6] On recent programs, the YBWC[7] seems the preferred approach.
Multi-Prob cut
Multi-ProbCut is a heuristic used in alpha–beta pruning of the search tree.[8] The ProbCut heuristic estimates evaluation scores at deeper levels of the search tree using a linear regression between deeper and shallower scores. Multi-ProbCut extends this approach to multiple levels of the search tree. The linear regression itself is learned through previous tree searches, making the heuristic a kind of dynamic search control.[9] It is particularly useful in games such as Othello where there is a strong correlation between evaluations scores at deeper and shallower levels.[10][11]
Evaluation techniques
There are three different paradigms for creating evaluation functions.
Disk-square tables
Different squares have different values - corners are good and the squares next to corners are bad. Disregarding symmetries, there are 10 different positions on a board, and each of these is given a value for each of the three possibilities: black disk, white disk and empty. A more sophisticated approach is to have different values for each position during the different stages of the game; e.g. corners are more important in the opening and early midgame than in the endgame.[12]
Mobility-based
Most human players strive to maximize mobility (number of moves available) and minimize frontier disks (disks adjacent to empty squares). Player mobility and opponent mobility are calculated, and player potential mobility and opponent potential mobility are calculated as well.[13] These measures can be found very quickly, and they significantly increase playing strength. Most programs have knowledge of edge and corner configurations and try to minimize the number of disks during the early midgame, another strategy used by human players.[12]
Pattern-based / pattern coefficients
Mobility maximization and frontier minimization can be broken down into local configurations which can be added together; the usual implementation is to evaluate each row, column, diagonal and corner configuration separately and add together the values, many different patterns have to be evaluated.[12] The process of determining values for all configurations is done by taking a large database of games played between strong players and calculating statistics for each configuration in each game stage from all the games.[12]
The most common choice to predict the final disc difference uses a weighted disk difference measure where the winning side gets a bonus corresponding to the number of disks.[12]
Opening book
Opening books aid computer programs by giving common openings that are considered good ways to counter poor openings. All strong programs use opening books and update their books automatically after each game. To go through all positions from all games in the game database and determine the best move not played in any database game, transposition tables are used to record positions that have been previously searched. This means those positions do not need to be searched again.[12] This is time-consuming as a deep search must be performed for each position, but once this is done, updating the book is easy. After each game played, all new positions are searched for the best deviation.
Other optimizations
Faster hardware and additional processors can improve Othello-playing program abilities, such as deeper ply searching.
Solving Othello
During gameplay, players alternate moves. The human player uses black counters while the computer uses white. The human player starts the game.[1] Othello is strongly solved on 4×4 and 6×6 boards, with the second player (white) winning in perfect play.[14][15]
Othello 4 × 4
Othello 4x4 has a very small game tree and has been solved in less than one second by many simple Othello programs that use the Minimax method, which generates all possible positions (nearly 10 million). The result is that white wins with a +8 margin (3-11).[14]
Othello 6 × 6
Othello 6x6 has been solved in less than 100 hours by many simple Othello programs that use the Minimax method, which generates all possible positions (nearly 3.6 trillion). The result is that white wins with a +4 margin (16-20).[16]
Othello 8 × 8
The Othello 8x8 game tree size is estimated at 1054 nodes, and the number of legal positions is estimated at less than 1028. As of October 2023, a preprint claims that the game has been solved, with optimal result being draw.[17][18] Computation results is also shared, making it one of the largest publicly available book.[19]
Some top programs have expanded their books for many years now. As a result, many lines are in practice draws or wins for either side. Regarding the three main openings of diagonal, perpendicular and parallel, it appears that both diagonal and perpendicular openings lead to drawing lines, while the parallel opening is a win for black. The drawing tree also seems bigger after the diagonal opening than after the perpendicular opening.[20][failed verification] The parallel opening has strong advantages for the black player, enabling black to always win in a perfect play.[21][failed verification]
1977: Scientific American made the earliest known published reference to an Othello/Reversi program, written by N. J. D. Jacobs in BCPL.[22]BYTE published "Othello, a New Ancient Game" as a BASIC type-in program in October.[23]
1980: The Othello program The Moor (written by Mike Reeve and David Levy) won one game in a six-game match against world champion Hiroshi Inoue.[27] Peter W Frey of Northwestern University discussed computer and human Othello strategies in BYTE, and discussed his TRS-80 Othello game which, Frey claimed, easily defeated Wright's version running on a CDC 6600.[25] Paul Rosenbloom of Carnegie Mellon University developed IAGO, which finished in third place at a Northwestern University computer tournament.[28] When IAGO played The Moor, IAGO was better at capturing pieces permanently and limiting its opponent's mobility.[27]
1981: IAGO running on a DEC KA10 finished ahead of 19 other contestants at the Santa Cruz Open Othello Tournament at the University of California, Santa Cruz, with the only undefeated record. Charles Heath's TRS 80-based game finished in second place. Microcomputer CPU-based engines won the second through seventh places, ahead of several mainframes and minicomputers; Frey speculated that this was because computer Othello does not benefit from several of the advantages of larger computers, such as faster floating-point arithmetic.[28]
Late 1980s: Kai-Fu Lee and Sanjoy Mahajan created the Othello program BILL, which was similar to IAGO but incorporated Bayesian learning. BILL reliably beat IAGO.[27]
1992: Michael Buro began work on the Othello program Logistello. Logistello's search techniques, evaluation function, and knowledge base of patterns were better than those in earlier programs. Logistello perfected its game by playing over 100,000 games against itself.[27]
1997: Logistello won every game in a six-game match against world champion Takeshi Murakami. Though there had not been much doubt that Othello programs were stronger than humans, it had been 17 years since the last match between a computer and a reigning world champion. After the 1997 match, there was no longer any doubt: Logistello was significantly better than any human player.[29][27]
1998: Michael Buro retired Logistello. Research interest in Othello waned somewhat, but some programs, including Ntest, Saio, Edax, Cassio, Zebra and Herakles, continued to be developed.[27]
2004: Ntest became the strongest program, significantly stronger than Logistello.
2005: Ntest, Saio, Edax, Cyrano and Zebra, became significantly stronger than Logistello. Ntest and Zebra retired.
2011: Saio, Edax and Cyrano, became much faster than Logistello and other programs.
2022: Egaroucid appears as strong engine highly inspired by Edax.
2023: Othello is solved using slightly modified Edax. Egaroucid releases self-play data.[30]
↑ Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Algorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal Vol. 19, No. 1
↑ Mark Brockington (1997). KEYANO Unplugged - The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta.
↑ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). A Fully Distributed Chess Program. Advances in Computer Chess 6
Minmax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.
Reversi is a strategy board game for two players, played on an 8×8 uncheckered board. It was invented in 1883. Othello, a variant with a fixed initial setup of the board, was patented in 1971.
A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.
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 grandmaster or higher are available on hardware from supercomputers to smart phones. Standalone chess-playing machines are also available. Stockfish, Leela Chess Zero, GNU Chess, Fruit, and other free open source applications are available for various platforms.
Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player combinatorial games. It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position in a game tree. Most of the time, the value is either a real number or a quantized integer, often in nths of the value of a playing piece such as a stone in go or a pawn in chess, where n may be tenths, hundredths or other convenient fraction, but sometimes, the value is an array of three values in the unit interval, representing the win, draw, and loss percentages of the position.
In competitive two-player games, the killer heuristic is a move-ordering method based on the observation that a strong move or small set of such moves in a particular position may be equally strong in similar positions at the same move (ply) in the game tree. Retaining such moves obviates the effort of rediscovering them in sibling nodes.
In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha–beta pruning algorithm.
Computer Go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays the traditional board game Go. The field is sharply divided into two eras. Before 2015, the programs of the era were weak. The best efforts of the 1980s and 1990s produced only AIs that could be defeated by beginners, and AIs of the early 2000s were intermediate level at best. Professionals could defeat these programs even given handicaps of 10+ stones in favor of the AI. Many of the algorithms such as alpha-beta minimax that performed well as AIs for checkers and chess fell apart on Go's 19x19 board, as there were too many branching possibilities to consider. Creation of a human professional quality program with the techniques and hardware of the time was out of reach. Some AI researchers speculated that the problem was unsolvable without creation of human-like AI.
A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or determine moves or plays in the game.
Logistello is a computer program that plays the game Othello, also known as Reversi. Logistello was written by Michael Buro and is regarded as a strong player, having beaten the human world champion Takeshi Murakami six games to none in 1997 — the best Othello programs are now much stronger than any human player. Logistello's evaluation function is based on disc patterns and features over a million numerical parameters which were tuned using linear regression.
Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game.
Quiescence search is an algorithm typically used to extend search at unstable nodes in minimax game trees in game-playing computer programs. It is an extension of the evaluation function to defer evaluation until the position is stable enough to be evaluated statically, that is, without considering the history of the position or future moves from the position. It mitigates the effect of the horizon problem faced by AI engines for various games like chess and Go.
Chess was a pioneering chess program from the 1970s, written by Larry Atkin, David Slate and Keith Gorlen at Northwestern University. Chess ran on Control Data Corporation's line of supercomputers. Work on the program began in 1968 while the authors were graduate students at the university. The first competitive version was Chess 2.0 which gradually evolved to Chess 3.6 and was rewritten as the 4.x series. It dominated the first computer chess tournaments, such as the World Computer Chess Championship and ACM's North American Computer Chess Championship. NWU Chess adopted several innovative or neglected techniques including bitboard data structures, iterative deepening, transposition tables, and an early form of forward pruning later called futility pruning. The 4.x versions were the first programs to abandon selective search in favor of full-width fixed-depth searching.
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. 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.
Artificial stupidity is a term used within the field of computer science to refer to a technique of "dumbing down" computer programs in order to deliberately introduce errors in their responses.
NTest is a free Othello/Reversi program created by Chris Welty.
Ultimate tic-tac-toe is a board game composed of nine tic-tac-toe boards arranged in a 3 × 3 grid. Players take turns playing on the smaller tic-tac-toe boards until one of them wins on the larger board. Compared to traditional tic-tac-toe, strategy in this game is conceptually more difficult and has proven more challenging for computers.
Michael Buro is a Canadian AI Researcher and the creator of the Skat-playing computer program Kermit, as well as the Othello-playing computer program Logistello.
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.
