Computer Othello

from Wikipedia, the free encyclopedia

Computer Othello is the implementation of the game Othello for computer through algorithms .

Availability

There are numerous Othello programs such as NTest , Saio , Edax, Caissio, Herakles, WZebra and Logistello . These can be downloaded free of charge from the Internet. The programs mentioned are capable of beating the best human gamers when run on updated hardware . In addition, there are numerous implementations that can be played directly online , for example using a Java applet . However, these are usually much less powerful than the above. Programs. There are also programs that are aimed at ambitious players and are intended to help practice certain game situations. A well-known representative is happy ending , which helps to identify the right moves in an ambiguous endgame situation in order to have more pieces than the opponent in the end. Other programs are used to “crunch” player openings, which are essential for tournament players to know, very similar to chess .

Search techniques for recognizing possible moves

Othello programs look for possible permitted moves i. d. Usually by means of a search tree . They examine all positions (nodes of the tree), i.e. every half move (English: ply ), until the tree has been traversed completely, a certain search depth has been reached or a certain time has elapsed. Trivial algorithms like Minimax or Negamax can only search the tree to a shallow depth within an acceptable time. Therefore, over time, more efficient algorithms were sought and formulated. These are mostly based on alpha-beta search , Negascout , MTD-f , NegaC *. Newer hardware allows the use of multiple processor cores . ABDADA and APHID are better known examples of this. Various approaches based on pseudo-random numbers with successful algorithms such as Monte-Carlo Tree Search (MCTS), Upper Confidence Bounds (UCB) or UCB applied to Tree Search ( UCT ) are also used alternatively.

Strategies for evaluating possible moves

Just like the popular school break game Tic-Tac-Toe , Othello is a finite game. Thus there is a finite number of possible game courses. The number of nodes and leaves in a complete game tree is about 10 54 , and the number of possible, allowed moves is about 10 28 . However, this number is so challenging even for today's most powerful computers that it is impossible, especially on personal computers, to calculate the entire game and choose a move based on the result. Therefore, different approaches have been developed to evaluate trains. The three most important are:

Disk Square

Compared to the success of the other two strategies, the Disk Square approach is rather naive and is only played by human players as an exclusive strategy for beginners. Each field on the game board is assigned a certain value. There are a total of ten different field types on the board, which can be mapped onto the whole board by mirror symmetry.

  • DefaultDiskSquare

The figure above shows such a disk square approach, with the smallest possible factors. The algorithm works trivially: Add the values ​​of all opposing stones that the train turns over and the value of the stone that you place. Assuming the following game situation with White to move

  • SampleSetting

and the approach shown above would result in move A to 1 + 3 + 5 = 9 and move B to 2 + 8 = 10. So move B would be better. Now the fields that are marked with 7 and especially with 8 in the first diagram are considered to be particularly “bad” for your own move. Therefore, disk square approaches usually weight such fields differently, so that the corner fields in particular are considered to be particularly valuable, and those directly adjacent to them are particularly avoidable, for example:

  • OtherAdjustment

Then move A would be: 1 + 1 + 5 = 7, and move B would be: 1 + (−30) = −29. And now move A would be better. It is a particular challenge for developers of Othello programs to adjust these weightings. One approach is to recalculate the weight as the game progresses. Here one does not leave a fixed value, i.e. a constant function, for each field, but recalculates the value along a parameter or even several parameters with every half move. In the simple version, the only parameter is the half-move counter. For example, you can stipulate that in the opening phase the edge fields should be avoided as much as possible, but should be aimed for in the later course of the game.

If you imagine the Othello board as a matrix and take into account all symmetries, the corresponding algorithm can be illustrated clearly:

(The components of the matrix with zeros are either covered by symmetries or (as ) already shown by the basic position at the start of the game.)

For now, appropriate functions can be set. Since the corner fields are particularly desirable, a constant function is sufficient in a first draft, for example . However, a fringe field as said above at the beginning of the game to avoid to pursue the course, a matching function could be: .

More complex variants pass further parameters, such as the occupation of the surrounding fields with own and opposing stones. Very sophisticated algorithms of this type are almost equivalent to those using other strategies, but they require significantly more computational effort.

The fact that online implementations of Othello in particular are often based on the Disk Square algorithm is due to the fact that, as shown, it can be programmed with very little effort.

mobility

Most human players strive to maximize their own mobility (number of possible, allowed moves) and at the same time to minimize that of the opponent. In addition, be careful to avoid boundary stones (stones that border on empty fields). Good human players, depending on their ability, gain an advantage very quickly in this way. Mobility algorithms follow the same strategy and are much faster compared to the disk square approach. Many Othello programs have knowledge of edge and corner game positions, on the basis of which they try to keep their own number of pieces as small as possible during the opening and early middlegame. Some programs such as NTest or WZebra have such a strong mobility rating that even if they determine their next half-move solely on this basis and completely ignore the game tree , they are difficult to beat even for experienced players.

Pattern recognition

Some programs contain algorithms that recognize typical game situations. Othello is a game that has far more symmetries than chess, for example, so that it is sufficient to analyze small areas of the board. For example, there are typical "traps" at the edges of the playing fields that can appear eight times (rotated, mirrored) and which inevitably lead to the occupation of a corner field after five half-moves, so that the game tree does not have to be searched any further. At least a certain value can be assigned to such a constellation, which can be compared with the further evaluations. With the advent of multi-core processors and the steadily increasing availability of aids within software development tools that support these capabilities, this aspect is becoming increasingly important. Typically, successful Othello programs combine all of these three methods, with "Disk Square" and "Pattern Recognition" mostly used to exclude certain branches in the game tree, and "Mobility" evaluates the remaining branches.

Opening and Endgame Libraries

Although Othello is a finite game, today's computing power is not sufficient to completely calculate a game within a period of time that is appropriate for a tournament. In order to give programs in the opening and endgame an advantage, they therefore have an opening and partly also an endgame library. These generally do not have a fixed draw depth, but are designed in such a way that game constellations that allow a quick and unambiguous assessment are only contained with a shallow depth, and those that are scarce are available stored with a much greater depth. Most of the strongest Othello programs have an opening library, such as the Thor database , which is based on numerous games by particularly strong players, in particular all games from the World Cup. Some programs also contain endgame libraries that work in a similar way to the above. Happy ending training program . To minimize the data stock, the numerous symmetries of Othello are also used here.

Milestones in Computer Othello

1978 : Nintendo published the arcade game Computer Othello .

1980 : The Moor program (by Mike Reeve and David Levy) won one of six games against world champion Hiroshi Inoue.

Early 1980s : Paul Rosenbloom developed the IAGO Othello program . In games against Moor, IAGO was superior in minimizing the opposing mobility.

Late 1980s : Kai-Fu Lee and Sanjoy Mahajan wrote BILL , a program similar to IAGO but implementing Bayesian learning. BILL was able to beat IAGO regularly.

1992 : Michael Buro started working on the Logistello program . Logistello's algorithms for calculating trains and implementing pattern recognition made the program superior to older programs. What was extraordinary was that Logistello played over 100,000 games against himself to improve his skills.

1997 : Logistello won all of six games against world champion Takeshi Murakami. Even if the professional world was certain that sooner or later Othello programs would play stronger than human players, it was 17 years since a program had played against a reigning world champion. After this tournament, however, there was no longer any doubt: Logistello was far superior to any human player.

2004 : Ntest won the title of Logistello's strongest Othello program.

2005 : Ntest, Saio, Edax, Cyrano and WZebra became much stronger in their current versions than Logistello. Ntest ​​and WZebra have not been further developed since then, but are still popular challenges for ambitious players, precisely because of their historical significance.

2011 : Saio , Edax and Cyrano showed, for example in comparison to the reference Logistello, how much Othello programs can be optimized.

Well-known Othello programs

See also

Individual evidence

  1. ^ Jean-Christophe Weill (1992). The NegaC * Search. ICCA Journal, Vol. 15, No. 1, pp. 3-7
  2. ^ Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Algorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, NY, reprinted ICCA Journal Vol. 19, No. 1
  3. ^ Mark Brockington (1997). KEYANO Unplugged - The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta.
  4. ↑ C # Othello, at Sourceforge .
  5. ↑ How Ntest ​​Works ( Memento of the original from November 9, 2011 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. March 02, 2005 @1@ 2Template: Webachiv / IABot / othellogateway.com
  6. ↑ The History of Computer Games ( Memento of the original from January 24, 2011 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 216 kB)  @1@ 2Template: Webachiv / IABot / userhome.brooklyn.cuny.edu
  7. ↑ Othello Indonesia

Web links