{{short description|Abstract strategy game}} {{For|the arcade game|Computer Othello (video game)}} {{Infobox game | title = | italic title = no | subtitle = | image_link = 250px | image_caption = | footnotes = NTest - a strong othello program }} '''Computer Othello''' refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. A version of Othello was famously included in Microsoft Windows from version 1.0 to XP, where it is simply known as Reversi.{{Citation needed|date=September 2024}}
== Availability == 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.<ref name="paper">{{Cite web|url=http://www.dcs.gla.ac.uk/~daw/masters-projects/dissertations/Colquhoun.2008.pdf|archiveurl=https://web.archive.org/web/20110103130600/http://www.dcs.gla.ac.uk/~daw/masters-projects/dissertations/Colquhoun.2008.pdf|url-status=dead|title=Dcs.gla.ac.uk|archivedate=January 3, 2011}}</ref>
== 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*.<ref>Jean-Christophe Weill (1992). The NegaC* Search. ICCA Journal, Vol. 15, No. 1, pp. 3-7.</ref> 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.<ref>{{cite journal|last=Armanto|first=Hendrawan|author2=Santoso, Joan |author3=Giovanni, Daniel |author4=Kurniawan, Faris |author5=Yudianto, Ricky |author6= Gunawan, Steven |title=Evolutionary Neural Network for Othello Game|journal=Procedia - Social and Behavioral Sciences|date=October 2012|volume=57|pages=419–425|doi=10.1016/j.sbspro.2012.09.1206|doi-access=free}}</ref>
Several heuristics are also used to reduce the size of the searched tree: good move ordering, transposition table and selective Search.<ref name = Buro>Buro, M., [http://www.cs.ualberta.ca/~mburo/ps/improve.pdf "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.), {{ISBN|90-621-6416-1}}, 2000</ref>
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<ref>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</ref> or APHID<ref>Mark Brockington (1997). KEYANO Unplugged - The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta.</ref> On recent programs, the YBWC<ref>Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). A Fully Distributed Chess Program. Advances in Computer Chess 6</ref> seems the preferred approach.
===Multi-Prob cut=== Multi-ProbCut is a heuristic used in alpha–beta pruning of the search tree.<ref name="Buro1997">{{cite journal|last1=Buro|first1=Michael|date=1997|title=Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello|url=http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.19.1136|journal=Games in AI Research|language=en|volume=34|issue=4|pages=77–96}}</ref> 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.<ref name="Bulitko2008">{{cite journal |last1=Bulitko |first1=Vadim |last2=Lustrek |first2=Mitja |last3=Schaeffer |first3=Jonathan |last4=Bjornsson |first4=Yngvi |last5=Sigmundarson |first5=Sverrir |title=Dynamic control in real-time heuristic search |journal=Journal of Artificial Intelligence Research |date=1 June 2008 |volume=32 |pages=419–452 |url=https://dl.acm.org/doi/abs/10.5555/1622673.1622683 |language=EN|doi=10.1613/jair.2497 |doi-access=free }}</ref> It is particularly useful in games such as Othello where there is a strong correlation between evaluations scores at deeper and shallower levels.<ref name="Fürnkranz2001">{{cite book |last1=Fürnkranz |first1=Johannes |title=Machines that learn to play games {{!}} Guide books |date=2001 |publisher=Nova Science Publishers, Inc. |location=Nova Science Publishers, Inc.6080 Jericho Tpke. Suite 207 Commack, NYUnited States |isbn=978-1-59033-021-0 |pages=11–59 |url=https://dl.acm.org/doi/book/10.5555/644391}}</ref><ref name="Heinz2013">{{cite book |last1=Heinz |first1=Ernst A. |title=Scalable Search in Computer Chess: Algorithmic Enhancements and Experiments at High Search Depths |date=2013 |publisher=Springer Science & Business Media |isbn=978-3-322-90178-1 |page=32 |url=https://books.google.com/books?id=KkQBCAAAQBAJ |language=en}}</ref>
== 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.<ref name="writing">{{Cite web|title=Writing an Othello program|url=http://radagast.se/othello/howto.html|access-date=2023-02-12|website=radagast.se |author1= Gunnar Andersson | date= 2007 }}</ref>
=== 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.<ref>[http://othellogateway.com/ntest/Ntest/howitworks.htm How Ntest Works] {{Webarchive|url=https://web.archive.org/web/20111109223307/http://othellogateway.com/ntest/Ntest/howitworks.htm |date=2011-11-09 }} March 02, 2005</ref> 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.<ref name="writing"/>
=== 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.<ref name="writing"/> 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.<ref name="writing"/>
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.<ref name="writing"/>
== 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.<ref name="writing"/> 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.<ref name="paper" /> Othello is strongly solved on 4×4 and 6×6 boards, with the second player (white) winning in perfect play.<ref name="Solution of Othello 4 × 4">[http://ailab.awardspace.com/othello4x4.html Solution of Othello 4 × 4] {{Webarchive|url=https://web.archive.org/web/20110707200005/http://ailab.awardspace.com/othello4x4.html |date=2011-07-07 }} September 02, 2008</ref><ref>[http://www.feinst.demon.co.uk/Othello/6x6sol.html Perfect play in 6x6 Othello from two alternative starting positions] {{webarchive |url=https://web.archive.org/web/20091101013931/http://www.feinst.demon.co.uk/Othello/6x6sol.html |date=November 1, 2009 }} November 17, 2004</ref>
=== 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).<ref name="Solution of Othello 4 × 4"/>
=== 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 w<s></s>hite wins with a +4 margin (16–20).<ref>{{Cite web|title=Tothello home page|url=http://www.tothello.com/|access-date=2023-02-12|website=www.tothello.com | author1= F. Pittner | date= July 2006 }}</ref>
=== Othello 8 × 8 === The Othello 8x8 game tree size is estimated at 10<sup>54</sup> nodes, and the number of legal positions is estimated at less than 10<sup>28</sup>. As of October 2023, a preprint claims that the game has been solved, with optimal result being draw.<ref>{{Cite web |url=https://arxiv.org/pdf/2310.19387.pdf |title=Othello is Solved |access-date=2023-11-04}}</ref><ref>{{cite web |last1=Takizawa |first1=Hiroki |url=https://github.com/eukaryo/reversi-scripts |website=Github |title=reversi-scripts |access-date=4 November 2023}}</ref> Computation results is also shared, making it one of the largest publicly available books.<ref>{{Cite web |url=https://figshare.com/articles/dataset/Analyses_of_the_Game_of_Othello_s_Positions/24420619 |title=Analyses of the Game of Othello's Positions |access-date=2023-11-04}}</ref>
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.<ref>{{Cite web |url=http://othellogateway.com/ntest |title=Strongest othello program in term of artificial intelligent |access-date=2010-04-05 |archive-url=https://web.archive.org/web/20070109170329/http://othellogateway.com/ntest |archive-date=2007-01-09 |url-status=dead }}</ref>{{failed verification|date=July 2023}} The parallel opening has strong advantages for the black player, enabling black to always win in a perfect play.<ref>{{Cite web|title=SaioApp project – The strongest Othello engine|url=https://www.romanobenedetto.it/|access-date=2023-02-12|language=en-US}}</ref>{{failed verification|date=July 2023}}
== Milestones in computer Othello == {{Othello diagram | right | <!-- board a b c d e f g h (X: black, O: white) --> <!-- 1 --> |X|X|X|X|X|X|X|X <!-- 2 --> |X|X|O|X|X|X|X|X <!-- 3 --> |X|X|X|O|X|X|O|X <!-- 4 --> |X|X|O|X|X|O|X|X <!-- 5 --> |X|X|X|X|X|X|X|X <!-- 6 --> |X|X|X|O|X|X|X|X <!-- 7 --> |X|X|O|O|O|X|X|X <!-- 8 --> |X|X|X|X|X|X|X|X | Logistello vs. Takeshi Murakami (4th Game) }}
*'''1977''': Scientific American made the earliest known published reference to an Othello/Reversi program, written by N. J. D. Jacobs in BCPL.<ref>Gardner, Martin. Mathematical Recreations. Scientific American, April 1977.</ref> ''BYTE'' published "Othello, a New Ancient Game" as a BASIC type-in program in October.<ref name="duda197710">{{Cite magazine |last=Duda |first=Richard O |date=October 1977 |title=Othello, a New Ancient Game |url=https://archive.org/stream/byte-magazine-1977-10/1977_10_BYTE_02-10_Implementing_Space_War#page/n61 |magazine=BYTE |pages=60–62}}</ref> *'''1977''': Creative Computing published a version of Othello written by Ed Wright in FORTRAN.<ref name="wright19771112">{{cite news | url=http://www.atariarchives.org/bcc3/showpage.php?page=258 | title=Othello | work=Creative Computing | date=November–December 1977 | access-date=18 October 2013 | author=Wright, Ed | pages=140–142}}</ref>{{r|frey198007}} *'''1978''': Nintendo releases the video game ''Computer Othello'' in arcades.<ref>{{Cite web|url=https://www.arcade-museum.com/game_detail.php?game_id=7380|title = Computer Othello - Videogame by Nintendo}}</ref> *'''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.<ref name="The History of Computer Games">{{Cite web|url=http://userhome.brooklyn.cuny.edu/cirasella/Presentations/computer_games_handout.pdf|archiveurl=https://web.archive.org/web/20110124212107/http://userhome.brooklyn.cuny.edu/cirasella/Presentations/computer_games_handout.pdf|url-status=dead|title=The History of Computer Games|archivedate=January 24, 2011}}</ref> 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.<ref name="frey198007">{{cite news | url=https://archive.org/stream/byte-magazine-1980-07/1980_07_BYTE_05-07_Computers_and_Education#page/n57/mode/2up | title=Simulating Human Decision-Making on a Personal Computer | work=BYTE | date=July 1980 | access-date=18 October 2013 | author=Frey, Peter W | pages=56}}</ref> Paul Rosenbloom of Carnegie Mellon University developed '''IAGO''', which finished in third place at a Northwestern University computer tournament.{{r|frey198107}} When IAGO played The Moor, IAGO was better at capturing pieces permanently and limiting its opponent's mobility.<ref name="The History of Computer Games" /> *'''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.<ref name="frey198107">{{cite news | url=https://archive.org/stream/byte-magazine-1981-07/1981_07_BYTE_06-07_Energy_Conservation#page/n27/mode/2up | title=The Santa Cruz Open / Othello Tournament for Computers | work=BYTE | date=July 1981 | access-date=18 October 2013 | author=Frey, Peter W | pages=16}}</ref> *'''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.<ref name="The History of Computer Games" /> *'''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.<ref name="The History of Computer Games" /> *'''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.<ref>{{Cite web|title=Othello match of the year|url=https://skatgame.net/mburo/event.html|access-date=2023-02-12|website=skatgame.net | author1= Michael Buro | date= 20 August 1997 }}</ref><ref name="The History of Computer Games" /> *'''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.<ref name="The History of Computer Games" /> *'''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.<ref>{{cite web |last1=Yamana |first1=Takuto |title=Egaroucid Self-Play Transcripts |url=https://www.egaroucid.nyanyan.dev/en/technology/transcript/ |website=Othello AI Egaroucid |access-date=5 November 2023}}</ref>
== List of top Othello/ Reversi programs == # NTest ([https://web.archive.org/web/20120116085700/http://othellogateway.com/ntest/Ntest/ Ntest]) by Chris Welty # Edax ([http://abulmo.perso.neuf.fr/edax/4.2/index.htm Edax] {{Webarchive|url=https://web.archive.org/web/20130406015023/http://abulmo.perso.neuf.fr/edax/4.2/index.htm |date=2013-04-06 }}) by Richard Delorme # Logistello ([https://skatgame.net/mburo/log.html Logistello]) by Michael Buro
== See also == {{div col|colwidth=30em}} * Computer Go * Computer shogi * Computer chess * Computer Olympiad * Reversi {{div col end}}
== Notes == {{reflist}}
== External links == {{wiktionary}} * [https://web.archive.org/web/20110707200005/http://ailab.awardspace.com/othello4x4.html 4 × 4 Othello] * [https://web.archive.org/web/20091101013931/http://www.feinst.demon.co.uk/Othello/6x6sol.html 6 × 6 Othello] * [http://chessprogramming.org/Othello Chess programming] * [https://playpager.com/othello-reversi/ Play Othello Online vs Computer]
Category:Reversi software Category:Abstract strategy games Category:PSPACE-complete problems