15
$\begingroup$

Based on Clear board in Othello

If we have an $2m\times 2n$ Othello board ($m\geq n\geq 2$), and the centre $4$ squares have the usual starting position, then for what all values of $m$ and $n$ can we clear the board (make the board entirely covered with one colour, either black or white) by controlling both players?

I am not interested in trial-and-error or a computer algorithm. Since this still remains unsolved, I guess any approach will be of help. I'm only asking if there is a logical/mathematical way to solve the Q for large $m$ and $n$?

Bonus sub-case: $m=n$

$\endgroup$
  • $\begingroup$ Just to clarify, are you asking for the solution to the problem? (aka a proof by induction). Or are you asking, how would the solution be given? (aka an explanation of proof by induction) I am preparing a proof by induction on this but wanted to make sure I was answering the right question before I go and post my mile-long proof. $\endgroup$ – Tim Nov 18 '16 at 5:37
  • $\begingroup$ @Tim A solution would definitely be most welcome...if not, even an approach would be fine. $\endgroup$ – ghosts_in_the_code Nov 18 '16 at 13:14
  • $\begingroup$ Othello is largely unsolved mathematically. $\endgroup$ – ULTIMATEGAMER07 Mar 10 '17 at 5:14
14
$\begingroup$

Here is one way you could begin to prove that the board can be cleared for all values of $m$ and $n$.

Proof by induction. [incomplete]

Case 1: $k = 1$

Here we take k = 1 to mean the smallest possible board with the given conditions $(m \ge n \ge 2)$ which would be a $m = n = 2$ or $2m \times 2n$ = $4\times4$ board.

Theorem: For an Othello board of size $4\times4$, there exists a sequence of valid moves $F$ which terminates in a board state of one side winning 16-0. Each item in $F$ is a single move. $F$ is always a subset of the set of all moves $G$ which contains all unoccupied coordinates on the board, along with the pass move $p$. We will note these moves as B1,2 meaning player B (black) played a piece in row 1, column 2. Player W is white who always moves second.

$F_1$ for example is the first move. Moves are thus ordered within this set the same as in the game, and can in fact be compared in sequence. To say that some move $F_b$ > $F_a$ means that the move $F_a$ occurs before $F_b$ in the game. Since $b > a$ numerically, this tells us move $a$ must occur before move $b$, otherwise order is not preserved in $F$ as we have defined it.

Proof. We first define a requirement called middle-board completeness that no moves occur on the side or in the corners until the entire middle of the board is filled in. The middle of the board is any space which is not a corner or side - any space with four spaces orthogonally adjacent to it. In this first case, that requirement is already met before the game even begins. The middle board is completely filled by the initial 4 pieces, and they are arranged in a checkerboard pattern. This requirement will become much more important later. Solutions may or may not exist which do not require middle-board completeness, but we will ignore any such solutions here.

We also define a stagnant piece to be one that can no longer be flipped directly because it sits between pieces of the opponent, or is on the sides or in a corner and is therefore difficult or impossible to flip. Again, in this first case, we will see that there can be no stagnant pieces in the middle board. A corner piece is always stagnant and can never be flipped, so the corner pieces must necessarily be played all by the winning player.

Now, we prove that a board clear is possible. We intend to clear the board with player B (black) winning 16-0.

When the game begins, there are eight moves currently available to player B (black which moves first in Othello): B1,2, B1,3, B2,1, B2,4, B3,1, B3,4, B4,2 and B4,3. All of these moves will flip exactly one of white's two pieces, and leave us in the same board state with rotational, vertical, or horizontal symmetry to each of the other possible board states after this first move. The first move is therefore irrelevant, so we will just play B1,2.

The board at this state in time is shown below:

| |B| | |  
| |B|B| |  
| |B|W| |  
| | | | |

Player W now has only two possible moves. There are three moves in $G$, but one is in the corner and if black is to win, we must eliminate all possibilities of white taking a corner. The two valid moves are therefore W1,3 and W3,1. Each of these moves flips exactly one black piece, but the board state is different depending on which one we pick. We therefore need some kind of move strategy for W to give us the best chance of a board clear.

Our only rule for choosing moves for W is to avoid any situation in which the only valid move for W is to take a corner, because in that case we have eliminated the potential outcome of a clear board. In order to achieve this, it therefore also makes sense for B to take every available corner as soon as possible, to prevent W being forced to take it later.

Our strategy dictates that we should play W1,3 to give B a corner. However, that results in a board with empty spaces at the end (unplayable by either B or W), though B could certainly eliminate all white pieces. If neither player can move, the game ends, blanks or not. So instead we play W3,1 and now the board looks like this:

| |B| | |  
| |B|B| |  
|W|W|W| |  
| | | | |

Due to the oscillatory nature of the game (pieces being flipped back and forth), it will be advantageous to have white play W1,3 next, so that B can take two corners by first playing B4,1.

| |B| | |  
| |B|B| |  
|W|B|W| |  
|B| | | |

White plays W1,3 as planned:

| |B|W| |  
| |W|W| |  
|W|B|W| |  
|B| | | |

Black can now take the opposite corner with B1,4:

| |B|B|B|  
| |W|B| |  
|W|B|W| |  
|B| | | |

Next white only has two moves, W4,2 and W2,4. We play the latter.

| |B|B|B|  
| |W|W|W|  
|W|B|W| |  
|B| | | |

B is still unable to take the other corners and can only play B2,1, B3,4, or B4,3. We play B4,3 which is necessary to prevent a board with empty spaces.

| |B|B|B|  
| |W|B|W|  
|W|B|B| |  
|B| |B| |

W now plays W3,4 and flips two of the three black pieces in the center, making for no further available moves for white, allowing black to complete the board clear when the correct sequence is chosen.

| |B|B|B|  
| |W|B|W|  
|W|W|W|W|  
|B| |B| |

B now plays carefully on order to prevent any available moves opening up for white. Black plays B4,4 next.

| |B|B|B|  
| |W|B|B|  
|W|W|W|B|  
|B| |B|B|

With no available moves for white, white passes and black moves again, this time playing B1,1 and taking the only remaining corner:

|B|B|B|B|  
| |B|B|B|  
|W|W|B|B|  
|B| |B|B|

Again white cannot move and black must play B4,2 now. If black played B2,1 instead, it would flip all remaining white pieces, but also leave one empty space and it would not result in a complete board clear.

|B|B|B|B|  
| |B|B|B|  
|W|B|B|B|  
|B|B|B|B|

Now white must again pass and black can play the final piece at B2,1, resulting in a complete board clear.

|B|B|B|B|  
|B|B|B|B|  
|B|B|B|B|  
|B|B|B|B|

A board clear exists for the $k = 1$ case. Q.E.D.

Now that we have proved the $k = 1$ case, we extend it by assuming the $k = x$ case holds, and prove that it still holds for $k = x + 1$.

Case 2: $k = x$ implies $k = x + 1$

Here we define what the $k = x$ case means: $x \gt 1$ would imply that the board is enlarged by two rows or columns $x-1$ times. More simply, it means that $m$ or $n$ is increased, $m$ being increased first followed by $n$. Which direction it is enlarged in does not matter (a solution for a $4\times6$ board is the same as a solution for a $6\times4$ board thanks to rotational symmetry). We will take $x = 2$ to be a $6\times4$ board.

Theorem: If a solution exists for a $k = x$ or $2n \times 2m$ board, then a solution exists for an $k = x + 1$ or $2n \times 2(m+1)$ board.

Proof. If $x = 2$, and thus $m = 3$ the theorem states that a $6\times4$ solution implies a $6\times6$ solution. In this case, we take the solution for the $6\times4$ board to be similar to the $4\times4$ solution, only having 8 more moves in the sequence. The word “similar” here means that it is obtained via the same general strategy; having black win, having white avoid the corners and black take them immediately, unless it results in one or more blank spaces, and so on. Our $k = 1$ case did not prove that a solution exists for any other strategy, so it would make sense to continue with that same strategy.

More generally, there will be $2m$ more moves in a $x+1$ solution than for the $x$ solution, if as previously noted, adding one to $m$ or $n$ expands the board in one direction (and due to the given inequality, $m$ must always increase before $n$).

Our task is to show that $2m$ additional possible moves along one dimension of the board does not eliminate every possible sequence which results in a board clear.

For the $k = x$ case, we know that there exists a sequence $F$ which results in a board clear. Let's examine this sequence and begin at the first point $z$ where there is an additional move $F_z$ in a $x+1$ sized board that would not exist on the $x$ sized board, and therefore could alter the existence of a solution, and the sequence of moves required for such a solution.

Due to the rules of Othello, moves can only occur which are adjacent to other pieces. We will prove that $F_z$ could not occur prior to the first $m$ moves. In the $6\times4$ case, for example, it requires at least $m = z = 3$ moves for either black or white to move into the new lowest row of the board (either could be thought of as the 'new' dimension, so we will choose row - rotational symmetry again proves that it doesn't matter which one we choose).

Let's prove this sub-point.

Lemma A: For the first move $F_z$ for an $x+1$ sized board such that the move $F_z$ does not exist on an $x$ sized board, $z$ must be at least $m$.

Sub-proof. Take a $6\times4$ board as an example. We will attempt to make a sequence of moves that most quickly encounters $F_z$ in row 6 of the $6\times4$ board (taking rows 1 and 6 to be the new dimension in a $6\times4$ board). Even when choosing optimal moves in that direction, $F_z$ can occur no sooner than $z \ge m$.

Remark: No matter the board size, the same 2x2 checkerboard pattern is used to begin the game, placing it in the center.

| | | | |
| | | | |
| |B|W| |
| |W|B| |
| | | | |
| | | | |

Black moves first and plays B2,5 heading straight towards row 6. ($F_1$)

| | | | |
| | | | |
| |B|W| |
| |B|B| |
| |B| | |
| | | | |

Next white also moves near the bottom by playing W3,5 - playing 1,5 instead is seen to afford black no option to continue play towards row 6. ($F_2$)

| | | | |
| | | | |
| |B|W| |
| |B|W| |
| |B|W| |
| | | | |

Black can now take the corner in row 6 at B6,4. ($F_3$)

| | | | |
| | | | |
| |B|W| |
| |B|W| |
| |B|B| |
| | | |B|

Thus B6,4 is an example of such a move $F_z$. For $m = 3$, a move $F_z$ exists no sooner than when $z = 3$. New dimensions on larger boards will necessarily be farther away than in this example, and therefore will take even more moves to reach. The starting layout size does not change, nor does the amount of moves required to progress across the board. Therefore for any size board, $F_z$ can occur no sooner than when $z = m$. Q.E.D.

By lemma A, the first $m$ moves can therefore be assumed to be the same for both solutions ($x$, and $x+1$ if it exists) - there is no reason they should be different, especially as we decided the solutions will be similar. No additional moves are available. Any moves prior to $F_z$ made as part of the $k = x$ solution must also be valid moves towards a $k = x + 1$ solution.

So now the task is to prove that from the first move $F_z$ where the $x$ solution and the $x+1$ game could diverge, there is nothing than can completely eliminate the possible outcome, and therefore the existence, of a board clear.

Let's now examine the end of the game. We saw in the $k = 1$ case ($4\times4$ board) that the last few moves were exclusively made by the winning player, black as we have determined. We will now prove that there exists a move $F_w$ which begins a sequence of remaining moves for black $B_w$ for which white must continue to pass, and which results in a board clear for black.

Lemma B: The white-pass sequence denoted $B_w$ begins at least $2m$ moves from the end of the game, and at most $2n + 2m + 4$. So $2(n+m)+4 \ge w \ge 2m$.

Sub-Proof. In the $k = 1$ case ($2m = 4$ since the board there was $4\times4$) the last 4 moves of the game were exclusively made by black, with no moves becoming available for white. Since such a sequence exists for a $4\times4$ board, and a solution exists for a $6\times4$ board (by the premise of our current $k = x$ case), $B_w$ must exist in the $k = x$ solution, and must begin no less than 4 moves from the end of the game, since the solutions are similar. The same sequence $B_w$ that exists for the $6\times4$ board solution must necessarily be at least 4 moves, and in general must be $2m$ moves. If any of the moves in $B_w$ allowed white to play, white would flip at least one black piece. At move $F_w$ there are no middle board spaces left; $F_w$ is at least 4 moves from the end and there must be more than $2n + 2m + 4$ spaces left (12 for a $4\times4$ board) for a middle space to be available. It could not occur when a middle space is available as that would either require a board clear state in the middle (for which no more moves would be possible), or allow white to move, and therefore not be part of $B_w$. Because there are no middle spaces left (by the middle-board completeness condition), white would have to play on a side or corner space and would therefore flip at least one black piece which would necessarily become stagnant, preventing black from being able to clear the board. This would violate the case $k = x$ premise that a board clear solution exists for a $6\times4$ board. Q.E.D.

By lemmas A and B, $z \ge m$ and $w \ge 2m$. This leaves $(2m * 2n) - 3m - 4$ critical moves in $F$ which could completely eliminate the existence of a board clear solution (the number of spaces $n \times m$ minus 4 starting pieces, minus $m$ moves until $F_z$, minus $2m$ moves in $B_w$). On a $6\times4$ board, for example, this would be $(6*4)-3(3)-4 = 24-9-4 = 11$ moves.

Lemma C: Define the critical sequence $C$ of length $4nm-3m-4$ moves, where $C_1 \ge z$ and $C_e \lt w$ (where $e$ is the last move in $C$, $z$ is the number of the first divergent move $F_z$, and $w$ is the number of the move $F_w$ beginning the white-pass sequence $B_w$). The moves in this sequence $C$ cannot eliminate the existence of a board clear solution.

Sub-Proof. If the game tree of the same length as the critical sequence statistically must contain one or more board clear solutions, then it is mathematically impossible for that critical sequence to completely eliminate the possibility and existence of such a board clear solution - something which has been proven to exist for a $4\times4$ board and which is given to exist for a $6\times4$ board. For a $4\times4$ board, the sequence $C$ is of length at least $(4*4)-3(3)-4 = 16-9-4 = 3$. $z = m = 3$, so $F_z$ (where a $6\times4$ solution would begin to diverge) is no sooner than move 3. The first two moves therefore are not part of the critical sequence. It then continues from moves three through eight. $B_w$ is seen in the earlier $k = 1$ solution to begin at move 9. Therefore the actual length of $C$ in this particular example is six.

Let's determine the statistical possibility of a board clear (during the critical sequence of $C$ length 6) for all possible game trees of a $4\times4$ board. The game tree pruned to this size is still fairly large. Order matters, so we use permutation to count the tree size. $P(12,6)$ for 12 possible moves taken 6 at a time gives us just over 600 thousand permutations, with actual valid moves accounting for maybe half of that (black can't flip black pieces, only white, and vice versa), so roughly 300 thousand. Since a board clear solution exists for the $4\times4$ board, it's likely that many of these 300 thousand other possibilities are also board clear solutions - probably not just for black, either. If you take the probability of a board clear solution from a purely statistical standpoint, there are 12 moves for a $4\times4$ board which can result in a score from 16-0 to 0-16 and anywhere in between. 16-0 and 0-16 boards have only one such result, but the in between boards have many more variations which would result in the same score. Taking all this into account, the chances of getting either version of a 16-0 board clear, assuming you pick any random, valid game tree choice from the critical set, is $2/32$ at face value, minus all the additional results which share the same scores.

The number of these can be thought of by taking some number $J$ to be the lesser of the two scores. So for a 16-0 result, $J = 0$; for a 15-1 result, $J = 1$, for a 14-2 game, $J = 2$, etc. The bigger $J$ is, the more board states exist that give rise to the same score. This is given by $C(12,J)$ (because from a board result perspective, order doesn't matter) which for all the results from 15-1 through 1-15 (the in between) evaluates to

$2 * ( C(12,1) + C(12,2) + ... + C(12,8) )$

$= 2 * ( 12 + 66 + 220 + 495 + 792 + 924 + 792 + 495 )$

$ = 7592$

So this means rather than 2 chances out of 32 at face value, we have 2 chances out of 32 plus 7592 or rather two out of 7624 which comes out to 0.02 percent, which for 300,000 games works out to 78.6 games. So statistically speaking, if one board clear solution exists, as proved earlier, then 77 alternate board clear solutions should exist in the same game tree.

We are examining the possibility that the critical sequence $C$ alters the existence of a board clear solution. In order to do so, a sequence of that length would have to necessarily eliminate all board clear solutions in the game tree. Statistically it cannot; there are 78 remaining board clear solutions in a game tree of the same size as the critical sequence $C$. There would have to exist a sequence C such that, by the end of the sequence, none of those 78 solutions exist, regardless of which game tree path is taken. We have proved that, mathematically, there can be no such sequence. When we come to the end of a critical sequence of length C, with the appropriate nodes pruned to account for the specific $F_z$ opening sequence we are looking at, we find 78 board clear solutions still available to us. The critical move sequence therefore does not eliminate the existence of a board clear solution when going from $k = 1$ to $k = 2$.

Now this must be generalized for all board sizes. [unproven as pointed out by Peter Taylor]

A solution exists for $k = 1$, and the case $k = x + 1$ is true if the case $k = x$ holds; the only critical sequence $C$ which could eliminate the existence of a board clear solution does not eliminate it completely.

Take $x$ to be 1. By the first proof, case $k = 1$ holds. By the second proof, case $k = x + 1$ or $k = 2$ holds. Also by the second proof, case $k = x + 2$ holds (by case $k = x + 1$). And so forth.

Therefore, by induction, a board clear solution exists for a board of any size $2n \times 2m$. [unproven as it relies on the unfinished $k = x + 1$ generalization proof above]

$\endgroup$
  • $\begingroup$ The inductive step is nowhere near proven. The argument gives a heuristic argument that it's possible to get from $k=1$ to $k=2$. That's a long way short of what's required. $\endgroup$ – Peter Taylor May 20 '17 at 9:59
  • $\begingroup$ Fair point, I see what you mean. I still think it's fairly intuitive that as the game tree grows, even more board clears exist statistically so that as the critical sequence grows, it always has more solutions to eliminate and can never overtake them. But it definitely needs proven de facto. $\endgroup$ – Tim May 21 '17 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.