Computer Othello: Difference between revisions
m Added {{uncategorized}} and {{unreferenced}} tags to article. using Friendly |
Reference & Evaluation Techniques added |
||
| Line 1: | Line 1: | ||
{{unreferenced|date=October 2009}} |
{{unreferenced|date=October 2009}} |
||
{{For|the arcade game|Computer Othello (1978 arcade game)}} |
{{For|the arcade game|Computer Othello (1978 arcade game)}} |
||
[[Image:Wzebra_othello.jpg|thumb|250px|right|WZebra - a strong Othello engine]] |
|||
'''Computer Othello''' refers to computer architecture encompassing computer hardware and computer software capable of playing [[Othello (game)|Othello]] perfectly. |
'''Computer Othello''' refers to computer architecture encompassing computer hardware and computer software capable of playing [[Othello (game)|Othello]] perfectly. |
||
== Availability == |
== Availability == |
||
'''Othello-playing computers''' are now accessible to the average consumer. There are many [[Othello engine]]s 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 impossible for human defeat it. |
'''Othello-playing computers''' are now accessible to the average consumer. There are many [[Othello engine]]s 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 it. |
||
== 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 (game theory)|"ply"]]. This searching continues until a certain maximum search depth or the program determines that a final "leaf" position has been reached. |
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 (game theory)|"ply"]]. This searching continues until a certain maximum search depth or the program determines that a final "leaf" position has been reached. |
||
| Line 16: | Line 18: | ||
* [[Alpha-beta pruning]] |
* [[Alpha-beta pruning]] |
||
== 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.<ref>[http://radagast.se/othello/howto.html Writing an Othello program] April 02, 2007</ref> |
|||
Many other optimizations can be used to make Othello-playing programs stronger. For example, [[transposition table]]s are used to record positions that have been previously searched, to save researching of them. Opening books aid computer programs by giving common openings that are considered good play (and good ways to counter poor openings). |
|||
=== 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.<ref>[http://radagast.se/othello/howto.html Writing an Othello program] April 02, 2007</ref> |
|||
=== 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.<ref>[http://radagast.se/othello/howto.html Writing an Othello program] April 02, 2007</ref> 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.<ref>[http://radagast.se/othello/howto.html Writing an Othello program] April 02, 2007</ref> |
|||
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.<ref>[http://radagast.se/othello/howto.html Writing an Othello program] April 02, 2007</ref> |
|||
== 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 table]]s are used to record positions that have been previously searched, to save researching of them.<ref>[http://radagast.se/othello/howto.html Writing an Othello program] April 02, 2007</ref> 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 == |
|||
| ⚫ | |||
== Other optimizations == |
|||
| ⚫ | |||
== Solving Othello == |
== Solving Othello == |
||
Solved on a 4×4 and 6×6 board as a second player force to win under perfect play. 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. No strongly supposed estimates other than increased chances for the starting player (black) on 10×10 and greater boards exist. |
Solved on a 4×4 and 6×6 board as a second player force to win under perfect play.<ref>[http://ailab.awardspace.com/othello4x4.html Solution of Othello 4 x 4] September 02, 2008</ref> <ref>[http://www.feinst.demon.co.uk/Othello/6x6sol.html Perfect play in 6x6 Othello from two alternative starting positions] November 17, 2004</ref> 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, there are still possibilities that one of the players can force to win under perfect play.<ref>[http://abulmo.perso.neuf.fr/resources/book-2008.htm Edax 4.0 Opening Book] November 01, 2008</ref> No strongly supposed estimates other than increased chances for the starting player (black) on 10×10 and greater boards exist. |
||
== See also == |
== See also == |
||
| Line 34: | Line 51: | ||
* [[Computer Olympiad]] |
* [[Computer Olympiad]] |
||
{{div col end}} |
{{div col end}} |
||
==Notes== |
|||
{{Reflist|2}} |
|||
== External links == |
== External links == |
||
Revision as of 13:22, 24 October 2009
 |
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 it.
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:
- Minimax algorithm
- Alpha-beta pruning
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.[2]
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.[3] 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.[4]
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.[5]
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.[6] 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.[7] [8] 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, there are still possibilities that one of the players can force to win under perfect play.[9] No strongly supposed estimates other than increased chances for the starting player (black) on 10×10 and greater boards exist.
See also
Notes
- ^ Writing an Othello program April 02, 2007
- ^ Writing an Othello program April 02, 2007
- ^ Writing an Othello program April 02, 2007
- ^ Writing an Othello program April 02, 2007
- ^ Writing an Othello program April 02, 2007
- ^ Writing an Othello program April 02, 2007
- ^ Solution of Othello 4 x 4 September 02, 2008
- ^ Perfect play in 6x6 Othello from two alternative starting positions November 17, 2004
- ^ Edax 4.0 Opening Book November 01, 2008
External links
 | This article has not been added to any content categories. Please help out by adding categories to it so that it can be listed with similar articles. (October 2009) |