Home * Games * Othello
external image 250px-Othello_%28Reversi%29_board.jpg

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.
Reversi/Othello [1]

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 corner squares. In conjunction with probability based pruning aka ProbCut, Michael Buro elaborately addresses the evaluation function [18] [19] [20]. Further, Yasuhiro Osaki, Kazutomo Shibahara, Yasuhiro Tajima, and Yoshiyuki Kotani applied Temporal Difference Learning to an Othello evaluation function [21].

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 [22] demonstrates determining mobility, while the implementation by co-author Toshihiko Okuhara in their program Zebra [23] looks parallel prefixed [24].

Solving Othello

Othello on 4×4 [25] and 6×6 board [26] 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 [27]. While still mathematically unsolved, there is strong suspicion that perfect play on both sides results in a draw [28] [29].

See also


Publications

1980 ...

1990 ...

2000 ...

2010 ...


Forum Posts


External Links


References

  1. ^ Reversi from Wikipedia
  2. ^ Writing an Othello program by Gunnar Andersson
  3. ^ Dan and Kathe Spracklen - The Othello Wiki Book Project
  4. ^ The Othello Museum - Reversi Sensory Challenger
  5. ^ Odin - The Othello Wiki Book Project
  6. ^ Stuart Russell and 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.
  7. ^ Stuart Russell and 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
  8. ^ 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
  9. ^ 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
  10. ^ Michael Buro (1995). ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm. ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf
  11. ^ Logistello's Homepage
  12. ^ Michael Buro (1994). Techniken für die Bewertung von Spielsituationen anhand von Beispielen. Ph.D. Thesis. University of Paderborn, Paderborn, Germany. pdf (German)
  13. ^ Mark Brockington, Jonathan Schaeffer (1996). The APHID Parallel αβ Search Algorithm. Technical Report 96-07, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada. as pdf from CiteSeerX
  14. ^ Mark Brockington, Jonathan Schaeffer (1997). APHID Game-Tree Search. Advances in Computer Chess 8
  15. ^ APHID Parallel Game-Tree Search Library
  16. ^ Mark Brockington (1998). Asynchronous Parallel Game-Tree Search. Ph.D. Thesis, University of Alberta, zipped postscript
  17. ^ Jean Méhat, Tristan Cazenave (2011). A Parallel General Game Player. KI Journal, Vol. 25, No. 1, pdf
  18. ^ Michael Buro (1997). An Evaluation Function for Othello Based on Statistics. NEC Research Institute. Technical Report #31.
  19. ^ 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
  20. ^ 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.
  21. ^ 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
  22. ^ bitboard mobility Copyright (c) 2003, Gunnar Andersson
  23. ^ Zebra by Gunnar Andersson
  24. ^ bitbmob.c in zebra.tar.gz
  25. ^ AI Lab - Othello 4x4
  26. ^ The perfect play line in 6x6 Othello
  27. ^ Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, pdf
  28. ^ Computer opponents and research from Wikipedia
  29. ^ 2004 Opening Book Skeleton
  30. ^ Aart Bik - The Othello Wiki Book Project

What links here?


Up one Level