Tic-tac-toe 'get winner' algorithm

As a first step to attempting the Weekend Challenger Reboot, I decided to first implement a regular 'tic-tac-toe' game and then expand it later to be 'ultimate tic-tac-toe'.

Below is the code for the tic-tac-toe board. It's fully functional and unit tested, but I'm not too happy about the getWinner() method. This method's purpose is to check to see if there is any winner in the game, and to return the identity of said winner if they exist.

The reasons I don't like it are:

1. The method is very long, which immediately sets off warning flags in my mind.
2. It makes use of a 'flag' type variable that tracks if we've found a winner yet. I don't like flag variables because they're really something that I got in the habit of doing back when I did procedural programming, and therefore probably shouldn't exist in an object-oriented design.
3. There's an awful lot of continue and break statements which seem to indicate poorly-designed loops.
4. I'm pretty sure that if there is no winner, this method is O(n2).

This is the code for the getWinner() method:

public class Board {
private final Player[][] fields;
...
public Player getWinner() {
Player winner = null;
boolean isWon = false;

// check columns (same x)
for (int x = 0; x < fields.length; x++) {
Player value = fields[x];

if (value == null) {
continue;
}
for (int y = 1; y < fields[x].length; y++) {
Player current = fields[x][y];
if (current == null || !current.equals(value)) {
break;
}
if (y == fields[x].length -1) {
isWon = true;
winner = value;
}
}
if(isWon) {
break;
}
}

if (! isWon) {
// check rows (same y)

for (int y = 0; y < fields.length; y++) {
Player value = fields[y];
if (value == null) {
continue;
}
for (int x = 1; x < fields.length; x++) {
Player current = fields[x][y];
if (current == null || !current.equals(value)) {
break;
}
if (x == fields.length -1) {
isWon = true;
winner = value;
}
}
if(isWon) {
break;
}
}

}
if (! isWon) {
// check diagonal (bottom left to top right

Player value = fields;
if (value != null) {
for (int i = 1; i < fields.length; i++) {
if (fields[i][i] != value) {
break;
}
if (i == fields.length -1) {
isWon = true;
winner = value;
}
}
}
}

if (! isWon) {
// check anti-diagonal (top left to bottom right)
int length = fields.length;
Player value = fields[length-1];
if (value != null) {
for (int i = 1; i < length; i++) {
if (fields[i][length-i-1] != value) {
break;
}
if (i == length -1) {
isWon = true;
winner = value;
}
}
}
}
return winner;
}
...
}

The rest of the code is mostly irrelevant. Something important to be aware of is that the board will always be a perfect square -- eg. 3x3 or 4x4 or 5x5. The Player is a simple enum:

public enum Player {
X("X"),
O("O");

private String str;
private Player(String str) {
this.str = str;
}

@Override public String toString() {
return str;
}
}
• Nice that you support multiple sizes, I'm loving it! Feb 2 '14 at 16:09
• @sweeneyrod -- While the Board constraints have a minimum size of 3, there's no maximum. So in theory we could have a massize 100x100 board. (Not sure how fun the game would be, but there ya go.) Feb 2 '14 at 19:44
• @RoddyoftheFrozenPeas It becomes horrifyingly more difficult to win on a 100x100 board, I can tell you that! Feb 2 '14 at 20:55
• @RoddyoftheFrozenPeas a 100,100,? game is in the same category as a 3,3,3 - both of which are known as m,n,k-games.
– user22048
Feb 2 '14 at 21:21
• @MichaelT I have to thank you for that comment, that's what made me make my flexible Tic-Tac-Toe implementation May 6 '14 at 22:43

It's method extraction time!

But before that, I have to comment on your Player enum:

• str is a bad name, name would be better.
• Speaking of name, all enums have a name() method by default. You don't need your str variable, return name(); instead.
• Speaking of return name();, that's exactly what the default implementation of toString() already does for enums. Absolutely no need to override it.

And therefore, we've reduced your Player enum to:

public enum Player {
X, O;
}

Ain't it lovely with enums? :)

Now, back to your getWinner() method:

You have a whole bunch of duplicated code there indeed. It would be handy if you could get a Collection of some kind (or an array), add some elements to it and check: Is there a winner given by these Player values?

This is just one version of doing it, it's not the optimal one but it should get you started. This code will add a bunch of Player objects to a list and then we check if those objects match to find if there's a winner.

List<Player> players = new ArrayList<>();
for (int x = 0; x < fields.length; x++) {
for (int y = 0; y < fields[x].length; y++) {
}
Player winner = findWinner(players);
if (winner != null)
return winner;
}

Player findWinner(List<Player> players) {
Player win = players.get(0);
for (Player pl : players) {
// it's fine that we loop through index 0 again,
// even though we've already processed it.
// It's a fast operation and it won't change the result
if (pl != win)
return null;
}
return pl;
}

Please note that there are even more improvements possible for the getWinner method, I don't want to reveal all my secrets for now though ;) And also, this is just one way of doing it, which will reduce your code duplication a bit at least. There are other possible approaches here as well.

Consider using better data structures (objects). Your constructor will be more complex, but all the complexity will be there, not in the algorithm.

Here's a beginning of a design. Lots of details to work out, maybe not worth the effort if you're almost done and just cleaning things up.

Build a Set whose elements are Sets whose contents are the elements of the winning rows, columns and long diagonals (only 2n+2 of these for an nxn board).

To test for a win, iterate on that Set and see whether any of its elements (potential wins) has just one element (different from EMPTY). (You'll want to allow three values in cells: X, O and EMPTY).

This is a classic case of where early-return makes sense....

There are some schools of thought that suggest early return is a bad thing, but consider changing all your if (isWon) {break;} statements to be return winner;.

We can then get rid of the isWon and the winner variables entirely, as well as the then the unnecessary checks to gate each logic loop. Your method would look like:

public Player getWinner() {

// check columns (same x)
for (int x = 0; x < fields.length; x++) {
Player value = fields[x];

if (value == null) {
continue;
}
for (int y = 1; y < fields[x].length; y++) {
Player current = fields[x][y];
if (current == null || !current.equals(value)) {
break;
}
if (y == fields[x].length -1) {
//  Early Return.... We have a WINNER!
return value;
}
}
}
// there was no winner in this check
// no need for isWon check or variable... we can't get here unless there is
// no winner yet....
for (int y = 0; y < fields.length; y++) {
Player value = fields[y];
if (value == null) {
continue;
}
for (int x = 1; x < fields.length; x++) {
Player current = fields[x][y];
if (current == null || !current.equals(value)) {
break;
}
if (x == fields.length -1) {
// We have a winner!
return value;
}
}
}

}
// and so on....
....

// there is no winner.
return null;
}

Hints on how to reduce your cyclomatic complexity:

1. if (isWon) { break; } at the end of the outer loop is the same as && !isWon inside the guard of the loop.
2. if (value == null) { continue; } before the inner loop is the same as && (value != null) in the guard of the loop.
• Your first suggestion does not actually reduce the complexity... it just moves it from two if statements with a complexity of 1 each, to a single if statement with a complexity of 2 (because there are two ways pass through the condition with short-circuit logic). Your second statement has the same flaw Feb 3 '14 at 2:27
• It at least makes it easier to read :) But from my non-expert reading of wikipedia, the complexity seems to be reduced; using the (value == null) example, in the original code there are four paths (neither block is entered, (value == null) block is entered, loop is entered, or both are entered), but with my suggestion, there are only two paths (the loop is entered, or the loop is not entered). But even if the cyclomatic complexity is not reduced, I think the readability is enhanced. Feb 3 '14 at 2:36

I would make a function that takes the play field and a 'kernel' to run over each cell.

Here's some code for you:

void Main()
{
int[][] verticalWin = { new int[] {0,1}, new int[] {0,2} };
int[][] horizontalWin = { new int[] {1,0}, new int[] {2,0} };

int[][] playfield = { new int[] { 20,10,10 },
new int[] { 20,10,20 },
new int[] { 10,10,10}};

var winner = GetWinner(playfield, verticalWin);
Console.WriteLine(winner);

winner = GetWinner(playfield, horizontalWin);
Console.WriteLine(winner);
}

// Define other methods and classes here

int GetWinner(int[][] playfield, int[][] kernel){
for (int x=0; x<playfield.Length; x++){
for (int y=0; y<playfield.Length; y++){
var player = playfield[x][y];
int k=0;
while (k<kernel.Length
&& playfield.Length > (kernel[k] + x)
&& playfield.Length > (kernel[k] + y)
&& player == playfield[x+kernel[k]][y +kernel[k]]
) {
k++;
}
if (k==kernel.Length){
return player;
}
}
}
return 0;
}

Obviously I've made some simplifications, but it should just be a matter of changing the type of the player variable, and create your kernels for win conditions. The length of the kernel (index 0,0 aka current cell is implied) will determine how many in a row is needed.

• if you need optimization because of a large playfield, you can simply check early that the current x,y index is within the bounds of the most extreme attempted index of the kernel (if you follow my outlined convention, the most extreme case will always be the last coordinate of the kernel). Let me know if you like to give this a go and I can help to identify what needs to change. Good luck on your project! Feb 3 '14 at 14:11
• This code doesn't look very readable to me. It is quite hard to follow how it works. Your while condition is very big and your k and kernel variables could also be named better... Feb 4 '14 at 18:56
• What readable code is is highly subjective - that said I agree that it should be commented. The while check can be extracted to a method if wanted. Readable code is good, though working code also have some value. Don't forget that I also offered to help with the final implementation, as opposed to withholding some magic sauce. ;) Feb 4 '14 at 21:06

Well, if the players are considered to be 0 and 1, and the game matrix to be frame, then given a player and a matrix, I can easily get a winner without having to check all possibilities!

int winner(int player, int pos) {
int v = 0, h = 0, s0 = 0, s1 = 0;
int col = pos % 3;
int row = pos / 3;
for (int i = 0; i < 3; i++) {
if (frame[i][col] == player) {
v++;// vertical
}
if (frame[row][i] == player) {
h++;// horizontal
}
}
if (pos % 4 == 0) {
for (int i = 0; i < 3; i++) {
if (frame[i][i] == player) {
s0++;// backward slash like slant
}
}
}
if ((pos + 2) % 4 == 0) {
for (int i = 0; i < 3; i++) {
if (frame[2 - i][i] == player) {
s1++;// forward slant
}
}
}

if (v == 3 || h == 3 || s0 == 3 || s1 == 3) {
return player;
}
return -1;
}
• What is pos? Also, it looks like this method only works for a 3x3 tic-tac-toe implementation -- could it be expanded for boards of arbitrary size? Jul 31 '14 at 15:44
• Welcome to Code Review! Could you be a bit more descriptive in your answer ? It's not the best way to dump code in an answer for reviewing code. You could explain how you achieve this algorithm. Jul 31 '14 at 15:45