Edax (computing)
   HOME

TheInfoList



OR:

Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of
Othello ''The Tragedy of Othello, the Moor of Venice'', often shortened to ''Othello'' (), is a tragedy written by William Shakespeare around 1603. Set in Venice and Cyprus, the play depicts the Moorish military commander Othello as he is manipulat ...
. It was notably included in
Microsoft Windows Windows is a Product lining, product line of Proprietary software, proprietary graphical user interface, graphical operating systems developed and marketed by Microsoft. It is grouped into families and subfamilies that cater to particular sec ...
from 1.0 to XP, where it is simply known as Reversi.


Availability

There are many Othello programs such as NTest, Saio, Edax, Cassio, Pointy Stone, Herakles, WZebra, and
Logistello 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 &md ...
that can be downloaded from the
Internet The Internet (or internet) is the Global network, global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a internetworking, network of networks ...
for free. These programs, when run on any up-to-date
computer A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...
, 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.


Search techniques

Computer Othello programs search for any possible legal moves using a
game tree In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe. A game tree can be us ...
. 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 Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for ''minimizing'' the possible loss function, loss for a Worst-case scenari ...
or
Negamax Negamax search is a variant form of minimax search that relies on the Zero-sum (Game theory), zero-sum property of a two-player game. This algorithm relies on the fact that to simplify the implementation of the minimax algorithm. More precisely, ...
, 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 Alphabeta or Alpha Beta may also refer to: * Alphabeta, an Israeli musical group * Alpha Beta, a former chain of Californian supermarkets * The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters * Alpha and beta anome ...
,
Negascout Principal variation search (sometimes equated with the practically identical NegaScout) is a negamax algorithm that can be faster than alpha–beta pruning. Like alpha–beta pruning, NegaScout is a directional search algorithm for computing the mi ...
,
MTD(f) MTD(f) is an alpha-beta game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory (usually a transposition table) to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for M ...
, and NegaC*. 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. Several heuristics are also used to reduce the size of the searched tree: good move ordering,
transposition table {{no footnotes, date=November 2017 A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the ...
and selective Search.Buro, M.
"Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello"
''Games in AI Research'', H.J. van den Herik, H. Iida (ed.), , 2000
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 or APHID On
recent The Holocene () is the current geological epoch, beginning approximately 11,700 years ago. It follows the Last Glacial Period, which concluded with the Holocene glacial retreat. The Holocene and the preceding Pleistocene together form the Qu ...
programs, the YBWC seems the preferred approach.


Multi-Prob cut

Multi-ProbCut is a heuristic used in
alpha–beta pruning Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the Minimax#Minimax algorithm with alternate moves, minimax algorithm in its game tree, search tree. It is an adversarial search algorith ...
of the search tree. The ProbCut heuristic estimates evaluation scores at deeper levels of the search tree using a
linear regression In statistics, linear regression is a statistical model, model that estimates the relationship between a Scalar (mathematics), scalar response (dependent variable) and one or more explanatory variables (regressor or independent variable). A mode ...
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. It is particularly useful in games such as
Othello ''The Tragedy of Othello, the Moor of Venice'', often shortened to ''Othello'' (), is a tragedy written by William Shakespeare around 1603. Set in Venice and Cyprus, the play depicts the Moorish military commander Othello as he is manipulat ...
where there is a strong correlation between evaluations scores at deeper and shallower levels.


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.


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. 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.


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. 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. 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.


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 table {{no footnotes, date=November 2017 A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the ...
s are used to record positions that have been previously searched. This means those positions do not need to be searched again. 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. Othello is strongly solved on 4×4 and 6×6 boards, with the second player (white) winning in
perfect play Perfect commonly refers to: * Perfection; completeness, and excellence * Perfect (grammar), a grammatical category in some languages Perfect may also refer to: Film and television * ''Perfect'' (1985 film), a romantic drama * ''Perfect'' ( ...
.Solution of Othello 4 × 4
September 02, 2008


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).


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).


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. Computation results is also shared, making it one of the largest publicly available books. 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. The parallel opening has strong advantages for the black player, enabling black to always win in a perfect play.


Milestones in computer Othello

*1977:
Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it, with more than 150 Nobel Pri ...
made the earliest known published reference to an Othello/Reversi program, written by N. J. D. Jacobs in
BCPL BCPL ("Basic Combined Programming Language") is a procedural, imperative, and structured programming language. Originally intended for writing compilers for other languages, BCPL is no longer in common use. However, its influence is still f ...
. ''
BYTE The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable un ...
'' published "Othello, a New Ancient Game" as a BASIC
type-in program A type-in program or type-in listing was computer source code printed in a home computer magazine or book. It was meant to be entered via the keyboard by the reader and then saved to cassette tape or floppy disk. The result was a usable game, ut ...
in October. *1977:
Creative Computing ''Creative Computing'' was one of the earliest magazines covering the microcomputer revolution. Published from October 1974 until December 1985, the magazine covered the spectrum of hobbyist/home/personal computing in a more accessible format t ...
published a version of Othello written by Ed Wright in FORTRAN. *1978:
Nintendo is a Japanese Multinational corporation, multinational video game company headquartered in Kyoto. It develops, publishes, and releases both video games and video game consoles. The history of Nintendo began when craftsman Fusajiro Yamauchi ...
releases the
video game A video game or computer game is an electronic game that involves interaction with a user interface or input device (such as a joystick, game controller, controller, computer keyboard, keyboard, or motion sensing device) to generate visual fe ...
''
Computer Othello 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. Av ...
'' in arcades. *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. Peter W Frey of
Northwestern University Northwestern University (NU) is a Private university, private research university in Evanston, Illinois, United States. Established in 1851 to serve the historic Northwest Territory, it is the oldest University charter, chartered university in ...
discussed computer and human Othello strategies in ''BYTE'', and discussed his
TRS-80 The TRS-80 Micro Computer System (TRS-80, later renamed the Model I to distinguish it from successors) is a desktop microcomputer developed by American company Tandy Corporation and sold through their Radio Shack stores. Launched in 1977, it is ...
Othello game which, Frey claimed, easily defeated Wright's version running on a
CDC 6600 The CDC 6600 was the flagship of the 6000 series of mainframe computer systems manufactured by Control Data Corporation. Generally considered to be the first successful supercomputer, it outperformed the industry's prior recordholder, the I ...
. Paul Rosenbloom of
Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...
developed IAGO, which finished in third place at a Northwestern University computer tournament. When IAGO played The Moor, IAGO was better at capturing pieces permanently and limiting its opponent's mobility. *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 The University of California, Santa Cruz (UC Santa Cruz or UCSC) is a public university, public Land-grant university, land-grant research university in Santa Cruz, California, United States. It is one of the ten campuses in the University of C ...
, 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 In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a Sign (mathematics), signed sequence of a fixed number of digits in some Radix, base) multiplied by an integer power of that ba ...
. *Late 1980s:
Kai-Fu Lee Kai-Fu Lee (; born December 3, 1961) is a Taiwanese businessman, computer scientist, investor, and writer. He is currently based in Beijing, China. Lee has worked as an executive, first at Apple, then SGI, Microsoft, and Google. He became the ...
and Sanjoy Mahajan created the Othello program BILL, which was similar to IAGO but incorporated Bayesian learning. BILL reliably beat IAGO. *1992:
Michael Buro 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. Professional career Michael Buro is a professor at the University of Alberta in ...
began work on the Othello program
Logistello 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 &md ...
. 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. *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. *1998:
Michael Buro 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. Professional career Michael Buro is a professor at the University of Alberta in ...
retired Logistello. Research interest in Othello waned somewhat, but some programs, including Ntest, Saio, Edax, Cassio, Zebra and Herakles, continued to be developed. *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.


List of top Othello/ Reversi programs

# NTest
Ntest
by Chris Welty # Edax
Edax
) by Richard Delorme #
Logistello 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 &md ...

Logistello
by
Michael Buro 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. Professional career Michael Buro is a professor at the University of Alberta in ...


See also

*
Computer Go 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 ...
*
Computer shogi Computer shogi is a field of artificial intelligence concerned with the creation of computer programs which can play shogi. The research and development of shogi software has been carried out mainly by freelance programmers, university research gro ...
*
Computer chess Computer chess includes both hardware (dedicated computers) 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 analysi ...
*
Computer Olympiad The Computer Olympiad is a multi-games event in which computer programs compete against each other. For many games, the Computer Olympiads are an opportunity to claim the "world's best computer player" title. First contested in 1989, the major ...
*
Reversi 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. Basics Two players compete, using 64 identi ...


Notes


External links

{{wiktionary
4 × 4 Othello



Chess programming

Play Othello Online vs Computer
Reversi software Abstract strategy games PSPACE-complete problems