title: Minimax debugging. Not sure how to look for where the code is falling apart
body: <p>First time actually using the site so if I do anything wrong I apologize in advance and will work to correct it given guidance. I am currently working on my senior project. It is a game very similar to tic-tac-toe but the height and width of the board are of variable sizes and the amount in a row needed to win is also variable (all chosen by the user through jcomboboxes).</p>
  
  <p>the problem is that the miniMax method will often select a tile that's already been chosen. I'm not entirely sure how to figure out the source of the problem, after having done quite a few hours of research. I just need to be pointed in the right direction on the means of finding the source but will gladly take any help I can get</p>
  
  <p>attached below is the code. I provided all of the code for the program so that it can be compiled and tested, hopefully, with ease. If this is the wrong thing to do I apologize, let me know and I will correct.</p>
  
  <p>I found various examples of the minimax algorithm being implemented and ended up using the one in the following link: <a href="https://stackoverflow.com/questions/45168697/simplest-minimax-algorithm-for-tictactoe-ai-in-java">simplest MiniMax algorithm for TicTacToe AI in Java</a></p>
  
  <p>I also tried implementing the following: <a href="https://medium.com/@pelensky/unbeatable-tic-tac-toe-minimax-in-java-e1ad687ed821" rel="nofollow noreferrer">https://medium.com/@pelensky/unbeatable-tic-tac-toe-minimax-in-java-e1ad687ed821</a></p>
  
  <p>but that led to numerous stackoverflow errors that I couldn't see how to reasonably mitigate without redoing the entire algorithm.</p>
  
  <p>I am currently working with the former and it works to an extent but the AI doesn't appear to make intelligent decisions and will often try to choose a tile that's already been selected.</p>
  
  <pre><code>import java.awt.Dimension;
  import java.awt.GridLayout;
  import java.awt.Window;
  import java.awt.event.ActionEvent;
  import java.awt.event.ActionListener;
  import java.io.IOException;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.HashMap;
  import java.util.Map;
  
  import javax.swing.*;
  
  public class Konnexion extends JPanel
  {
      ArrayList&lt;JButton&gt; buttons = new ArrayList&lt;JButton&gt;(); 
      private static int totalButtons;
      private JLabel winStat;
      private JLabel lossStat;
      protected JLabel drawStat;
      JPanel gameBoard;
      JButton exitButton;
      int wins = 0;
      int losses = 0;
      int draws = 0;
      Game game;
  
  
      public Konnexion(int height, int width, int connects, String ai)
      {
        JPanel gameStats = new JPanel();
        gameStats.setLayout(new GridLayout(1,3));
        winStat = new JLabel("Wins: " + wins);
        lossStat = new JLabel("Losses: " + losses + " ");
        drawStat = new JLabel("Draws: " + draws);
        gameStats.add(winStat);
        gameStats.add(lossStat);
        gameStats.add(drawStat);
        add(gameStats);
  
            totalButtons = (height * width) - 1;
            gameBoard = new JPanel();
        gameBoard.setLayout(new GridLayout(height,width));
        initializebuttons();
        add(gameBoard);
  
        JPanel menuButtons = new JPanel();
        menuButtons.setLayout(new GridLayout(1,1));
        exitButton = new JButton();
        exitButton.setText("Exit Game");
        exitButton.addActionListener(new buttonListener());
        menuButtons.add(exitButton);
        add(menuButtons);
  
        game = new Game(totalButtons, height, width, connects, ai);
      }
  
      public void initializebuttons()
      {
          for(int i = 0; i &lt;= totalButtons; i++)
          {
                  buttons.add(i, new JButton());
                  buttons.get(i).setText("");
                  buttons.get(i).setPreferredSize(new Dimension(75,75));
              buttons.get(i).addActionListener(new buttonListener());
  
              gameBoard.add(buttons.get(i));
          }
      }
  
      public void resetButtons()
      {
          for(int i = 0; i &lt;= totalButtons; i++)
          {
              buttons.get(i).setText("");
          }
          game.resetGameState();
      }
  
      private class buttonListener implements ActionListener
      {
  
          public void actionPerformed(ActionEvent e) 
          {
  
              JButton buttonClicked = (JButton)e.getSource(); //get the particular button that was clicked
              if (buttonClicked.getText().equals(""))
              {
  
                      buttonClicked.setText(Game.getSymbol(game.getCurrentPlayer()));
                  game.setMarker(buttons.indexOf(buttonClicked), game.getSymbol(game.getCurrentPlayer()));
                  if (Game.getSymbol(game.getCurrentPlayer()).equals("X")) 
                  {
                                  game.changeCurrentPlayer();
                          if (game.hasWon("X", Game.cells)) {
                                  wins++;
                                  winStat.setText("Wins: " + wins);
                              JOptionPane.showConfirmDialog(null, "Player X Wins!!!");
                              resetButtons();
                              game.resetGameState();
                          }
                  }
                  else
                  {
                              game.changeCurrentPlayer();
                          if (game.hasWon("O", Game.cells)) {
                                  losses++;
                                  lossStat.setText("Losses: " + losses + " ");
                          JOptionPane.showConfirmDialog(null, "Player O Wins!!!");
                          resetButtons();
                          game.resetGameState();
                      }
                  }
  
                  if (game.getCurrentPlayer() == 2) {
                          game.printArrays();
                          game.copyGameState();
                          //System.out.println(game.miniMax(game.getCurrentPlayer()));
                          buttons.get(game.miniMax(game.getCurrentPlayer())).doClick();
                  }
              }
              else if (buttonClicked.equals(exitButton))
              {
                      Window window = SwingUtilities.getWindowAncestor(exitButton);
                      window.dispose();
                      try {
                          new MainMenu();
                      } catch (IOException e1) {
                          // TODO Auto-generated catch block
                          e1.printStackTrace();
                      }
              }
              else
              {
                      JOptionPane.showMessageDialog(buttonClicked, "That tile has already been selected!");
              }
  
              if (game.checkDraw())
              {
                      draws++;
                      drawStat.setText("Draws: " + draws);
                  JOptionPane.showConfirmDialog(null, "It was a Draw!!!");
                  resetButtons();
              }
          }
      }
  
  }
  </code></pre>
  
  <pre><code>import java.io.IOException;
  import java.util.HashMap;
  import java.util.Map;
  
  public class Game {
      public static int ROWS;
      public static int COLS;
      public static int WIN_SIZE;
      public static int currentPlayer;
      public static String[][] cells; //Game state array
      String[][] node; //copy of the game state used for minimax method
  
      public Game(int totalButtons, int height, int width, int connects, String difficulty) {
          ROWS = height;
          COLS = width;
          WIN_SIZE = connects;
          currentPlayer = 1;
          cells = new String[ROWS][COLS];
          node = new String[ROWS][COLS];
          resetGameState(cells);
          resetGameState(node);
      }
  
      public void setMarker(int space, String marker) {
          int col = space % COLS;
          int rows = space / COLS;
          cells[rows][col] = marker;
      }
  
      public void changeCurrentPlayer() {
          if (currentPlayer == 1)
          {
              currentPlayer = 2;
          }
          else if (currentPlayer == 2)
          {
              currentPlayer = 1;
          }
      }
  
      public int getCurrentPlayer() {
              return currentPlayer;
      }
  
      public static String getSymbol(int playerNum) {
          if (playerNum == 1)
              return "X";
          else
              return "O";
      }
  
      public void resetGameState() {
          currentPlayer = 1;
          for (int i = 0; i &lt; cells.length; i++) {
              for (int j = 0; j &lt; cells[i].length; j++) {
                  cells[i][j] = "-";
              }
          }
      }
  
      public static void resetGameState(String[][] gameState) {
          for (int i = 0; i &lt; gameState.length; i++) {
              for (int j = 0; j &lt; gameState[i].length; j++) {
                  gameState[i][j] = "-";
              }
          }
      }
  
      /**
       * 
       * @param theSeed   Value expected in each cell
       * @param row       Row index to check
       * @param col       Col index to check
       * @param count     Number of consecutive elements found in the line. 
       * @param rowIncrement   Increment to the row index for the next evaluation
       * @param colIncrement   Increment to the col index for the next evaluation
       * @return  true if there is a winner combination in the line, otherwise false. 
       */ 
      private boolean checkLine(String theSeed, int row, int col, int count, int rowIncrement, int colIncrement, String[][] gameCheck) {
          if (!areValidIndexes(row, col)) {
              return false;
          }
  
          if (theSeed.equals(gameCheck[row][col])) {
              count++;
              if (count &gt;= WIN_SIZE) {
                  return true;
              } else {
                  return checkLine(theSeed, row + rowIncrement, col + colIncrement, count, rowIncrement, colIncrement, gameCheck);
              }
          } else {
              return false;
          }
      }
  
  
      private boolean areValidIndexes(int row, int col) {
          if (row &gt;= 0 &amp;&amp; row &lt; ROWS &amp;&amp;
              col &gt;= 0 &amp;&amp; col &lt; COLS) {
              return true;
          }
          return false;
      }
  
      private boolean checkRow(String theSeed, int row, int col, String[][] gameCheck) {
          return checkLine(theSeed, row, col, 0, 1, 0, gameCheck);
      }
  
      private boolean checkColumn(String theSeed, int row, int col, String[][] gameCheck) {
          return checkLine(theSeed, row, col, 0, 0, 1, gameCheck);
      }
  
      private boolean checkForwardDiagonal(String theSeed, int row, int col, String[][] gameCheck) {
          return checkLine(theSeed, row, col, 0, 1, 1, gameCheck);
      }
  
      private boolean checkBackwardDiagonal(String theSeed, int row, int col, String[][] gameCheck) {
          return checkLine(theSeed, row, col, 0, -1, 1, gameCheck);
      } 
  
      public boolean hasWon(String theSeed, String[][] gameCheck) {
          for (int row = 0; row &lt; ROWS; row++) {
              for (int col = 0; col &lt; COLS; col++) {
                  if (checkRow(theSeed, row, col, gameCheck) ||
                      checkColumn(theSeed, row, col, gameCheck) ||
                      checkForwardDiagonal(theSeed, row, col, gameCheck) ||
                      checkBackwardDiagonal(theSeed, row, col, gameCheck)) {
  
                      return true;
                  }
              }
          }
          return false;
      }
  
      public boolean checkDraw()
      {
              String s = "";
          for (String[] r : cells) {
              for (String t : r) {
                  s += t;
              }
          }
  
              if (!s.contains("-"))
              {
                  return true;
              }
  
              return false;
      }
  
      public static boolean checkDraw(String[][] node)
      {
              String s = "";
          for (String[] r : node) {
              for (String t : r) {
                  s += t;
              }
          }
  
              if (!s.contains("-"))
              {
                  return true;
              }
  
              return false;
      }
  
  
      public int checkWin(String[][] gameState) {
          if (hasWon("X", gameState))
          {
              return 1;
          }
          else if (hasWon("O", gameState))
          {
              return 2;
          }
          else
          {
              return 0;
          }
      }
  
      public void copyGameState() {
          for (int i = 0; i &lt; cells.length; i++) {
              for (int j = 0; j &lt; cells[i].length; j++) {
                  node[i][j] = cells[i][j];
              }
          }
      }
  
  
      public static int[] getAvailableSpaces() {
          String s = "";
          for (int i = 0; i &lt; cells.length; i++) {
              for (int j = 0; j &lt; cells[i].length; j++) {
                  if (cells[i][j].equals("-"))
                      s += ((j * COLS) + i) + ", ";
              }
          }
          String[] split = s.split(", ");
  
          int[] availableSpaces = new int[split.length];
  
          for (int i = 0; i &lt; split.length; i++)
              availableSpaces[i] = Integer.parseInt(split[i]);
  
          return availableSpaces;
      }
  
      public void resetSpace(int space) {
          int col = space % COLS;
          int rows = space / COLS;
          cells[rows][col] = "-";
      }
  
  
      public int miniMax(int playerNum)
      {
          //printArrays();
          int victor = checkWin(cells); // returns 0 if game is ongoing, 1 for p1, 2 for p2, 3 for tie.
          if(victor != 0) //game over
              {
              return Score(victor);
              }
  
          if(playerNum == 2) //AI
          {
              int bestVal = Integer.MAX_VALUE;
              int bestSpot = 0;
              for(int i = 0; i &lt; cells.length; i++)
                      for (int j = 0; j &lt; cells[i].length; j++)
                      {
                          if(!cells[i][j].equals("-"))
                              continue;
                          cells[i][j] = getSymbol(playerNum);
                          int value = miniMax(1); 
                          if(value &lt; bestVal)
                          {
                              bestVal = value;
                              bestSpot = (j * COLS) + i;
                              System.out.println("Best Value: " + bestVal);
                              System.out.println("Best Spot: " + bestSpot);
                          }
  
                          cells[i][j] = "-";
                      }
              return bestSpot;
          }
          else
          {
              int bestVal = Integer.MIN_VALUE;
              int bestSpot = 0;
              for(int i = 0; i &lt; cells.length; i++)
                      for(int j = 0; j &lt; cells[i].length; j++)
                      {
                          if(!cells[i][j].equals("-"))
                              continue;
                          cells[i][j] = getSymbol(playerNum);
                          int value = miniMax(2); 
                          if(value &gt; bestVal)
                          {
                              bestVal = value;
                              bestSpot = (j * COLS) + i;
                          }
                          cells[i][j] = "-";
                      }
              return bestSpot;
          }
      }
  
      private int Score(int gameState)
      {
          if(gameState ==2) //O wins.
              return 10;
          else if(gameState==1) //X wins
              return -10;
          return 0;
      }
  
      public void printArrays() {
          String s = "cells: ";
          String l = "node: ";
          for (int i = 0; i &lt; cells.length; i++) {
              for (int j = 0; j &lt;cells[i].length; j++) {
                  s += cells[i][j];
                  l += node[i][j];
              }
          }
          System.out.println(s);
          System.out.println(l);
      }
  }
  </code></pre>