SUGISAKAMASANORI

Journal of Robotics, Networking and Artificial Life
Vol. 9(4); March (2023), pp. 331–336
ISSN (Online):2352-6386; ISSN (Print):2405-9021
https://alife-robotics.org/jrnal.html

Satoshi Ikeda1, Tomoyasu Toshimori2, Makoto Sakamoto1, Takao Ito3
1

Department of Computer Science and System Engineering, Miyazaki University, Japan
Graduate School of Engineering, Miyazaki University, Japan
3
Graduate School of Engineering, Hiroshima University, Japan
2

Received 25 November 2021
Accepted 12 December 2022

Combinatorial game theory
Perfect information
Perfect play.
Othello (Reversi)

In 1993, Joel Feinstein discovered one of perfect plays for Othello (Reversi) on a board with2n×2n (n = 2,3) , which showed that the second player(White) is the winner, respectively. Since
2015, we have been analyzing Othello on a board with 4×2n (n = 3,4,…) . As results, we found
one of perfect plays for each on the 4×2n (n = 3,4,5) boards, which showed that the first player(Black) is the winner respectively. Recently, we completed the analysis of the 4×12 board. In thispaper, we will introduce the analysis results of 4×12 board Othello and summarize the results thathave been found so far.
© 2022 The Author. Published by Sugisaka Masanori at ALife Robotics Corporation Ltd.
This is an open access article distributed under the CC BY-NC 4.0 license(http://creativecommons.org/licenses/by-nc/4.0/).

outcome for that player regardless of the response by theopponent.
We have been analyzing Othello with a board size of
4×2n (n = 3,4,…) since 2015. As results, we found oneof perfect plays for each on the 4×2n (n = 3,4,5) boards,
which showed that the first player (Black) is the winner[4], [5], [6], respectively.
Based on the results obtained from analyzing Othello
so far, it seems that the second player has the advantage
on a square board, while the first player has the advantage
on a rectangular board with differing lengths and widths.
However, this conclusion may be inaccurate. According
to computer-generated high-quality games analysis ofboard size of 2n×2n (n=2,3,4,…), the first player's
advantage increases as n increases. Therefore, it isbelieved that the first player always wins for any
sufficiently large n. The standard 8×8 board Othello isstill remains unsolved, but it is believed that it is likely toend in a draw. It may be that there are only two sizes of

1. Introduction
Othello [1] is a board game derived from Reversi by Goro
Hasegawa (JPN) in 1973. Its rules are completely unified ,whereas Reversi has many local rules. The rules ofOthello in this paper are the same as those of Hasegawa’s
Othello, except for the size of the board.
Othello (Reversi) is one of the games with perfect
information and no element of chance. In a two-player
game with perfect information like Othello, they arealways categorized as either a win, a loss, or a draw for
the first player [2].
In 1993, Joel Feinstein found one of perfect plays for
Othello with board size of 2n×2n (n = 2,3) in [3], whichshowed that the second move player (White) is thewinner, respectively. Here, "perfect play" is the behavior
or strategy of a player that leads to the best possible

Corresponding author’s E-mail: bisu@cs.miyazaki-u.ac, hm17033@student.miyazaki-u.ac.jp, saka2000@cc.miyazaki-u.ac.jp,itotakao@hiroshima-u.ac.jp331

Othello board on which the first player wins: the 4×4board and the 6×6 board.
After solving the 4×2n (n=3,4,5) board of Othello, we
challenged the 4×12 board problem by partitioning it into
several sub-problems. This is because its search space ofthe 4×12 board was too large (estimated to be more than
1000 times larger than the 4×10 boards). Recently, wesolved the 4×12 board problem by solving all its subproblems, which showed that the first player (Black) isthe winner. In this paper, we introduce the analysis
results of 4×12 board Othello and summarize the resultsthat have been found so far.

solve the game. i.e. find a sequence of moves that either
the first or second player can follow that will guarantee
the best possible outcome for that player. Depending onevaluation values used, we can find a perfect play.
Perfect analysis of Othello is useful to refer to thethinking routines of a game program. This is because
end-game routine of game program is the perfect analysis,and evaluation function in the middle-game routine isavailable for the ordering of the search in perfect analysis.
3.1. MiniMax with Alpha-Beta Pruning
As the method of analysis in this research, regardless ofthe middle or the end, MiniMax with Alpha-Beta pruning[4], [5], [6] is used. MiniMax algorithm achieves the best
moves for both players, Alpha-Beta method cuts
unnecessary search in MiniMax. These are commonlyused together since MiniMax with Alpha-Beta pruning
gives the same results as the simple MiniMax search.
Here, for the 4×2n (n = 2,3,4,5,6) board Othello, theevaluation value of the leaf vertex on the game tree, thefinal phase of game, is the stone difference between thefirst player and the second player. Additionally, only inthe case of 4×12 board Othello, if one of the players wins
completely without leaving any stones of the opponent,
the winner is considered to have filled all the squares withhis own stones.

2. Rules of Othello*
The rules of Othello [1] are as follows. Othello always
begins with the setup as shown in Fig. 1. One player uses
the black side of the pieces (circular chips), the other thewhite side. The player who chooses the black stone is thefirst to move.

Fig. 1. Starting position for the 4×12 board.

Each player puts a piece of own color to an empty squarein own turn. A player’s move consists of outflanking thepieces of his opponent, he flips outflanked pieces to theirown color. To outflank means to place the piece on theboard so that his opponent’s rows of the piece arebordered at each end by the piece of his color. If a player
cannot make any move, then he has to pass. If he is able
to make a valid move, then passing is not allowed. The
game ends when neither player can make any valid move.
The winner is the player who has more pieces than his
opponent.

3.2. Move Ordering

3. Techniques

4.

In the combinatorial game such as Chess, Go and Othello,game tree is a directed graph whose nodes are positions
in a game and whose edges are moves. The complete
game tree for a game is the game tree from starting
position and containing all possible moves from eachposition. Analyzing the complete game tree leads us toThis chapter introduces one of the perfect plays obtainedso far on both 4×2n (n = 2,3,4,5) and 6×6 boards.
However, a perfect play in 4×2n (n = 4,5) is used in thesense of the first player wins completely (the second
player has no stones). The result on the 4×12 board has
the same meaning.

The appropriate order in the search process facilitatespruning by Alpha-Beta method. In our program, we
extract all positions one step forward from the current
position and sort them. In order to realize efficient search
results, it is necessary to have a good evaluation value forthe position. This is because the higher the accuracy ofthe position evaluation value, the higher the search space
reduction effect. To determine the evaluation value of theposition, we utilize pre-calculated values obtained
through techniques such as machine learning [6].

332Preliminary results [4], [5], [6]4.1. 4×4 and 6×6 boards

4.2. 4×6, 4×8 and 4×10 boards

On 4×4 and 6×6 square boards, the second player wins,
respectively. For the 4×4 board, a perfect play is shownin Fig. 2 which means Black: 3, White: 11. There was nopass in this procedure.

On 4×6, 4×8, and 4×10 rectangular boards, the firstplayer wins, respectively. For the 4×6 board, a perfectplay is shown in Fig. 5 which means Black: 20, White: 4.
It was passed at move 18.

Fig. 2. A perfect play of 4×4 board Othello.

Fig. 5. A perfect play of 4×6 board Othello.

For the 6×6 board, a perfect play is shown in Fig. 3
which means Black: 16, White: 20. It was passed atmove 31.

For the 4×8 board, a perfect play is shown in Fig. 6 whichmeans the first player wins completely (the second player
has no stones remaining), with Black: 28, White: 0. It was
passed at move 12, 24 and 26, respectively.

Fig. 6. A perfect play of 4×8 board Othello.
Fig. 3. A perfect play of 6×6 board Othello.

For 4×10 board, a perfect play is shown in Fig.7 whichmeans the first player wins completely (the second player
has no stones remaining), with Black: 39, White: 0. It was
passed at move 19, 28, 34, 36, 38 and 40, respectively.

There are generally multiple perfect plays. Fig. 4
shows Feinstein's perfect play which has no pass.

Fig. 7. A perfect play of 4×10 board Othello.
Fig. 4. Feinstein’s perfect play.

The evaluation value in Othello on a 4×2n (n=4,5) board
is the stone difference between the first player and thesecond player. Perfect play in this paper means the bestplay in this sense. For this reason, for example, in Othello
on a 4×10 board, the first player may always win before
39 moves. However, at that time, the stone difference willbe less than 39 stones.

Feinstein's perfect play is different from that of Fig. 3,but the score is the same.

333

4.3. 4×12 board
The first 6 moves in each perfect play of 4×2n (n = 3,4,6)
boards introduced in the previous section are identical.
Therefore, we examined the perfect play of the 4×12
board with the initial position fixed up to the 6th move,using the same method as for the 4×2n (n = 3,4,5) board,
see Fig. 8. Our findings indicate that the first player
achieves a complete victory, leaving the second player
with no remaining stones [6].

Fig. 11. 2th move.

Under the fixed setting up to the 6th move andsearching from that position, it is necessary to solve 95
sub-problems in order to examine all the alternative
moves for White. However, under the assumption that
this problem is a complete win for Black, we only needto search for promising moves in Black's turn anddemonstrate that all result in a complete win for Black.
Also, as a result, we find a perfect play.
Table 1 shows all possible 14 sub-problems, whicharise from restricting the moves on Black's turn to onlythe promising ones after choosing alternate moves
indicated by Greek alphabet for each White's move (6thmove, 4th move, 2nd move). Here, the coordinates are asshown in Fig.12.

Fig. 8. A perfect play of 4×12 board Othellowith the initial position fixed up to the 6th move.

5.

Experiments

In order to find a perfect play on the 4×12 board, we
examine all possible moves for White (the second player)
up to the 6th move of white's turn in the procedure ofFig. 8.
Fig. 9, Fig. 10 and Fig. 11 represent the positions thatmust be examined in order to prove that gives win forBlack (the first player) on the 4×12 board. The 'F' in eachfigure represents the location where White (the secondplayer) placed their stone in the corresponding turn (6thmove, 4th move, 2nd move) as shown in Fig. 8. And theGreek alphabets in Fig. 9, Fig. 10 and Fig. 11 represent
all the possible positions where White can place his stone
instead of F in that White's turn.

Table 1. Sub-problems.
6th move(α)(β)

4th move(γ)f4g1(δ)e2g1(δ)e2h1(ε)h3f4(ε)h3h42th move(ζ)f4e1d1g1(ζ)f4e1d1h2(ζ)f4g1h1h2(η)h1e1d1e3(η)h1e1d1f4(η)h1e1d1h2(η)h1e3g4h3

We have confirmed that the 14 sub-problems listed inTable 1 lead to complete victories for Black (the firstplayer). In other words, 4×12 board Othello is a game thatthe first player wins if both players do their best.

Fig. 9. 6th move.

Fig. 12. Coordinates on 4×12 board.

Fig. 10. 4th move.

334

For Othello played on a 2n×2n (n = 2,3,4,…) squareboard, it has been established that White (the secondplayer) can only win when n=2,3. However, the outcome
remains unresolved for n greater than or equal to 4. As n
increases, Black generally holds an advantage, so it isuncertain whether White is guaranteed to win for n
greater than or equal to 4.
From the above, it appears that among the various sizesof Othello boards, the 4×4 and 6×6 boards are theexceptions where White can win.

For 4×12 board, a perfect play is shown in Fig. 13
indicating that the first player achieves a completevictory (the second player has no stones, that is, Black:42, White: 0). It was passed at move 28, 30 and 40,
respectively.

References
1. Japan Othello Association: Nihon osero renmei kyougi ru-ru,[online]www.othello.gr.jp/r_info/rule.html (Retrieved 24
November. 2021)
2. John von Neumann and Oskar Morgenstern, Theory ofGames and Economic Behavior, Princeton, 1944.
3. British Othello Federation: Forty Billion Nodes Under The
Tree - The Newsletter of the British Othello Federation, pp. 6–8 (1993).
4. Yuki Takeshita, Satoshi Ikeda, Makoto Sakamoto and Takao
Ito: “Perfect Analysis in miniature Othello,” Proceedings of the2015 International Conference on Artificial life and Robotics,
pp.39 (2015).
5. Yuki Takeshita, Makoto Sakamoto, Takao Ito and Satoshi
Ikeda: “Perfect Play in Miniature Othello,” Proceedings of theNinth International Conference on Genetic and EvolutionaryComputing, pp.281-290 (2015).
6. Yuki Takeshita, Makoto Sakamoto, Takao Ito, Tsutomu Itoand Satoshi Ikeda: “Reduction of the search space to findperfect play of 6×6 board Othello,” Proceedings of the 2017
International Conference on Artificial life and Robotics,
pp.675-678 (2017)

Fig. 13. A perfect play of 4×12 board Othello.

Our conclusion is that 4×12 board Othello, the firstplayer can achieve a complete victory regardless of thechoices made by the second player. A complete victory
for the first player in 4×12 board Othello means thatwinning without leaving any stones for the second player,
resulting in a score of 48 for Black and 0 for White. For
this reason, there is also another perfect play for 4×12board, as shown in Fig. 14, where the first player achieves
a complete victory (the second player has no stones, thatis, Black: 37, White: 0). It was passed at move 10, 18, 20,respectively. For this reason, for example, in Othello on
a 4×12 board, the first player can always achieve acomplete victory within 37 moves.

Authors Introduction
Prof. Satoshi Ikeda
He received PhD degree from Hiroshima
University. He is an associate professor in
the Faculty of Engineering, University ofMiyazaki. His research interest includes
graph theory, probabilistic algorithm,fractal geometry and measure theory.

Fig. 14. Another perfect play of 4×12 board Othello.

6. Conclusions
The Game of Othello on a 4×2n (n = 3,4,5,6) board resultin a victory for Black (the first player). Especially for n =4,5,6, it is a complete victory for Black. It is highly
probable that for any Othello game played on a 4×2n(where n ≧ 7) board, it always results in a complete
victory for Black.
It is important to note that the strategy for achieving acomplete victory with the minimum number of moves
remains unresolved, as the focus has primarily been on
determining the outcome of the game rather than
optimizing the number of moves required for victory.

Mr. Tomoyasu Toshimori
He is a student of the Department ofComputer Science and Systems
Engineering, Faculty of Engineering,
University of Miyazaki.

335

Prof. Makoto Sakamoto
He received the Ph.D. degree incomputerscienceandsystems
engineering from Yamaguchi University.
He is presently an associate professor in
the Faculty of Engineering, University ofMiyazaki. He is a theoretical computerscientist, and his current main researchinterests are automata theory, languages
and computation. He is also interested in digital geometry,
digital image processing, computer vision, computer
graphics, virtual reality, augmented reality, entertainment
computing, complex systems and so on.
Prof. Takao ItoHe is Professor of Management ofTechnology (MOT) in Graduate Schoolof Engineering at Hiroshima University.
He is serving concurrently as Professorof Harbin Institute of Technology(Weihai) China. He has publishednumerous papers in refereed journals
and proceedings, particularly in the area of management
science, and computer science. He has published more thaneight academic books including a book on Network
Organizations and Information (Japanese Edition). His
current research interests include automata theory, artificial
intelligence, systems control, quantitative analysis of interfirm relationships using graph theory, and engineering
approach of organizational structures using complex
systems theory.

336