Othello,
or differing in not having a defined starting position, Reversi, is a two-playerzero-sum and perfect informationabstract strategyboard 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 on 4×4 [28] and 6×6 board [29] 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[30]. While still mathematically unsolved, there is strong suspicion that perfect play on both sides results in a draw [31][32].
Donald H. Mitchell (1984). Using Features to Evaluate Positions in Experts' and Novices' Othello Games. Masters thesis, Department of Psychology, Northwestern University, Evanston, IL
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.
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
^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.
^Jean-Christophe Weill (1991). Experiments With the NegaC* Search - An Alternative for Othello Endgame Search. Heuristic Programming in Artificial Intelligence 2: the second computer olympiad (eds. David Levy and Don Beal), pp. 174-188. Ellis Horwood, Chichester. ISBN 0-13-382615-5, zipped ps and pdf from CiteSeerX
^Michael Buro (1994). Techniken für die Bewertung von Spielsituationen anhand von Beispielen. Ph.D. Thesis. University of Paderborn, Paderborn, Germany. pdf (German)
^Michael Buro (1997). An Evaluation Function for Othello Based on Statistics. NEC Research Institute. Technical Report #31.
^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
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.
Table of Contents
Othello Programming
Writing an Othello program [2] 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 [3], marketed as Reversi Sensory Challenger [4] by Fidelity Electronics. Larry Atkin and Peter W. Frey wrote the commercial program Odin in the early 80s as well [5]. 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 [6] and 1989 [7] respectively. In Othello, there is no concept of standing pat or quiescence, and null move pruning does not work.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 [18], current mobility and potential mobility, weighted by coefficients as suggested by Hans Berliner [19] [20]. In conjunction with probability based pruning aka ProbCut, Michael Buro elaborately addresses the evaluation function [21] [22] [23]. Further, Yasuhiro Osaki, Kazutomo Shibahara, Yasuhiro Tajima, and Yoshiyuki Kotani applied Temporal Difference Learning to an Othello evaluation function [24].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 [25] demonstrates determining mobility, while the implementation by co-author Toshihiko Okuhara in their program Zebra [26] looks parallel prefixed [27].Solving Othello
Othello on 4×4 [28] and 6×6 board [29] 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 [30]. While still mathematically unsolved, there is strong suspicion that perfect play on both sides results in a draw [31] [32].Computer Olympiads
See also
Publications
1979
1980 ...
1985 ...
1990 ...
1995 ...
2000 ...
2005 ...
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
20142015 ...
Forum Posts
External Links
References
What links here?
Up one Level