Check Old Game winner

20

The algorithm teacher asked us to write a code to play a simple old game in Java. And I already have everything ready, but I'm not too happy with the solution I've got to validate who won the game.

I've done a series of if and elseifs to check each condition in which a player can win the game. And okay, that covers what the teacher asked, but I do not think that's the smartest way to write an algorithm. I was thinking of using embedded reps (for inside for) but I can not find a way where I can apply this in the algorithm, or maybe from thinking so much I can no longer think straight.

I also thought about creating an array with all possible possibilities:

   final int[][][] condicoesVencer = {
    //COLUNAS
    {{ 0, 0 }, { 1, 0 }, { 2, 0 }},
    {{ 0, 1 }, { 1, 1 }, { 2, 1 }},
    {{ 0, 2 }, { 1, 2 }, { 2, 2 }},

    //LINHAS
    {{ 0, 0 }, { 0, 1 }, { 0, 2 }},
    {{ 1, 0 }, { 1, 1 }, { 1, 2 }},
    {{ 2, 0 }, { 2, 1 }, { 2, 2 }},

    //DIAGONAIS
    {{ 0, 0 }, { 1, 1 }, { 2, 2 }},
    {{ 2, 0 }, { 1, 1 }, { 0, 2 }}
};

condicoesVencer saves all possible combinations of wins, the positions of the char tabuleiro[][] = new char[3][3] vector where X or O can win. But I did not get a way to traverse the two vectors so as to check in the vector tray each condition in the condicoesVencer vector and now I do not know what to do.

How to replace the mount of ifs I've done in something more 'smart'? Please, if you have an answer, please send the code and explain.

EDIT: Here's the method I created, with all ifs:

public boolean haGanhador(){
    //Checa X verticalmente
    if(tabuleiro[0][0] == 'X' && tabuleiro[1][0] == 'X' && tabuleiro [2][0] == 'X'){
        System.out.println("'X' VENCEU");
        return true;
    }
     else if(tabuleiro[0][1] == 'X' && tabuleiro[1][1] == 'X' && tabuleiro[2][1] == 'X'){
        System.out.println("'X' VENCEU");
        return true;
     }
     else if(tabuleiro[0][2] == 'X' && tabuleiro[1][2] == 'X' && tabuleiro[2][2] == 'X'){
        System.out.println("'X' VENCEU");
        return true;
    }



     //Checa X horizontalmente
     else if(tabuleiro[0][0] == 'X' && tabuleiro[0][1] == 'X' && tabuleiro[0][2] == 'X'){
    System.out.println("'X' VENCEU");
    return true;
    }
    else if(tabuleiro[1][0] == 'X' && tabuleiro[1][1] == 'X' && tabuleiro[1][2] == 'X'){
    System.out.println("'X' VENCEU");
    return true;
    } 
    else if(tabuleiro[2][0] == 'X' && tabuleiro[2][1] == 'X' && tabuleiro[2][2] == 'X'){
    System.out.println("'X' VENCEU");
    return true;
    }
    //Checa X diagonalmente
    else if(tabuleiro[0][0] == 'X' && tabuleiro[1][1] == 'X' && tabuleiro[2][2] == 'X'){
    System.out.println("'X' VENCEU");
    return true;
    }
    else if(tabuleiro[0][2] == 'X' && tabuleiro[1][1] == 'X' && tabuleiro[2][0] == 'X'){
    System.out.println("'X' VENCEU");
    return true;
    }
    //Checa O verticalmente
    if(tabuleiro[0][0] == 'O' && tabuleiro[1][0] == 'O' && tabuleiro [2][0] == 'O'){
    System.out.println("'O' VENCEU");
    return true;
    }
    else if(tabuleiro[0][1] == 'O' && tabuleiro[1][1] == 'O' && tabuleiro[2][1] == 'O'){
    System.out.println("'O' VENCEU");
    return true;
    }
    else if(tabuleiro[0][2] == 'O' && tabuleiro[1][2] == 'O' && tabuleiro[2][2] == 'O'){
    System.out.println("'O' VENCEU");
    return true;
    }

    //Checa O horizontalmente
    if(tabuleiro[0][0] == 'O' && tabuleiro[0][1] == 'O' && tabuleiro[0][2] == 'O'){
    System.out.println("'O' VENCEU");
    return true;
    }
    else if(tabuleiro[1][0] == 'O' && tabuleiro[1][1] == 'O' && tabuleiro[1][2] == 'O'){
    System.out.println("'O' VENCEU");
    return true;
    }
    else if(tabuleiro[2][0] == 'O' && tabuleiro[2][1] == 'O' && tabuleiro[2][2] == 'O'){
    System.out.println("'O' VENCEU");
    return true;
    }

    //Checa O diagonalmente
    if(tabuleiro[0][0] == 'O' && tabuleiro[1][1] == 'O' && tabuleiro[2][2] == 'O'){
    System.out.println("'O' VENCEU");
    return true;
    }
    else if(tabuleiro[0][2] == 'O' && tabuleiro[1][1] == 'O' && tabuleiro[2][0] == 'O'){
    System.out.println("'O' VENCEU");
    return true; 
    }

    return false;
}
    
asked by anonymous 08.10.2014 / 13:48

4 answers

11

Since you prefer with a few IF s, I made a solution using IF and FOR only.

Solution:

public class JogoVelha {

    public static String obtemVencedor(String[] tabuleiro) {

        if ((tabuleiro == null) || (tabuleiro.length != 9)) {
            throw new IllegalArgumentException
                ("Um tabuleiro deve ser um array de 9 posições.");
        }
        Integer[][] padroesVitoria = {
                    {0, 1, 2},
                    {0, 4, 8},
                    {0, 3, 6},
                    {1, 4, 7},
                    {2, 5, 8},
                    {2, 4, 6},
                    {3, 4, 5},
                    {6, 7, 8}};

        for (Integer[] padraoVitoria: padroesVitoria) {

            boolean haVencedor = tabuleiro[padraoVitoria[0]] != null 
                && tabuleiro[padraoVitoria[0]].equals(tabuleiro[padraoVitoria[1]]) 
                && tabuleiro[padraoVitoria[0]].equals(tabuleiro[padraoVitoria[2]]);

            if (haVencedor) {
                String vencedor = tabuleiro[padraoVitoria[0]];
                return vencedor;
            }
        }
        return null;
    }
}

Test:

@Test
public void jovadorXVence() {

    String[] tabuleiro = {
            "X", "O", null, 
            "O", "O", null,
            "X", "X", "X"} ;

    String vencedor = JogoVelha.obtemVencedor(tabuleiro);

    assertEquals("X", vencedor);
}

@Test
public void naoHaVencedor() {

    String[] tabuleiro = {
            "X", "O", null, 
            "O", "O", null, 
            "X", null, "X"} ;

    String vencedor = JogoVelha.obtemVencedor(tabuleiro);

    assertNull(vencedor);
}

My approach was as follows:

  • I noticed that the board has nine positions. Your visualization would look something like this:

    0 | 1 | 2
    ---------
    3 | 4 | 5
    ---------
    6 | 7 | 8
    
  • Then the filled or partially filled board is represented by a 9-position array.

  • Then I visualized an example of finished game. It would look like this:

    X | O | -
    ---------
    O | O | -
    ---------
    X | X | X
    
  • Viewing this completed game within my array, I have identified the winning patterns (which positions within the array, when occupied by the same player, signal a win):

    0 1 2
    0 4 8
    0 3 6
    1 4 7
    2 5 8
    2 4 6
    3 4 5
    6 7 8
    
  • And then I wrote an algorithm to process the array representing a board, looking within it for the patterns of victory.

After each move, obtemVencedor can be invoked to identify if there is already a winner. If there is no winner, we can check if there are still available positions on the board (if there are elements not null in the array) to see if the game has finished tied.

    
08.10.2014 / 15:00
9

You can use for loops to check at the end of each round (from the third round) the winner, I would do the following:

1. Fora do for verifica diagonais são iguais
2. Verifica se linha i todas as colunas são iguais
3. Verifica se coluna i todas as linhas são iguais

Encoding would look something like this:

public boolean fimDoJogo(){
  if((matriDoJogo[0][0] == matriDoJogo[1][1] && matriDoJogo[1][1] == matriDoJogo[2][2]) || 
     (matriDoJogo[0][2] == matriDoJogo[1][1] && matriDoJogo[1][1] == matriDoJogo[2][0])){
    System.out.println("Venceu o jogador que escolheu o "+matriDoJogo[1][1]);
    return true;
  }
  for(int i = 0; i < 3; i++){
    if(matriDoJogo[i][0] == matriDoJogo[i][1] && matriDoJogo[i][1] == matriDoJogo[i][2]){
      System.out.println("Venceu o jogador que escolheu o "+matriDoJogo[i][1]);
      return true;
    }
    if(matriDoJogo[0][i] == matriDoJogo[1][i] && matriDoJogo[1][i] == matriDoJogo[2][i]){
      System.out.println("Venceu o jogador que escolheu o "+matriDoJogo[1][i]);
      return true;
    }
  }
  return false;
}

It would still be possible to change the method return, to return which player token won.

    
08.10.2014 / 14:27
7

Use bitmaps.

Your 'board' can be expressed in a sequence of bits, like this:

Posições
2 | 1 | 0
5 | 4 | 3
8 | 7 | 6

It is equivalent to:

Posição 876543210
Bit     000000000

The following win condition

Posições
X |   |  
  | X |  
  |   | X

It can then be expressed as follows:

001 010 100 = Decimal 84

To verify that the player has reached this condition, turn the positions occupied by him into a binary map as well.

Posições
A | B |  
  | A | A 
B | B | A

Apenas jogador A
A |   |  
  | A | A 
  |   | A

Bitmap:

001 011 100 = Decimal 92

Now perform a AND operation between the two:

001 010 100 AND
001 011 100 = 
001 010 100   Decimal 84

If the result of the AND operation equals the win condition value, the player won.

Create an array with all possible win conditions:

Integer[] mapasVitoria = 
    {
    0b100100100, //Todas as posições da Coluna 1
    0b010010010, //Todas as posições da Coluna 2
    0b001001001, //Todas as posições da Coluna 3

    0b111000000, //Todas as posições da Linha 1
    0b000111000, //Todas as posições da Linha 2
    0b000000111, //Todas as posições da Linha 3

    0b100010001, //Diagonal Topo esquerdo -> Fundo direito
    0b001010100  //Diagonal Topo direito -> Fundo esquerdo
    };

and compare each player's bitmap to each bid.

    
08.10.2014 / 16:13
1

Look at the simplest way that I think you can solve this whole problem is with this code:

possibilidades = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{6,4,8}}

for (p: possibilidades)
    if(tabuleiro[p[0]] == (tabuleiro[p[1]] == (tabuleiro[p[0]] && tabuleiro[p[0]] != null )
        System.out.println("Venceu");

Considering that:

1 - You have initialized a vector of 9 positions with null value (tray)

2 - every time a move takes place you validate yourself won

Possibilities are the map of valid moves, all positions of a possibility must be equal (X / O) and different from null which is the initial value of the map.

I hope I have helped!

    
08.10.2014 / 17:04