Jump to content

Computer Othello

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Gulabatu (talk | contribs) at 11:33, 5 April 2010 (Solving Othello ( 4x4 , 6x6 , 8x8 )). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

For the arcade game, see Computer Othello (1978 arcade game).


Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing Othello perfectly.

Availability

Othello-playing computers are now accessible to the average consumer. There are many Othello engines such as Logistello, WZebra, and Edax that can be downloaded from the Internet for free, and play a game that when run on any up-to-date personal computer, can defeat easily the best human players. Nowdays, the best Othello programs have surpassed even world-champion caliber players, and it's clearly almost impossible for human defeat them. At tournament speed with both the computer and human having no specific knowledge of their opposition, there is only a wedge from about the twentieth to thirtieth of the sixty moves (in a full-board game) in which the human may produce researched (using a computer) or insightful moves to get any edge in compensation for the perfection of the programs at the end.

Search techniques

Computer Othello programs search for any possible legal moves as a game tree. In theory, they examine all positions / nodes, where each move by one player is called a "ply". This searching continues until a certain maximum search depth or the program determines that a final "leaf" position has been reached.

A naive implementation of this approach can only search to a small depth in a practical amount of time, so various methods have been devised to greatly speed the search for good moves.

For more information, see:

Evaluation Techniques

There are three different paradigms for creating evaluation functions.

Disk-square tables

Different squares have different values - corners are good and the squares next to corners are bad. Disregarding symmetries, there are 10 different positions on a board, and each of these is given a value for each of the three possibilities: black disk, white disk and empty. A more sophisticated approach is to have different values for each position during the different stages of the game; e.g. corners are more important in the opening and early midgame than in the endgame.[1]

Mobility-based

Most human players strive to maximize mobility (number of moves available) and minimize frontier disks (disks adjacent to empty squares). These measures can be found very quickly, and they increase playing strength a lot. Most programs have knowledge of edge and corner configurations and try to minimize the number of disks during the early midgame, another strategy used by human players.[1]

Pattern-based

Mobility maximization and frontier minimization can be broken down into local configurations which can be added together; the usual implementation is to evaluate each row, column, diagonal and corner configuration separately and add together the values, lots of different patterns have to be evaluated.[1] The process of determining values for all configurations done by taking a large database of games played between strong players and calculating statistics for each configuration in each game stage from all the games.[1]

The most common choice to predict the final disc difference, it used a weighted disk difference measure where the winning side gets a bonus corresponding to a number of disks.[1]

Opening Book

Opening books aid computer programs by giving common openings that are considered good ways to counter poor openings. All strong programs use opening books and update their books automatically after each game. It is to go through all positions from all games in the game database and determine the best move not played in any database game, transposition tables are used to record positions that have been previously searched, to save researching of them.[1] This is time-consuming as a deep search must be performed for each position, but once this is done, updating the book on the fly is easy - after each game played, all new positions are searched for the best deviation.

Endgame

Nowdays, best Othello programs that run on average personal computers can solve exactly the result of a game, within the last 30 - 31 ply given the practical match time (depend on the cpu speed), either win, draw or lose.

Other optimizations

Faster hardware and additional processors can improve Othello-playing program abilities, such as deeper ply searching that lead to be a stronger program.

Solving Othello

Solved on a 4×4 and 6×6 board as a second player force to win under perfect play.[2] [3] Far from solved on 8×8 board (the standard one), yet computer analysis shows a very likely draw: there are thousands of likely draw lines although not a single line has been fully proven[4]. No strongly supposed estimates other than increased chances for the starting player (black) on 10×10 and greater boards exist.

Othello 4 x 4

Othello 4x4 has considerably very small game tree and it has been solved in less than one second by many simple othello programs that use minimax method.[5] White Win +8 in a perfect play. All available perfect play solutions, included its symetricals: D3 C3 C4 C5 F6 E3 C6 F4 F3 F5

D3 C3 C4 E3 F6 C5 F3 D6 C6 E6

E6 F6 F5 F4 C3 D6 F3 C5 C6 C4

E6 F6 F5 D6 C3 F4 C6 E3 F3 D3

F5 F6 E6 D6 C3 F4 C6 E3 F3 D3

F5 F6 E6 F4 C3 D6 F3 C5 C6 C4

C4 C3 D3 E3 F6 C5 F3 D6 C6 E6

C4 C3 D3 C5 F6 E3 C6 F4 F3 F5

Othello 6 x 6

It always end with White Win +4 in a perfect play.[6] All available perfect play solutions, included its symetricals:

D3 C5 D6 E3 F5 F4 E2 D2 C2 E6 E7 G5 C4 C3 G4 G3 F3 C7 B5 D7 B7 B3 C6 B6 F7 F6 B4 B2 G6 G7 PA F2 G2

D3 C5 D6 E3 F5 F4 E2 D2 C2 E6 E7 G5 C4 C3 G4 G3 F3 C7 B5 B4 B6 B7 B2 C6 B3 D7 F6 F7 PA G2 F2 G6 G7

E6 F4 E3 D6 C4 C5 D7 E7 F7 D3 D2 B4 F5 F6 B5 B6 C6 F2 G4 E2 G2 G6 F3 G3 C2 C3 G5 G7 B3 B2 PA C7 B7

F5 D6 C5 F4 D3 E3 G4 G5 G6 C4 B4 D2 E6 F6 E2 F2 F3 B6 D7 B5 B7 F7 C6 C7 B3 C3 E7 G7 C2 B2 PA G3 G2

C4 E3 F4 C5 E6 D6 B5 B4 B3 F5 G5 E7 D3 C3 D7 C7 C6 G3 E2 G4 G2 C2 F3 F2 G6 F6 D2 B2 F7 G7 PA B6 B7

E6 F4 E3 D6 C4 C5 D7 E7 F7 D3 D2 B4 F5 F6 B5 B6 C6 F2 G4 G5 G3 G2 G7 F3 G6 E2 C3 C2 PA B7 C7 B3 B2

F5 D6 C5 F4 D3 E3 G4 G5 G6 C4 B4 D2 E6 F6 E2 F2 F3 B6 D7 E7 C7 B7 G7 C6 F7 B5 C3 B3 PA G2 G3 C2 B2

C4 E3 F4 C5 E6 D6 B5 B4 B3 F5 G5 E7 D3 C3 D7 C7 C6 G3 E2 D2 F2 G2 B2 F3 C2 G4 F6 G6 PA B7 B6 F7 G7

Othello 8 x 8

Top programs have expanded and explored all promising lines, and still expanding so many lines everywhere. They expand diagonal, perpendicular and parallel openings, seems perpendicular opening have really less good variants than diagonal, so seems that about all lines on perpendicular are yet calculated.[7] There are many more lines after the diagonal opening than after the perpendicular opening.[8] The parallel opening has strong advantages for the black player to always in a perfect play.[9] They expand their books for many years now on a couple of computers. As a result, many lines are in practice proven draws or wins for either side. The computations have progressed a lot in recent years, they are very close to solving the othello / reversi. It is highly likely to be a draw with the perfect play on both side.

There are thousands of perfect play solutions, below some of them which are solid:

F5 F6 E6 F4 G5 E7 E3 F3 C5 C4 G3 C6 D6 D7 E8 D8 G6 F8 G4 F7 D3 H6 C3 H5 B5 A5 C8 B8 H7 H8 G8 G7 A8 B3 H4 C7 B4 F2 F1 G2 B7 H3 B6 A4 H1 D2 H2 E2 C1 G1 C2 B2 A1 A6 A7 A2 A3 B1 D1 E1

F5 D6 C3 D3 C4 F4 F6 F3 E6 E7 D7 G6 F8 F7 G5 H6 H4 G4 H3 H5 H7 C5 B4 E8 D8 B5 E3 D2 C6 B6 A5 F2 C2 A4 A6 E2 G3 B1 A3 B3 C1 D1 A2 G2 E1 F1 H1 C8 B8 H2 C7 H8 G1 G7 G8 A8 A1 B2 PA B7 A7

F5 D6 C4 G5 F6 F4 F3 D3 C3 G6 E3 E6 H6 E2 F2 D2 D1 H4 C7 C6 C1 B5 H5 H7 C2 E1 E7 F8 C5 D7 F1 B3 A3 C8 F7 B4 A4 G4 A5 E8 B6 G3 H3 G7 H8 G8 D8 B2 B8 B1 A1 A6 B7 A8 A7 H2 G2 A2 H1 G1

F5 D6 C3 D3 C4 F4 F6 F3 E6 E7 D7 G6 F8 F7 G5 H6 H4 G4 H3 H5 H7 C5 B4 E8 D8 B5 E3 D2 C6 F2 C2 A5 B3 E2 A3 A4 A6 B6 C7 B1 C1 D1 F1 C8 B8 E1 A1 G3 H2 A2 B2 G7 H8 G8 PA A8 PA A7 B7 G1 G2 H1

F5 D6 C3 D3 C4 F4 F6 F3 E6 E7 D7 G6 F8 F7 G5 H6 H4 G4 H3 H5 H7 C5 B4 E8 D8 B5 E3 D2 C6 F2 C2 A5 B3 E2 C1 C8 B8 C7 F1 D1 G8 G2 G3 B1 H1 H2 G1 H8 E1 G7 A1 B2 A2 A8 A4 A3 A6 B6 B7 A7

F5 D6 C3 D3 C4 F4 F6 F3 E6 E7 D7 G6 F8 F7 G5 H6 H4 G4 H3 H5 H7 C5 B4 E8 D8 B5 E3 D2 C6 F2 C2 A5 B3 E2 C1 C8 B8 C7 G8 D1 F1 G2 G3 B1 H1 H2 G1 H8 E1 G7 A1 B2 A2 A8 A4 A3 A6 B6 B7 A7

F5 D6 C3 D3 C4 F4 C5 B3 C2 E3 D2 C6 B4 A3 G3 G4 F3 C1 B5 D1 E2 A4 A6 F2 G1 F6 E6 G6 F1 G5 H4 E1 B1 F7 H6 A5 A2 H5 F8 G7 H3 G8 H8 H7 G2 H1 H2 A1 B2 E7 E8 D8 C8 A7 B6 B7 C7 D7 B8 PA A8

F5 D6 C3 D3 C4 F4 C5 B3 C2 E3 D2 C6 B4 A3 G3 G4 F3 C1 B5 D1 E2 A4 A6 F2 G1 F6 E6 G6 F1 G5 H4 E1 B1 F7 H6 A5 A2 H5 F8 G7 H3 G8 H8 H7 G2 H1 H2 A1 B2 E7 E8 D8 C8 A7 B7 B6 D7 C7 B8 A8

F5 D6 C3 D3 C4 F4 C5 B3 C2 E3 D2 C6 B4 A3 G3 G4 F3 C1 B5 D1 E2 A4 A6 F2 G1 F6 E6 G6 F1 G5 H4 E1 B1 F7 H6 A5 A2 H5 F8 G7 H3 G8 H8 H7 G2 H1 H2 A1 B2 E7 E8 D8 C8 A7 B7 B6 C7 D7 B8 A8

See also

Notes

  1. ^ a b c d e f Writing an Othello program April 02, 2007
  2. ^ Solution of Othello 4 x 4 September 02, 2008
  3. ^ Perfect play in 6x6 Othello from two alternative starting positions November 17, 2004
  4. ^ Edax 4.0 Opening Book November 01, 2008
  5. ^ Solution of Othello 4 x 4 September 02, 2008
  6. ^ A free software for solving 4x4 and 6x6 othello
  7. ^ 8x8 othello discussion
  8. ^ Strongest othello program in term of artificial intelligent
  9. ^ Saio's book
Look up computer othello in Wiktionary, the free dictionary.
Wikimedia Commons has media related to Othello computers.
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Computer_Othello&oldid=354085566"