Othello

Home * Games * Othello

Reversi/Othello ¹

Othello,
or differing in not having a defined starting position, Reversi, is a two-player zero-sum and perfect information abstract strategy board game, usually played on a board with 8 rows and 8 columns and a set of light and a dark turnable pieces for each side. The player's goal is to have a majority of their colored pieces showing at the end of the game, turning over as many of their opponent's pieces as possible. The dark player makes the first move from the starting position, alternating with the light player. Each player has to place a piece on the board such that there exists at least one straight (horizontal, vertical, or diagonal) occupied line of opponent pieces between the new piece and another own piece. After placing the piece, the side turns over (flips, captures) all opponent pieces lying on any straight lines between the new piece and any anchoring own pieces. |}

Othello Programming

Writing an Othello program ¹ is an appealing and interesting challenge. Beside the dedicated Othello programmers Gunnar Andersson, Michael Buro, Mark Brockington, Paul Hsieh, and Andrea Zinno, to name a few, many chess programmers were and are busy in this domain as well. Already in 1981 Dan and Kathe Spracklen wrote a commercial Reversi program, marketed as Reversi Sensory Challenger ² by Fidelity Electronics. Larry Atkin and Peter W. Frey wrote the commercial program Odin in the early 80s as well ³. Other programmers to mention are Aart Bik, Bruno Bras, Dennis Breuker, Joost Buijs, Jonathan Kreuzer, Fabien Letouzey, Steve Maughan, and Jean-Christophe Weill.

Search

In Othello, similar to chess, search implementations are dominated by alpha-beta and variants so far. An alternative approach called MGSS and MGSS* was proposed by Stuart Russell and Eric Wefald in 1988 ⁴ and 1989 ⁵ respectively. In Othello, there is no concept of standing pat or quiescence, and null move pruning does not work.

• Jean-Christophe Weill elaborated on NegaC* ⁶ and for parallel search on ABDADA ⁷.
• Michael Buro successfully implemented his ProbCut and Multi-ProbCut (MPC) as selective extension ⁸ inside his successful Othello program Logistello ⁹, already described in his Ph.D. thesis ¹⁰.
• The Asycnhronous Parallel Hierarchical Iterative Deepening algorithm, APHID by Mark Brockington was applied to Othello as well ^{11 12 13 14}.
• In 2011, Jean Méhat and Tristan Cazenave implemented Monte-Carlo Tree Search in parallel General Game Playing, also covering Othello with promising results ¹⁵.

Evaluation

Despite material as decisive feature in Othello, it is also a volatile one and difficult to evaluate. Othello programmers often use piece-square tables, mobility and take various other features, pattern, and heuristics into account, considering strategic elements like the importance of the edge squares. Paul Rosenbloom's program Iago of the early 80s used edge stability, internal stability ¹⁶, current mobility and potential mobility, weighted by coefficients as suggested by Hans Berliner ^{17 18}. In conjunction with probability based pruning aka ProbCut, Michael Buro elaborately addresses the evaluation function ^{19 20 21}. Further, Yasuhiro Osaki, Kazutomo Shibahara, Yasuhiro Tajima, and Yoshiyuki Kotani applied Temporal Difference Learning to an Othello evaluation function ²².

Bitboards

Othello is very bitboard friendly. It seems that Dumb7Fill or Kogge-Stone Fill Algorithms are suitable to generate moves. Generator sets are the own pieces, propagator sets the opponent ones. The fill result, after a final direction shift similar as fill based sliding piece attacks in chess, needs an intersection with empty squares to determine the target squares per direction. Beside the target square coordinate, move encoding may incorporate a direction set (one Byte with one distinct bit per direction) for all eight directions with anchor squares, and possibly the number of pieces to flip, may be even as set for more reliable move ordering and faster make move. An MMX implementation of Dumb7Fill in inline assembly by Gunnar Andersson ²³ demonstrates determining mobility, while the implementation by co-author Toshihiko Okuhara in their program Zebra ²⁴ looks parallel prefixed ²⁵.

Solving Othello

Othello on 4×4 ²⁶ and 6×6 board ²⁷ are strongly solved and proved as a second player (white) to win. For 8x8 boards, Victor Allis estimated the number of legal positions in Othello is at most 1028, and it has a game-tree complexity of approximately 1058 ²⁸. While still mathematically unsolved, there is strong suspicion that perfect play on both sides results in a draw ^{29 30}.

Computer Olympiads

• 1st Computer Olympiad, London 1989
• 2nd Computer Olympiad, London 1990
• 3rd Computer Olympiad, Maastricht 1991
• 4th Computer Olympiad, London 1992
• 20th Computer Olympiad, Leiden 2017

Photos

20th Computer Olympiad, Leiden 2017, Othello 10x10 winners, Shun-Chin Hsu (Mothello10, Bronze),
Fabien Letouzey with WCCC 2005 shirt (Decapus, Gold) and Andrew Lin (Deep Nikita, Silver) ³¹

Othello Programs

• Bill by Kai-Fu Lee and Sanjoy Mahajan

See also

• ABDADA
• APHID
• Monte-Carlo Tree Search
• ProbCut
• SANE

Publications

1979

• Peter B. Maggs (1979). Programming Strategies in the Game of Reversi. BYTE, Vol. 4, No. 11, pp. 66-79

1980 ...

• Ed Wright (1980). Othello. The Best of Creative Computing Volume 3
• Editor (1980). Background and Origins of Othello. Personal Computing, Vol. 4, No. 7, pp. 87
• Peter W. Frey (1980). Machine Othello. Personal Computing, Vol. 4, No. 7, pp. 89
• Paul S. Rosenbloom (1981). A world-championship-level Othello program. Technical report, Carnegie Mellon University, pdf
• Alan S. Wolff, Donald H. Mitchell, Peter W. Frey (1984). Perceptual Skill in the Game of Othello. The Journal of Psychology, Vol. 118, No. 1
• Donald H. Mitchell (1984). Using Features to Evaluate Positions in Experts' and Novices' Othello Games. Master thesis, Department of Psychology, Northwestern University, Evanston, IL

1985 ...

• Kai-Fu Lee, Sanjoy Mahajan (1986). BILL: a table-based, knowledge-intensive othello program. Technial Report CMU-CS-86-141, Carnegie Mellon University, pdf
• Kai-Fu Lee (1986). A pattern classification approach to evaluation function learning. Technial Report CMU-CS-86-173, Carnegie Mellon University
• Kai-Fu Lee, Sanjoy Mahajan (1988). A Pattern Classification Approach to Evaluation Function Learning. Artificial Intelligence, Vol. 36, No. 1
• Stuart Russell, Eric Wefald (1988). Decision-Theoretic Search Control: General Theory and an Application to Game-Playing. Computer Science Division Technical Report 88/435, University of California, Berkeley, CA.
• Kenneth A. De Jong, Alan C. Schultz (1988). Using Experience-Based Learning in Game Playing. Proceedings of the Fifth International Machine Learning Conference, CiteSeerX » Learning
• Stuart Russell, Eric Wefald (1989). On optimal game-tree search using rational metareasoning. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, MI: Morgan Kaufmann, pdf
• Clarence Hewlett (1989). Hardware Help on an Othello Endgame Analyzer. Heuristic Programming in AI 1
• Anders Kierulf (1989). New Concepts in Computer Othello: Corner Value, Edge Advoidance, Access, and Parity. Heuristic Programming in AI 1
• Greg M. Gupton (1989). Genetic Learning Algorithm Applied to the Game of Othello. Heuristic Programming in AI 1

1990 ...

• Kai-Fu Lee, Sanjoy Mahajan (1990). The Development of a World Class Othello Program. Artificial Intelligence, Vol. 43, No. 1
• Jean-Christophe Weill (1991). Experiments With the NegaC* Search - An Alternative for Othello Endgame Search. Heuristic Programming in AI 2
• Richard Korf and Max Chickering (1994). Best-first minimax search: Othello results. Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-94), pp. 1365-1370. AAAI Press, Menlo Park, CA.
• Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, pdf
• David E. Moriarty, Risto Miikkulainen (1994). Evolving Neural Networks to focus Minimax Search. AAAI-94

1995 ...

• David E. Moriarty, Risto Miikkulainen (1995). Discovering Complex Othello Strategies Through Evolutionary Neural Networks. Connection Science, Vol. 7
• Anton Leouski (1995). Learning of Position Evaluation in the Game of Othello. Master's Project, University of Massachusetts, Amherst, Massachusetts, pdf
• Michael Buro (1995). Statistical Feature Combination for the Evaluation of Game Positions. JAIR, Vol. 3
• Michael Buro (1995). ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm. ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf
• Jean-Marc Alliot, Nicolas Durand (1995). A Genetic Algorithm to Improve an Othello Program. Artificial Evolution, LNCS 1063, Springer
• David Currie (1996). Othello Game Player. St. John's College, pdf
• 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, zipped ps
• Michael Buro (1997). An Evaluation Function for Othello Based on Statistics. NEC Research Institute. Technical Report #31.
• Mark Brockington (1997). KEYANO Unplugged - The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta, CiteSeerX
• Michael Buro (1997). Experiments with Multi-ProbCut and a New High-quality Evaluation Function for Othello. Technical Report No. 96, NEC Research Institute, Princeton, N.J. pdf
• Michael Buro (1997). The Othello match of the year: Takeshi Murakami vs Logistello. ICCA Journal, Vol 20, No. 3, zipped ps
• Craig S. Bruce (1998). Performance Optimization for Distributed-Shared-Data Systems. Ph.D. thesis, University of Waterloo, 6.6. Game-Tree Searching: Othello, pp. 188
• Ayumu Nagai, Hiroshi Imai (1999). Application of df-pn+ to Othello endgames. 5th Game Programming Workshop » Proof-Number Search

2000 ...

• Michael Buro (2000). Experiments with Multi-ProbCut and a new High-Quality Evaluation Function for Othello. Games in AI Research (eds. Jaap van den Herik and Hiroyuki Iida), pp. 77-96. Universiteit Maastricht, Maastricht, The Netherlands. ISBN 90-621-6416-1.
• Makoto Sakuta, Hiroyuki Iida (2001). The Performance of PN*, PDS, and PN Search on 6x6 Othello and Tsume-Shogi. Advances in Computer Games 9 » Proof-Number Search
• Michael Buro (2002). Report on the IWEC-2002 Man-Machine Othello Match. ICGA Journal, Vol. 25, No. 2, pdf
• Konstantinos Tournavitis (2002). MOUSE(μ): A Self-teaching Algorithm that Achieved Master-Strength at Othello. CG 2002
• Michael Buro (2003). The Evolution of Strong Othello Programs. IFIP, Vol. 112, Springer
• C.K. Wong, K.K. Lo and P.H.W. Leong (2004). An FPGA-based Othello Endgame Solver. The Chinese University of Hong Kong, pdf

2005 ...

• Simon Lucas, Thomas Philip Runarsson (2006). Temporal Difference Learning versus Co-Evolution for Acquiring Othello Position Evaluation. IEEE CIG 2006
• Simon Lucas (2007). Learning to play Othello with N-tuple systems. Australian Journal of Intelligent Information Processing Systems, Special Issue on Game Technology, Vol. 9, No. 4
• Edward P. Manning (2007). Temporal Difference Learning of an Othello Evaluation Function for a Small Neural Network with Shared Weights. IEEE CIG 2007
• Thomas Philip Runarsson, Egill Orn Jonsson (2007). Effect of look-ahead search depth in learning position evaluation functions for Othello using -greedy exploration. IEEE CIG 2007
• Pim Nijssen (2007). Playing Othello Using Monte Carlo. Bachelor's Thesis, Maastricht University, pdf
• Yasuhiro Osaki, Kazutomo Shibahara, Yasuhiro Tajima, Yoshiyuki Kotani (2008). An Othello Evaluation Function Based on Temporal Difference Learning using Probability of Winning. CIG'08, pdf
• Toru Ueda, Tsuyoshi Hashimoto, Junichi Hashimoto, Hiroyuki Iida (2008). Weak Proof-Number Search. CG 2008 » Proof-Number Search
• Marcin Szubert, Wojciech Jaśkowski, Krzysztof Krawiec (2009). Coevolutionary Temporal Difference Learning for Othello. IEEE Symposium on Computational Intelligence and Games, pdf
• Marcin Szubert (2009). Coevolutionary Reinforcement Learning and its Application to Othello. M.Sc. thesis, Poznań University of Technology, supervisor Krzysztof Krawiec, pdf

2010 ...

• Edward P. Manning (2010). Using Resource-Limited Nash Memory to Improve an Othello Evaluation Function. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 1
• Edward P. Manning (2010). Coevolution in a Large Search Space using Resource-limited Nash Memory. GECCO '10

2011

• Jean Méhat, Tristan Cazenave (2011). A Parallel General Game Player. KI Journal, Vol. 25, No. 1, pdf
• Marcin Szubert, Wojciech Jaśkowski, Krzysztof Krawiec (2011). Learning Board Evaluation Function for Othello by Hybridizing Coevolution with Temporal Difference Learning. Control and Cybernetics, Vol. 40, No. 3, pdf
• Krzysztof Krawiec, Marcin Szubert (2011). Learning N-Tuple Networks for Othello by Coevolutionary Gradient Search. GECCO 2011, pdf
• Damjan Strnad, Nikola Guid (2011). Parallel Alpha-Beta Algorithm on the GPU. CIT. Journal of Computing and Information Technology, Vol. 19, No. 4 » GPU, Parallel Search

2012

• Paweł Liskowski (2012). Co-Evolution versus Evolution with Random Sampling for Acquiring Othello Position Evaluation. master's thesis, Poznań University of Technology, supervisor Wojciech Jaśkowski, pdf
• Sjoerd van den Dries, Marco Wiering (2012). Neural-fitted TD-leaf learning for playing Othello with structured neural networks. IEEE Transactions on Neural Networks and Learning Systems, Vol. 23, No. 11

2013

• Michiel van der Ree, Marco Wiering (2013). Reinforcement Learning in the Game of Othello: Learning Against a Fixed Opponent and Learning from Self-Play. ADPRL 2013
• Marcin Szubert, Wojciech Jaśkowski, Krzysztof Krawiec (2013). On Scalability, Generalization, and Hybridization of Coevolutionary Learning: a Case Study for Othello. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 5, No. 3
• Marcin Szubert, Wojciech Jaśkowski, Paweł Liskowski, Krzysztof Krawiec (2013). Shaping Fitness Function for Evolutionary Learning of Game Strategies. GECCO 2013, pdf
• Paweł Liskowski (2013). Quantitative Analysis of the Hall of Fame Coevolutionary Archives. GECCO '13 Companion Proceedings
• Wojciech Jaśkowski, Paweł Liskowski, Marcin Szubert, Krzysztof Krawiec (2013). Improving Coevolution by Random Sampling. GECCO 2013, pdf

2014

• Wojciech Jaśkowski, Marcin Szubert, Paweł Liskowski (2014). Multi-Criteria Comparison of Coevolution and Temporal Difference Learning on Othello. EvoApplications 2014, Springer, volume 8602
• Shi-Jim Yen, Tsan-Cheng Su, Jr-Chang Chen, Shun-Chin Hsu (2014). Solving 6x6 Othello on Volunteer Computing System. GPW-2014
• Wojciech Jaśkowski (2014). Systematic n-Tuple Networks for Othello Position Evaluation. ICGA Journal, Vol. 37, No. 2
• Thomas Philip Runarsson, Simon Lucas (2014). Preference Learning for Move Prediction and Evaluation Function Approximation in Othello. IEEE CIG 2014

2015 ...

• Mohd Nor Akmal Khalid, E. Mei Ang, Umi Kalsom Yusof, Hiroyuki Iida, Taichi Ishitobi (2015). Identifying Critical Positions Based on Conspiracy Numbers. Agents and Artificial Intelligence, ICAART 2015 - Revised Selected Papers
• Wojciech Jaśkowski, Marcin Szubert (2016). Coevolutionary CMA-ES for Knowledge-Free Learning of Game Position Evaluation. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 8, No. 4
• Wojciech Jaśkowski, Paweł Liskowski, Marcin Szubert, Krzysztof Krawiec (2016). The performance profile: A multi–criteria performance evaluation method for test–based problems. International Journal of Applied Mathematics and Computer Science, Vol. 26, No. 1
• Shantanu Thakoor, Surag Nair, Megha Jhunjhunwala (2017). Learning to Play Othello Without Human Knowledge. Stanford University, pdf » AlphaZero, MCTS, Deep Learning ³²
• Paweł Liskowski, Wojciech Jaśkowski, Krzysztof Krawiec (2017). Learning to Play Othello with Deep Neural Networks. arXiv:1711.06583 ³³
• Paweł Liskowski, Wojciech Jaśkowski, Krzysztof Krawiec (2018). Learning to Play Othello with Deep Neural Networks. IEEE Transactions on Games
• Kiminori Matsuzaki (2018). Empirical Analysis of PUCT Algorithm with Evaluation Functions of Different Quality. TAAI 2018 » PUCT
• Kiminori Matsuzaki, Naoki Kitamura (2018). Do evaluation functions really improve Monte-Carlo tree search? CG 2018, ICGA Journal, Vol. 40, No. 3
• Nai-Yuan Chang, Chih-Hung Chen, Shun-Shii Lin, Surag Nair (2018). The Big Win Strategy on Multi-Value Network: An Improvement over AlphaZero Approach for 6x6 Othello. MLMI2018
• Ching-Nung Lin, Fabien Letouzey, Shi-Jim Yen (2019). Decapus wins Othello 10 × 10 tournament. ICGA Journal, Vol. 41, No. 1 » 21st Computer Olympiad 2018

Forum Posts

• Bitboards: speeding up FirstOne by Laurent Desnogues, rgcc, April 10, 1996 » BitScan
• Othello Match & Call for Papers by Ingo Althöfer, rgcc, March 24, 1997
• Enhanced Transposition Table Cutoffs by Andrea Zinno, rgcc, July 30, 1997 » Enhanced Transposition Cutoff
• Othello man machine match by Ingo Althöfer, rgcc, August 6, 1997
• Othello endgame search question by Daniel Lidström, comp.ai.games, December 13, 2001
• stability in a Othello game by Daniel, comp.ai.games, October 10, 2002
• Performance: linux vs Windows vs Mac OS X by Richard Delorme, CCC, November 21, 2009 » Edax
• WinBoard, exotic version by Harm Geert Muller, CCC, January 15, 2011 » WinBoard

External Links

• Reversi from Wikipedia
• Computer Othello from Wikipedia
• The Othello Wiki Book Project
• The Othello Engine Protocol by Stephane Nicolet
• Othello (ICGA Tournaments)
• The strong learning Othello Programs from Machine Learning in Games by Jay Scott
• Othello Players by Wojciech Jaśkowski
• Writing an Othello program by Gunnar Andersson
• Perft for Reversi/Othello by Aart Bik » Perft ³⁴
• Andrea Zinno's Home Page - Entirely dedicated to the Othello game, by Andrea Zinno
• Othello (disambiguation) from Wikipedia

References