Annotated bibliography of Othello programming

I also have nearly all the back issues of Othello Quarterly. I intend to add them to this reference in the future.

Entries are in alphabetical order of author.

"The Expected-Outcome Model of Two-Player Games"

This thesis focus on a statistical interpretation of game-trees. The author used Othello and tic-tac-toe to test the decision quality of the expected-outcome model. Used weighted square functions for the Othello evaluator.

"Alpha-Beta Conspiracy-Number Search"

Advances in Computer Chess 6, 1991, pp. 73-95.

Beal, D. F. [editor]

CN-search is a best-first game tree search algorithm, introduced by McAllester (1988). Introduced here, is a variation of cn-search, Alpha-Beta-cn search which outperforms unordered alpha-beta, and SSS* on game trees with non-uniform branching factors.

"Selective Trees and Majority Systems: Two Experiments with commercial chess computers."

Advances in Computer Chess 6, 1991, pp. 37-59.

Beal, D. F. [editor]

Experiments were conducted using multiple chess programs together to vote on the best move. In the case of game play, democracy tends to lead to mediocre play. The program that was the expert in a sub-domain would be out voted by the non-experts.

"Advances in Computer Chess 6"

Mostly chess oriented with the two following exceptions, see:

· I. Althofer, "Selective Trees and Majority Systems: Two Experiments with Commercial Chess Computers"

· L. V. Allis, M. van der Meulen, H.J. van den Herik, "Alpha-Beta Conspiracy-Number Search"

"Parallel Implementation and Optimization of the Minimax Algorithm with Alpha-Beta Cutoffs in conext of the game Othello"

CRPC Summer Research Student, Caltech

"Strategy knowledge and strategy change in skilled performance: A study of the game Othello"

American Journal of Psychology, Summer 1990, Vol. 103, No. 2, pp. 145-166.

Research into the evolution of Othello player's skill. Players usually shift from the greedy strategy to positional strategies and then to mobility strategies (through exposure in the othello community). From the authors experience, the mobility strategy seemed to have been discovered once, in the mid-70s in Japan. And then spread through cultural transmission to America and Europe. The authors did not know of the mobility strategy being reinvented else where.

My experience differ from the authors. I had independently developed an understanding of mobility when I was about 14. After running out of challenging opponents and being outside the othello community, I gave up Othello for about 15 years. I returned to Othello, once I discovered computers had finally become challenging.

Moriarty and Mikkulainen's has experimented with genetic evolution of neural networks and applied it to Othello. Their experiment discovered the importance of mobility.

"ProbCut: A Powerful Selective Extension of the AlphaBeta Algorith"

buro@uni-paderborn.de, 1995, University of Paderborn, Germany

ftp://ftp.uni-paderborn.de/unix/othello/ps-files/

Presents a new method for performing forward cuts.

"Techniques for the Evaluation of Game Positions Using Examples."

Ph.D. thesis (in German), 1994, University of Paderborn, Germany.

ftp://ftp.uni-paderborn.de/unix/othello/ps-files/mics_dis.ps.gz"

"Statistical Feature Combination for the Evaluation of Game Postions"

Journal of AI Research, 1995 (Submitted)

ftp://ftp.uni-paderborn.de/unix/othello/ps-files/combi.ps.gz

Compares three means of combining feature functions. Logistic regression leads to better results than Fisher's linear discriminant and the quadratic discriminant function for normally distributed features.

"A Comparison of Minimax Tree Search Algorithms"

Artificial Intelligence, 1983, Vol. 20, pp. 347-367

Reports on empirical performance studies on search trees with useful size and ordering properties. Emphasis is placed on trees that are strongly ordered. Algorithms compared: Alpha-Beta, Principal Variation Search, Scout, SSS*, and their hybrids. The relative strength of these algorithms depended not only on space/time considerations but also on ordering of the moves. SSS* and its' hybrid variants performed best when ordering is poor or random. On well ordered moves, the other searches algorithms performed competitively with SSS*, and they require much less resource than SSS*.

"In search of Better Decision-Making in Computer Game Playing"

PHD Dissertation, University of Maryland College Park, 1988

"Background and Origins of Othello"

Personal Computing, July 1980, pp. 87-88.

Gives a good one page history of Othello.

"Othello Tournament", and "Othello"

Personal Computing, December 1980, pp. 85.

Announcement for the first computer Othello tournament that Peter Frey hosted. Below the announcement is an ad for 6 Othello programs. Three are for Apple II. Two are for TRS-80. And one ran on the RCA Cosmac computer. Prices were from $13 to $35.

"Othello, a New Ancient Game"

BYTE, October 1977, pp. 60-62.

I remember typing this Basic program into my computer. I was 14.

It took me longer to type it in than it took me to beat it. :)

"Feature discovery for problem solving systems"

PHD Dissertation, University of Massachusetts, 1993

"This Othello is not Shakespearean"

Personal Computing, February 1980, pp. 76.

A letter to the editor. The author describes Othello and briefly mentions his Othello program that runs on a 16K TRS-80.

"Machine Othello"

Personal Computing, July 1980, pp. 89-90

Discusses Othello and his Othello program, written in Basic and does not use lookahead. The article includes a transcript of a match with his program.

"First US Othello Tournament"

Personal Computing, July 1980, pp. 88.

Another letter to the editor article. Mentions details on proposed US Othello tournament.

"Simulating Human Decision-Making on a Personal Computer"

BYTE, July 1980, pp. 56-72.

Author describes his experience in developing Othello programs. Discusses the weakness of evaluating purely by square value. And promotes the importance of edge configuration.

"The Santa Cruz Open: Othello Tournament for Computers"

BYTE, July 1981, pp. 26-37.

Twenty programs competed at UCSC. Back when Othello programs were easier to beat than write.

"Chess skill in man and machine"

Only of historical interest in computer chess. The search techniques are better illustrated in Levy and Newborns book.

"Genetic Learning Algorithm, Applied to the Game of Othello"

Heuristic Programming in Artificial Intelligence, the first

computer Olympiad, 1989, pp. 241-254

Levy, David, and Beal, D. F. [Editors]

Describes the use of Genetic Learning Algorithms to optimize the scoring parameters of an evaluator for Othello.

"Hardware Help in an Othello Endgame Analyzer"

Heuristic Programming in Artificial Intelligence, the first computer Olympiad, 1989, pp. 219-224

Levy, David, and Beal, D. F. [Editors]

Describes the infamous A. Computer from the Othello Quarterly. Presents details of the first and second generation in Othello endgame analyzer built to perform up to 26 ply endgame searches.

"Tree Searching Algorithms"

Computer, Chess, and Cognition, 1991, pp. 133-158.

Marsland, T. A., and Schaeffer, J. [editors]

Reviews and critiques game tree search algorithms for two-players:

AB (alpha-beta), AAB (aspiration alpha-beta), AO*, B*, cn-search, conspiracy numbers, DUAL*, FAB (fail-soft alpha-beta), INS (informed negascout), iterative-deepening, killer heuristic, min-max, minimal windows, move ordering, negamax, NS (negascout), parallel alpha-beta, PB* (probability-base B*), PS* (phase search), PVS (principal variation search), quiescence search, selective search, SSS* (state space search), transposition table, variable depth.

The bibliography, associated with this article, is an excellent reference.

"BRAND - An Othello Program"

ACM SIGART Newsletter, April 1982, Vol. 80, pp. 98-104

Discusses Othello strategy, statistics and makes comparisons with Chess. Describes Brand 2.2 as a brute-force Othello program:

Alpha-Beta with killer responses, rudimentary quiescence search, simple time-control algorithm, and static move ordering. The evaluator used mobility, square occupied, value of discs flipped, and the number of directions in which disc are flipped. Mobility was calculated for both the final depth D and D-1. This was to get around the temporary loss or gain of mobility, which would vanish with the next move.

"New Concepts in Computer Othello Cornder Value, Edge Avoidance, Access, and Parity"

Heuristic Programming in Artificial Intelligence, the first computer Olympiad, 1989, pp. 225-240

Levy, David, and Beal, D. F. [Editors]

Describes the evaluator function of Peer Gynt. Besides square evaluation and mobility, Peer Gynt makes us of four additional concepts: Corner Value, Edge Avoidance, Access, and Parity.

"Learning of Position Evaluation in the Game of Othello"

1995, Computer Science Department, Lederle Graduate Research Center, University of Massachusetts

ftp://ftp.cs.umass.edu/pub/techrept/ABSTRACT/UM-CS-1995-023.ABS

"Heuristic Programming in Artificial Intelligence, the first computer Olympiad"

Details the results of an event in which 85 programs from 16 countries competed against each other at 14 different games of skill. 15 programs competed in the Othello tournament. The top three Othello programs were POLYGON, COMP'OTH, and BADIA.

During the Olympiad, a conference on computer games was held, which three papers were delivered on Othello.

See:

· C. Hewlett, "Hardware Help in an Othello Endgame Analyzer"

· A. Kierulf, "New Concepts in Computer Othello: Corner Value, Edge Avoidance, Access and Parity"

· G.M. Gupton, "Genetic Learning Algorithm Applied to the Game of Othello"

Another article discussed BMP game tree search algorithm. See:

· W. Nagl, "Best-Move-Proving: A Fast Game-Tree Searching Algorithm"

"Heuristic Programming in Artificial Intelligence, the second computer Olympiad"

50 programs participated in 13 game contest. 6 programs competed in the Othello tournament. None of the five top programs from the previous year attended. An American program IAGO had an evaluation functions derived from a genetic "learning" algorithm. It's poor performance was possibly explained by "inbreeding".

Also see one of the conference papers on othello:

· Jean-Christophe Weill, "Experiments with the NegaC* Search, An Alternative for Othello Endgame Search"

"A Pattern Classification Approach to Evaluation Function Learning"

Artificial Intelligence, 1988, Vol. 36, pp. 1-25

Details the evaluator and its' derivation for Bill 3.0. Presented is an algorithm for deriving evaluation functions. Based on Bayesian learning, the algorithm uses a training database to learn the optimal quadratic combination of the feature set. The resulting evaluation functions produces an estimate for the probability of winning, an expected outcome.

"The Development of a World Class Othello Program"

Artificial Intelligence, 1990, Vol. 43, pp. 21-36.

Describes Othello program, Bill. Bayesian learning was used to derive the weighted combinations in Bill's pre-computed evaluation tables: mobility, potential mobility, weighted square, and edge. Bill also uses iterative deepening, hashed response and killer tables, zero-window search, and two-phase endgame search.

"How computers play chess"

Besides talking about the history of computer Chess, it has a good introduction to Alpha-Beta, Iterative Deepening, and Hash tables. Each concept is nicely illustrated.

"Programming Strategies in the Game of Reversi"

BYTE, November 1979, pp. 66-78.

One of the earliest articles on computer othello. Includes a Basic Program, which performs 2-ply minimax search. The evaluator uses a strategic value for each squares, i.e. Hasegawa weighting, weighted squares, or square priority.

"Low Overhead Alternatives to SSS*"

Artificial Intelligence, 1987, Vol. 31, pp. 185-199

Discusses DUAL, a hybrid of State Space Search (SSS*) and Alpha-Beta that requires less resources than standard SSS*. This was another case that one search algorithm was better than another in certain cases. SSS* outperformed on even-ply searches and INS (Informed Nega-Scout) outperformed in the odd-ply searches. DUAL* has the best performance of SSS* and INS. DUAL* space requirements can be less than that of SSS* at the cost of some degradation in performance.

"Computers, Chess, and Cognition"

Mainly about computer chess. Two chapters cover some issues with computer GO. Chapter 8 has an excellent review of search algorithms for two-player games, see: H. Kaindl, "Searching Algorithms".

"Using Features to Evaluate Positions in Experts' and Novices' Othello Games"

1984,Northwestern University

"Evolving Neural Networks to Focus Minimax Search"

Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94)

also available by ftp: cs.utexas.edu

Used genetic algorithms to evolve neural networks that were trained to decide which moves are promising enough to explore. The networks were able to guide the minmax search away from poor information from the evaluation function. This resulted in stronger play while fewer states. Used Othello as the testing environment.

"Evolving Complex Othello Strategies Using Marker-Based Genetic Encoding of Neural Networks"

Technical Report AI93-206, The University of Texas at Austin

also available by ftp: cs.utexas.edu

Presented an encoding scheme which allowed the artificial evolution of neural networks for the development of new game playing strategies. The game-playing networks were forced to evolve strategies in Othello. The networks first discovered a positional strategy, then latter discovered mobility strategy.

"Evolutionary Neural Networks for Value Ordering in Constraint Satisfaction Problems"

Technical Report AI94-218, The University of Texas at Austin

also available by ftp: cs.utexas.edu

Continuing their research in the artificial evolution of neural networks. Applying to the move ordering of depth first searches.

"Best-Move-Proving: A fast Game-Tree Searching Algorithm"

Heuristic Programming in Artificial Intelligence, the first computer Olympiad, 1989, pp. 255-272

Levy, David, and Beal, D. F. [Editors]

Presents BMP which computes the best move without returning the exact evaluation value for the best move. Best case of BMP is always better that Alpha-Beta, worst case of BMP is always worse than Alpha-Beta. The medium case is sometimes better, sometimes worse that Alpha-Beta. The consequence of this is that one should try both BMP and Alpha-Beta to find out which is most appropriate.

"Asymptotic Properties of Minimax Trees and Game-Searching Procedures"

Artificial Intelligence, 1980, Vol. 14, pp. 113-138.

Math! (like most of Pearl's work)

Discusses Alpha-Beta and Scout. Alpha-Beta with optimal pruning has a branching rate the square root of the MinMax branching rate.

"Game-Searching Theory: Survey of Recent Results"

ACM SIGART Newsletter, April 1982, Vol. 80, pp. 70-75

More Math!

Discusses Alpha-Beta and SSS* algorithms, the effects of move ordering, and the effects of search depth on the quality of decision.

When the moves are randomly ordered, Alpha-Beta explores n/log(n) of the legal moves. When the moves are perfectly ordered, Alpha-Beta explores sqrt(n) of the legal moves.

"The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality"

Communications of the ACM, August 1982, Vol. 25, No. 8, pp. 559-564.

And Even More Math!

Analyzes the average number of terminal nodes examined by alpha-beta pruning in a uniform game tree of degree N (i.e. branching) and depth D for which the terminal values are drawn at random from a continuos distribution.

For a given search time, Alpha-Beta pruning allows the search depth to be increased by approximately 4/3 over that of an exhaustive minimax search.

Alpha-Beta explores only a fraction of the legal moves, approximately N^(-1/4) for N<=1000.

"Modeling of heuristic evaluation strategies in game playing: linear and configural effects in Othello"

PHD Dissertation, University of Maryland College Park, 1981

"Parallel Tree Search on a Single-Instruction, Multiple-Data (SIMD) Machine"

PHD Dissertation, University of California, Los Angeles, 1993

"A World-Championship-level Othello program"

Artificial Intelligence, 1982, Vol. 19, pp. 279-320.

Describes Othello program, IAGO. Used many of the same techniques of computer chess programs from that same era: Iterative deepening, killer response tables, and tournament time management. IAGO's evaluator linearly combined edge stability, internal stability, current mobility and potential mobility. The weighting of these four features were adjusted by the move turn. IAGO did not have an opening book. Many of the references were from Othello Quarterly.

"Do the Right Thing: studies in limited rationality"

Their focus is on how (and the philosophy) to search for optimal behavior (make the right move) when the system has limited resources (up against a clock).

Another Best-First game tree search algorithm. The nodes of the search tree are expanded selectively, based on their utility in the decision process. This requires a utility function in addition to an evaluator function. Othello is one of their test-beds. When compared to 6-ply Alpha-Beta, MGSS* visits one-tenth the nodes. This approach has a large amount of memory overhead, because it requires the search tree to be held in memory.

"An Adaptive Othello Player: Experience-Based Learning Applied to Game Playing

Proceedings of the AAAI Spring Symposium, 1988

"Design and Analysis of parallel algorithms for game-tree search"

PHD dissertation, The University of Wisconsin-Madison, 1991

"REVERSI: An experiment in Game-Playing Programs"

ACM SIGART Newsletter, April 1982, Vol. 80, pp. 94-98

This program uses a bounded depth-first alpha-beta. The depth is adjusted from turn to turn based upon time previously used.

"A Parallel Network that Learns to Play Backgammon"

Artificial Intelligence, 1989, Vol. 39, pp. 357-390

Use of neural networks and sample game problems to build by example an evaluator. Backgammon is a game that traditional search algorithms are ineffective because of the large branching at each move.

"Experiments with The NegaC* Search, An Alternative for Othello Endgame Search"

Heuristic Programming in Artificial Intelligence, the second computer olympiad, 1991, pp. 174-188

Levy, David, and Beal, D. F. [Editors]

Paper presents experiments made by the author with the NegaC* search in Othello endgames. NegaC* is mathematically analyzed and compared to Alpha-Beta and NegaScout. When used for exact-outcome, NegaC* would only out perform Alpha-Beta if tree caching was available. For expected-outcome, NegaC* performed in half the time. For Othello, this could translate to an extra half ply in search. I don't immediately agree with the author that NegaC* is the most suitable algorithm for Othello endgame. Comparison with optimized variations of Alpha-Beta, such as PVS and SSS*, would have given more merit to the authors claim.

"OTHELLO"

Creative Computing, Nov-Dec 1977, pp. 140-142

Best of Creative Computing, Vol 4., pp. 258-260

Source code for an Othello program written in Fortran. Earliest published program that I know of.

Visit the Illuminati Online home page.