Othello

From Chessprogramming wiki
Jump to: navigation, search

Home * Games * Othello

Reversi/Othello [1]

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 [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, marketed as Reversi Sensory Challenger [3] by Fidelity Electronics. Larry Atkin and Peter W. Frey wrote the commercial program Odin in the early 80s as well [4]. 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 [5] and 1989 [6] 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 [17], current mobility and potential mobility, weighted by coefficients as suggested by Hans Berliner [18] [19]. In conjunction with probability based pruning aka ProbCut, Michael Buro elaborately addresses the evaluation function [20] [21] [22]. Further, Yasuhiro Osaki, Kazutomo Shibahara, Yasuhiro Tajima, and Yoshiyuki Kotani applied Temporal Difference Learning to an Othello evaluation function [23].

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

Solving Othello

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

Computer Olympiads

Photos

Olympiad2017Othello10x10.jpg

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) [32]

See also

Publications

1979

1980 ...

1985 ...

1990 ...

1995 ...

2000 ...

2005 ...

2010 ...

2011

2012

2013

2014

2015 ...

Forum Posts

External Links

References

  1. Reversi from Wikipedia
  2. Writing an Othello program by Gunnar Andersson
  3. The Othello Museum - Reversi Sensory Challenger
  4. Odin - The Othello Wiki Book Project
  5. 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.
  6. 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
  7. 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
  8. 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
  9. Michael Buro (1995). ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm. ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf
  10. Logistello's Homepage
  11. Michael Buro (1994). Techniken für die Bewertung von Spielsituationen anhand von Beispielen. Ph.D. Thesis. Paderborn University, Paderborn, Germany. pdf (German)
  12. 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
  13. Mark Brockington, Jonathan Schaeffer (1997). APHID Game-Tree Search. Advances in Computer Chess 8
  14. APHID Parallel Game-Tree Search Library
  15. Mark Brockington (1998). Asynchronous Parallel Game-Tree Search. Ph.D. Thesis, University of Alberta, zipped postscript
  16. Jean Méhat, Tristan Cazenave (2011). A Parallel General Game Player. KI Journal, Vol. 25, No. 1, pdf
  17. stability in a Othello game by Daniel, comp.ai.games, October 10, 2002
  18. Hans Berliner (1980). Backgammon Computer Program Beats World Champion. Artificial Intelligence, Vol. 14, hosted by Backgammon Galore, reprinted in David Levy (ed.) (1988). Computer Games I
  19. Paul S. Rosenbloom (1981). A world-championship-level Othello program. Technical report, Carnegie Mellon University, pdf
  20. Michael Buro (1997). An Evaluation Function for Othello Based on Statistics. NEC Research Institute. Technical Report #31.
  21. 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
  22. 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.
  23. 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
  24. bitboard mobility Copyright (c) 2003, Gunnar Andersson
  25. Zebra by Gunnar Andersson
  26. bitbmob.c in zebra.tar.gz
  27. AI Lab - Othello 4x4
  28. Shi-Jim Yen, Tsan-Cheng Su, Jr-Chang Chen, Shun-Chin Hsu (2014). Solving 6x6 Othello on Volunteer Computing System. GPW-2014
  29. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, pdf
  30. Computer opponents and research from Wikipedia
  31. 2004 Opening Book Skeleton
  32. Events 2017: Dinner - Photo 24 of 25 by Jan Krabbenbos
  33. GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)
  34. Aart Bik - The Othello Wiki Book Project

Up one Level