 |
| Home | Articles | Reviews | Interviews | JDK | Glossary | Features | Discussion | Search |
Contribute
- What's New
- Submit News
Basic Othello Strategy
The goal of the game is to own the most board locations at the end of the game. One way to approach reaching this goal is to try and secure board locations that can't be recaptured by your opponent. Through analysis of the game and this approach in mind, one can verify that the idea of capturing key board locations is fundamental to winning. Below, I will demonstrate these locations and how they become a key factor in the winning of the game:- Ownership of a corner is irreversible: meaning that an oppenent can't retake it once you own it and vice versa.
- Owning two adjacent corners means that it will be very likely that you will also own the connecting side. Squares under the influence of the corners are marked by the red X's in the following image:
- Furthermore, owning any 3 corners creates the strong likelihood of owning 2 adjacent sides. As demonstrated below:
- Those sides, once owned, can't be recaptured by an opponent. Yet most importantly, owning 2 adjacent sides yields the possibility to create many more irreversible pieces. This is done by repeating the same pattern described above:
Of course, this is only really effective if all the pieces on those two sides are owned by you. Regardless, the principle game strategy has now been introduced.
Initial Board Location Values
In order to translate the importance of board locations to a computer algorithm, an 8X8 matrix of integer values could be used. This gives us 64 board locations with each of them needing a value. If we allow each board location to have a possible value range of -20 to 20, this gives us approximately 3.4 E102 potential board configurations. That is a few too many board configurations to investigate. However, careful inspection of the symmetry of an 8X8 othello board gives 10 unique board location values:
This reduces the solution set to 1.0 E16 possible board configurations. This is still quite a large number but, believe it or not, the size of the solution set has been reduced by more than 99.9%. A genetic approach to finding the best 10 values for the board is probably the best. However, without taking an organized approach, but more hit and miss trials, I believe the best initial board values to be very close to
Looking at these board values, you can see that, as you probably expected, the corners are given a very high value. Yet the locations immediately surrounding the corners are given a negative value. This is because these surrounding locations, if occupied before the corner is taken, typically create an opportunity for the opponent to take that corner.
[7] The location on the diagonal and next to the corner is the most dangerous place on the board. If your piece occupies this location, then your opponent has the ability take that corner within 2 moves over 90% of the time. Hence, I have given that location the nickname of "corner give" and a value of -10.
[3] The locations next to the corner but not on the diagonal are dangerous as well. However, there are several occasions when it is a smart move to occupy those locations. So it earns a negative value but not nearly as extreme.
[10] The locations at the center of the board earns a value of 0 because it is anticipated that it will change hands so often that there is no inherent value in owning it.
[2] There is yet another, not so obvious, set of key locations about a quarter way down each side of the board. These locations have a high value of 5 because they are meant to create a bias for gaining control of a side. Consider that on a given side, both of these key locations are owned by a given player.
One can now see that if the opponent was to place a piece in any of the locations marked by the X's, then it could be immediately regained by black. Furthermore, in all 4 possible cases, black would retain a position of undiminished strength along the side. However, it is worth noting that this is only really an effective strategy if no other board locations on that side are previously owned by either player.
In fact, most of these board values discussed above would change depending on the state of the game. For example, the "corner give" [7] would no longer be a "corner give" if the corner was already owned. Thus if the corner is already owned, the value of the "corner give" should change accordingly.
Note: In order to properly calculate the value of a move, you must not only consider the value of the location you moved to, but all locations gained as a result of that move [a.k.a. impact flips].
Mobility Based Evaluation
So far we have introduced the principles of board location evaluation and, along the way, we touched on some aspects of pattern evaluation. Mobility based evaluation considers the number of potential moves as a means for determining move strength. Consider this example:
As you can see, black has 2 possible moves [A,B]. The most important issue in choosing between these two moves turns out to be a mobility issue rather than board location values. Recalling from the previous section on board value locations, owning board position A has a value of 50 while board position B has a value of -1. So it would seem that a move to position A would clearly be the best. However, it can be shown that a move to location A is not the best option.
A: 
White now has two possible moves available to him which are denoted as the red X's. In fact, one of the moves allows white to gain a corner along with 5 irrecoverable pieces along the top side, making white the clear winner of this exchange. Now, lets consider the alternate move to location B :
Somewhere in the decision tree's branches, there exists the best possible outcome as well as the worse outcome and everything in between given any particular move. Since we are interested in gaining positions that we can't lose, it's the worse possible outcome as the result of each of immediately possible moves that will receive our attention. More to the point, if we choose the move that has the best worse possible outcome each time, i.e. creating irreversible pieces, then we are constantly making moves that improve our strategic strength.
In order to evaluate the value of each possible outcome [node] in the tree, one should use a board location value matrix. The behavior of the decision tree is further increased if a relative strength (player 1 vs. player 2) is used as an indicator instead of the board value for the active player alone. Hence, a location value ratio is a great way to evaluate a tree node's weight:
Location Value Ratio: The sum of the active player's board values divided by the sum of the opponent's board values, where the each players values are established using their relative board location value matrix.
White now has two possible moves available to him which are denoted as the red X's. In fact, one of the moves allows white to gain a corner along with 5 irrecoverable pieces along the top side, making white the clear winner of this exchange. Now, lets consider the alternate move to location B :
B: 
Notice that this move leaves white absolutely no counter moves. In this example, making the move decision based on minimizing how many moves the opponent is left with is clearly the way to go. This example translates into an important rule: Force your opponent to forfeit their next turn whenever possible. This idea can also be generalized into a set of central mobility goals:
Notice that this move leaves white absolutely no counter moves. In this example, making the move decision based on minimizing how many moves the opponent is left with is clearly the way to go. This example translates into an important rule: Force your opponent to forfeit their next turn whenever possible. This idea can also be generalized into a set of central mobility goals:
- Minimize your opponents move options.
- Less importantly, maximize your own move options.
Decision Trees
The goal of a decision tree is to investigate the possible game outcomes given the current state of the game. In order to do this, a tree of game states is built where the depth of the tree represents how many moves into the future is currently being investigated. In order to evaluate the strength of one move branch over another, we return to the general strategy of gaining irreversible board locations.Somewhere in the decision tree's branches, there exists the best possible outcome as well as the worse outcome and everything in between given any particular move. Since we are interested in gaining positions that we can't lose, it's the worse possible outcome as the result of each of immediately possible moves that will receive our attention. More to the point, if we choose the move that has the best worse possible outcome each time, i.e. creating irreversible pieces, then we are constantly making moves that improve our strategic strength.
In order to evaluate the value of each possible outcome [node] in the tree, one should use a board location value matrix. The behavior of the decision tree is further increased if a relative strength (player 1 vs. player 2) is used as an indicator instead of the board value for the active player alone. Hence, a location value ratio is a great way to evaluate a tree node's weight:
Location Value Ratio: The sum of the active player's board values divided by the sum of the opponent's board values, where the each players values are established using their relative board location value matrix.
Parsing
It is necessary to parse these decision trees using some heuristic(s) so that they can be used real time.
Submitted: 11/04/2002
Article content copyright © Marc Mandt, 2002.
| Article Toolbar |
 Print BibTeX entry
|
| Search |
| Latest News |
|
- Generation5 10-year Anniversary (03/09/2008) - New Generation5 Design! (09/04/2007) - Happy New Year 2007 (02/01/2007) - Where has Generation5 Gone?! (04/11/2005) - NeuroEvolving Robotic Operatives (NERO) (25/06/2005) |
| What's New? |
|
- Back-propagation using the Generation5 JDK (07/04/2008) - Hough Transforms (02/01/2008) - Kohonen-based Image Analysis using the Generation5 JDK (11/12/2007) - Modelling Bacterium using the JDK (19/03/2007) - Modelling Bacterium using the JDK (19/03/2007) |