Computer-Othello

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

Availability

There are numerous Othello programs, such as NTEST, Saio, Edax, Caissio, Heracles, and WZebra Logistello. These can be downloaded for free from the Internet. The above programs are able to beat the best human players when they are executed on current hardware. In addition, there are numerous implementations that about via Java applet that can be played directly online. However, these are far less strong than the above game usually Programs. Furthermore, there are programs that appeal to serious gamers and to help train certain game situations. A well-known representative is happy end, which helps to identify in a non-unique end-game situation, the right moves to end to have more pieces than your opponent. Other programs serve the 'surprise ' of game openings, knowledge of which is essential for tournament players, much like in chess.

Search techniques to detect possible moves

Othello programs look possible allowed trains usually means of a search tree. Examine all positions ( nodes of the tree ), so each half move (English: ply ) as long as the tree was to completely go through a certain search depth has been reached or expired some time. Trivial algorithms such as Minimax or Negamax can browse the tree within an acceptable time only to a small depth. Therefore, with time efficient algorithms have been 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.

Strategies for the evaluation of possible moves

Othello is, just like the well-known school breaks game Tic -Tac- Toe, a finite game. Thus there is a finite number of possible game histories. The number of nodes and leaves of a complete game tree is about 1054 and the number of the possible legal moves, is about 1028. This number represents but also for today's most powerful computers such a big challenge that, particularly on personal computers, is impossible to calculate the entire game and select on the basis of the result of a train. Therefore, various approaches have been developed to evaluate features. The three most important are:

Disk Square

The Disk -square approach is compared with the success of the other two strategies, rather naive, and is played by human players as the exclusive strategy only in beginners' area. Here, each field is assigned a specific value on the board. In total there are 10 different field types on the board, as manifested by mirror symmetry to the whole board.

The figure above represents such a disk -square approach, with the smallest possible factors. The algorithm works trivial: Add up the values ​​of all the opponent's pieces, which turns the train, and the value of the stone that you set. Starting point is the following game situation with the white train

And the approach shown above, ie A train would result to 1 3 5 = 9 and train B to 2 8 = 10. Thus B would train the better. The fields that have been referred to in the first diagram with 7 and especially 8, as particularly " bad" for their own train apply. Therefore, weight disk Square approaches such fields usually different, so in particular apply the corner fields as particularly valuable, directly adjacent thereto as particularly vermeidenswert, like so:

Then train would be A: 1 1 5 = 7, and train B would be: 1 ( -30 ) = -29. And now would train A better. For developers of Othello programs, it is a special challenge to adjust these weights. One approach is to calculate the weight again with the progress of the game. Here one does not leave it per field at a fixed value, ie a constant function, but calculated along a parameter or even more to the new value with each half move. In the simple version is the only parameter of the half-move counter. So one can specify that in the opening phase of the fringe fields should be avoided, but to strive for in the later stages of the game.

If the Othello board one imagines as a matrix and all symmetries taken into account, the corresponding algorithm can be represented graphically:

( The occupied with zeros components of the matrix are either covered by symmetries or (as ) already occupied by the basic position when the game starts. )

For suitable functions can now be defined. Since the corner squares are particularly desirable in a first draft reaches a constant function, for example. For an edge field, which as I said above to avoid at the beginning of the game, in the course but seek, a matching function could be:.

More complex variants to pass additional parameters, such as the occupation of the surrounding fields with their own and enemy stones. Very sophisticated algorithms of this type are almost equivalent to those that apply different strategies, but they require significantly more computational effort.

That especially online implementations of Othello often based on the disk - square algorithm, is that it can be shown how to program, with very little effort.

Mobility

Most human players strive to maximize their own mobility (number of possible, legal moves ) while minimizing the opponents. In addition, they take care to avoid boundary stones (stones that border on blank fields ). Achieve good human players, depending on ability, this way very quickly an advantage. Mobility algorithms follow the same strategy and are compared to the disk -squares approach much faster. Many Othello programs have knowledge of edge - and corner - game positions, based on which they strive to keep their own number of pieces during the opening and early middlegame as small as possible. Some programs such as NTEST or WZebra have such a strong mobility assessment, that, even if they determine their next half train only on this basis and let the game tree, completely disregarding are difficult even for experienced players to beat.

Pattern Recognition

Some programs contain algorithms that can recognize typical game situations. Othello is a match, which contains much more than about chess symmetries so that it is sufficient to analyze small areas of the board. There are for example typical "Fallen " at the edges of the playing fields ( rotated, mirrored) eight times can appear and inevitably lead after five half moves to fill a Eckfeldes, so the game tree does not have to be searched here. At the least, such a situation can be assigned a certain value, which can be compared with the other evaluations. Especially with the advent of multi-core processors and the ever-growing availability of tools within the software development tools that support these capabilities, this aspect more and more importance. Typically combine successful Othello programs all three of these methods, where " disk Square" and " pattern recognition " often to the exclusion of certain branches in the game tree serve, and " mobility " rated the remaining branches.

Opening and endgame libraries

Although Othello is a finite game, but today's computing power is not sufficient to completely figure out a game within a period which is reasonable for such a tournament. To provide programs in the opening and in the final one advantage they have is why a opening and some have a final library. These generally have no set draw depth, but are designed so that game situations that allow fast a clear evaluation are included only with low depth, and those which are scarce, are stored with far greater depth available. Most gambling strong Othello programs have an opening book, about the Thor database, which is based on numerous games particularly strong player, especially all games in the world championships. Some programs also include playoff libraries that work similar to the above-mentioned training program happy ending. To minimize the data volume also here the numerous symmetries of Othello be exploited.

Milestones in Computer Othello

1978: Nintendo released the arcade game "Computer Othello ".

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

Early 1980s: Paul Rosenbloom developed the Othello program IAGO. IAGO showed in games against superior Moor is to minimize the opponent's mobility.

Late 1980s: Kai- Fu Lee and Sanjoy Mahajan wrote BILL, a program that IAGO similar, but implemented Bayesian learning. BILL could IAGO beating regularly.

1992: Michael Buro began with his work on Logistello program. Logistellos algorithms for the computation of trains and the implementation of pattern recognition made ​​the program superior to older programs. Was Exceptionally that Logistello played more than 100,000 games against themselves to improve its capabilities.

1997: Logistello won all six games against the World Champion Takeshi Murakami. Even if the experts was sure that Othello programs would play sooner or later stronger than human players, it was 17 years ago, had been playing for a program against a reigning world champion. After this tournament, but there was no longer any doubt: Logistello was superior to any human player far.

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

2005: Ntest ​​, Saio, Edax, Cyrano and WZebra were significantly stronger than Logistello play in their current versions. Ntest ​​and WZebra have since no longer being developed, but are still for ambitious players, precisely because of its historical significance, popular challenges.

2011: Saio, Edax and Cyrano showed as compared to the reference Logistello how much can be Othello programs optimize.

Known Othello programs

199435
de