Answers.Body: <p>I suspect that you'll have to remove this code:</p>
  
  <pre><code>    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(BLUE_WIN, movePlayed);
      }
  </code></pre>
  
  <p>from the <code>max()</code> method, and remove this code:</p>
  
  <pre><code>    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(RED_WIN, movePlayed);
      }
  </code></pre>
  
  <p>from the <code>min()</code> method.</p>
  
  <hr>
  
  <p>In the first case, you're checking whether the move that RED just made was a winning move. You don't want to check there if it was a winning move from BLUE, because it wasn't BLUE who just made that move; it was red. The same counts the other way around in the second case.</p>
  
  <hr>
  
  <p>Additionally, the initial call into the algorithm seems overly complicated. I am not sure what the intended use of the <code>tmp</code> variable there is, or that <code>dropToColumn()</code> call. I would rewrite it to be more like:</p>
  
  <pre><code>@Override
  public int nextMove(C4Game game) {
      C4Field field = game.getCurrentField();
  
      NextMove mv = null;
  
      if(game.getPlayerToMove().getSymbol().equals(C4Symbol.BLUE)){
          mv = max(field, -1);
      }
      else{
          mv = min(field, -1);
      }
  
      return mv.getMoveIndex();
  }
  </code></pre>
  
  <p>This will require an adaptation of the <code>max()</code> and <code>min()</code> methods such that they skip the whole checking-for-wins thing if the previous <code>movePlayed</code> equals <code>-1</code>.</p>
  
  <p>With the code you currently have there, you do not perform a minimax search for the optimal move in the current game state; instead you first arbitrarily modify the current game state using that <code>tmp.dropToColumn()</code> call, and perform the minimax search in that arbitrarily modified game state. The optimal move to play in such an arbitrarily-modified game state will tend not to be the optimal move in the game state that you really are in.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T10:46:18.527Z
Answers.Text: Removing those lines resulted in exactly the same behaviour as before.
Answers.UserDisplayName: wesleyy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T11:47:06.713Z
Answers.Text: @wesleyy I'm not seeing any other mistakes right now... (what I wrote in my answer may or may not be a true mistake, depending on how isWinningMove() is implemented). How sure are you that it actually is playing poorly? Can you easily defeat an agent using this algorithm yourself? How do the games end if you let this agent play itself? If they always end in draws, it may mean that a game of that board size is always a draw under perfect play, and then you may see strange moves being played as long as they don't lead to direct losses.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T11:56:37.370Z
Answers.Text: Yes, I can easily win against it. Because it always plays the leftmost first move, at index 0. Then i play index 2, it plays 0 again. I block on 0 (so it doesn't connect 3 in a column), it then plays index 1 making it straight-forward for me to also play index 1 and have the winning diagonal. If it plays itself, the 1st player always win, but very soon. Only about half of the board gets filled.
Answers.UserDisplayName: wesleyy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T12:00:29.487Z
Answers.Text: Yes. RED_WIN = -1; DRAW = 0; BLUE_WIN = +1;
Answers.UserDisplayName: wesleyy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T12:26:25.347Z
Answers.Text: Please see my edit.
Answers.UserDisplayName: wesleyy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T12:38:45.007Z
Answers.Text: @wesleyy Yes, the new code you edited into the question looks... suspect. Can't tell for sure since I don't understand what `dropToColumn()` does. I edited into my answer how I would have written that function
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T12:49:13.170Z
Answers.Text: Yeah, sorry, "dropToColumn" is actually "playMove", I forgot to rename it when I pasted it. Anyway, your edit seemed to have solved the problem on a first glance. Let me test it a bit more before I accept your answer!
Answers.UserDisplayName: wesleyy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T12:55:43.237Z
Answers.Text: @wesleyy Also added an explanation of why the code you originally had likely wouldn't work correctly here (see final paragraph)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-23T10:37:35.337Z
Answers.LastActivityDate: 2018-09-23T12:55:11.693Z
Answers.LastEditDate: 2018-09-23T12:55:11.693Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I'm trying to implement an algorithm that would choose the optimal next move for the game of Connect 4. As I just want to make sure that the basic <strong>minimax</strong> works correctly, I am actually testing it like a Connect 3 on a 4x4 field. This way I don't need the alpha-beta pruning, and it's more obvious when the algorithm makes a stupid move.</p>
  <p>The problem is that the algorithm <strong>always</strong> starts the game with the leftmost move, and also during the game it's just very stupid. It doesn't see the best moves.</p>
  <p>I have thoroughly tested methods <code>makeMove()</code>, <code>undoMove()</code>,  <code>getAvailableColumns()</code>, <code>isWinningMove()</code> and <code>isLastSpot()</code> so I am absolutely <strong>sure</strong> that the problem is not there.</p>
  <p>Here is my algorithm.</p>
  <p><strong>NextMove.java</strong></p>
  <pre><code>private static class NextMove {
      final int evaluation;
      final int moveIndex;
  
      public NextMove(int eval, int moveIndex) {
          this.evaluation = eval;
          this.moveIndex = moveIndex;
      }
  
      int getEvaluation() {
          return evaluation;
      }
  
      public int getMoveIndex() {
          return moveIndex;
      }
  }
  </code></pre>
  <p><strong>The Algorithm</strong></p>
  <pre><code>private static NextMove max(C4Field field, int movePlayed) {
      // moveIndex previously validated
      
      // 1) check if moveIndex is a final move to make on a given field
      field.undoMove(movePlayed);
      
      // check
      if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(BLUE_WIN, movePlayed);
      }
      if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(RED_WIN, movePlayed);
      }
      if (field.isLastSpot()) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(DRAW, movePlayed);
      }
      
      field.playMove(movePlayed, C4Symbol.RED);
      
      // 2) moveIndex is not a final move
      // --&gt; try all possible next moves
      final List&lt;Integer&gt; possibleMoves = field.getAvailableColumns();
      int bestEval = Integer.MIN_VALUE;
      int bestMove = 0;
      for (int moveIndex : possibleMoves) {           
          field.playMove(moveIndex, C4Symbol.BLUE);
          
          final int currentEval = min(field, moveIndex).getEvaluation();
          if (currentEval &gt; bestEval) {
              bestEval = currentEval;
              bestMove = moveIndex;
          }
  
          field.undoMove(moveIndex);
      }
      
      return new NextMove(bestEval, bestMove);
  }
  
  private static NextMove min(C4Field field, int movePlayed) {
      // moveIndex previously validated
      
      // 1) check if moveIndex is a final move to make on a given field
      field.undoMove(movePlayed);
      
      // check
      if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(BLUE_WIN, movePlayed);
      }
      if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(RED_WIN, movePlayed);
      }
      if (field.isLastSpot()) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(DRAW, movePlayed);
      }
      
      field.playMove(movePlayed, C4Symbol.BLUE);
      
      // 2) moveIndex is not a final move
      // --&gt; try all other moves
      final List&lt;Integer&gt; possibleMoves = field.getAvailableColumns();
      int bestEval = Integer.MAX_VALUE;
      int bestMove = 0;
      for (int moveIndex : possibleMoves) {
          field.playMove(moveIndex, C4Symbol.RED);
          
          final int currentEval = max(field, moveIndex).getEvaluation();
          if (currentEval &lt; bestEval) {
              bestEval = currentEval;
              bestMove = moveIndex;
          }
          
          field.undoMove(moveIndex);
      }
      
      return new NextMove(bestEval, bestMove);
  }
  </code></pre>
  <p>The idea is that the algorithm takes in the arguments of a <code>currentField</code> and the <code>lastPlayedMove</code>. Then it checks if the last move somehow finished the game. If it did, I just return that move, and otherwise I go in-depth with the subsequent moves.</p>
  <p>Blue player is MAX, red player is MIN.</p>
  <p>In each step I first undo the last move, because it's easier to check if the &quot;next&quot; move will finish the game, than check if the current field is finished (this would require to analyze for all possible winning options in the field). After I check, I just redo the move.</p>
  <p>From some reason this doesn't work. I am stuck with that for days! I have no idea what's wrong... Any help greatly appreciated!</p>
  <h2>EDIT</h2>
  <p>I'm adding the code how I'm invoking the algorithm.</p>
  <pre><code>@Override
  public int nextMove(C4Game game) {
      C4Field field = game.getCurrentField();
      C4Field tmp = C4Field.copyField(field);
  
      int moveIndex = tmp.getAvailableColumns().get(0);
      final C4Symbol symbol = game.getPlayerToMove().getSymbol().equals(C4Symbol.BLUE) ? C4Symbol.RED : C4Symbol.BLUE;
      tmp.dropToColumn(moveIndex, symbol);
  
      NextMove mv = symbol
              .equals(C4Symbol.BLUE) ? 
                      max(tmp, moveIndex) : 
                          min(tmp, moveIndex);
  
                      int move = mv.getMoveIndex();
                      return move;
  }
  </code></pre>
  
Tags: <game-ai><minimax><java>
Title: Connect 4 minimax does not make the best move
UserDisplayName: wesleyy
ThreadText: # Connect 4 minimax does not make the best move
  
  (Asked by: username_0 on 2018-09-23)
  
  I'm trying to implement an algorithm that would choose the optimal next move for the game of Connect 4. As I just want to make sure that the basic **minimax** works correctly, I am actually testing it like a Connect 3 on a 4x4 field. This way I don't need the alpha-beta pruning, and it's more obvious when the algorithm makes a stupid move.
  
  The problem is that the algorithm **always** starts the game with the leftmost move, and also during the game it's just very stupid. It doesn't see the best moves.
  
  I have thoroughly tested methods `makeMove()`, `undoMove()`, `getAvailableColumns()`, `isWinningMove()` and `isLastSpot()` so I am absolutely **sure** that the problem is not there.
  
  Here is my algorithm.
  
  **NextMove.java**
  
  ```
  private static class NextMove {
      final int evaluation;
      final int moveIndex;
  
      public NextMove(int eval, int moveIndex) {
          this.evaluation = eval;
          this.moveIndex = moveIndex;
      }
  
      int getEvaluation() {
          return evaluation;
      }
  
      public int getMoveIndex() {
          return moveIndex;
      }
  }
  
  ```
  
  **The Algorithm**
  
  ```
  private static NextMove max(C4Field field, int movePlayed) {
      // moveIndex previously validated
      
      // 1) check if moveIndex is a final move to make on a given field
      field.undoMove(movePlayed);
      
      // check
      if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(BLUE_WIN, movePlayed);
      }
      if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(RED_WIN, movePlayed);
      }
      if (field.isLastSpot()) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(DRAW, movePlayed);
      }
      
      field.playMove(movePlayed, C4Symbol.RED);
      
      // 2) moveIndex is not a final move
      // --> try all possible next moves
      final List<Integer> possibleMoves = field.getAvailableColumns();
      int bestEval = Integer.MIN_VALUE;
      int bestMove = 0;
      for (int moveIndex : possibleMoves) {           
          field.playMove(moveIndex, C4Symbol.BLUE);
          
          final int currentEval = min(field, moveIndex).getEvaluation();
          if (currentEval > bestEval) {
              bestEval = currentEval;
              bestMove = moveIndex;
          }
  
          field.undoMove(moveIndex);
      }
      
      return new NextMove(bestEval, bestMove);
  }
  
  private static NextMove min(C4Field field, int movePlayed) {
      // moveIndex previously validated
      
      // 1) check if moveIndex is a final move to make on a given field
      field.undoMove(movePlayed);
      
      // check
      if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(BLUE_WIN, movePlayed);
      }
      if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(RED_WIN, movePlayed);
      }
      if (field.isLastSpot()) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(DRAW, movePlayed);
      }
      
      field.playMove(movePlayed, C4Symbol.BLUE);
      
      // 2) moveIndex is not a final move
      // --> try all other moves
      final List<Integer> possibleMoves = field.getAvailableColumns();
      int bestEval = Integer.MAX_VALUE;
      int bestMove = 0;
      for (int moveIndex : possibleMoves) {
          field.playMove(moveIndex, C4Symbol.RED);
          
          final int currentEval = max(field, moveIndex).getEvaluation();
          if (currentEval < bestEval) {
              bestEval = currentEval;
              bestMove = moveIndex;
          }
          
          field.undoMove(moveIndex);
      }
      
      return new NextMove(bestEval, bestMove);
  }
  
  ```
  
  The idea is that the algorithm takes in the arguments of a `currentField` and the `lastPlayedMove`. Then it checks if the last move somehow finished the game. If it did, I just return that move, and otherwise I go in-depth with the subsequent moves.
  
  Blue player is MAX, red player is MIN.
  
  In each step I first undo the last move, because it's easier to check if the "next" move will finish the game, than check if the current field is finished (this would require to analyze for all possible winning options in the field). After I check, I just redo the move.
  
  From some reason this doesn't work. I am stuck with that for days! I have no idea what's wrong... Any help greatly appreciated!
  
  ## EDIT
  
  I'm adding the code how I'm invoking the algorithm.
  
  ```
  @Override
  public int nextMove(C4Game game) {
      C4Field field = game.getCurrentField();
      C4Field tmp = C4Field.copyField(field);
  
      int moveIndex = tmp.getAvailableColumns().get(0);
      final C4Symbol symbol = game.getPlayerToMove().getSymbol().equals(C4Symbol.BLUE) ? C4Symbol.RED : C4Symbol.BLUE;
      tmp.dropToColumn(moveIndex, symbol);
  
      NextMove mv = symbol
              .equals(C4Symbol.BLUE) ? 
                      max(tmp, moveIndex) : 
                          min(tmp, moveIndex);
  
                      int move = mv.getMoveIndex();
                      return move;
  }
  
  ```
  
  **Tags:** game-ai, minimax, java
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-09-23. Score: 3 | Accepted answer
  
  I suspect that you'll have to remove this code:
  
  ```
      if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
          field.playMove(movePlayed, C4Symbol.RED);
          return new NextMove(BLUE_WIN, movePlayed);
      }
  
  ```
  
  from the `max()` method, and remove this code:
  
  ```
      if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
          field.playMove(movePlayed, C4Symbol.BLUE);
          return new NextMove(RED_WIN, movePlayed);
      }
  
  ```
  
  from the `min()` method.
  
  ---
  
  In the first case, you're checking whether the move that RED just made was a winning move. You don't want to check there if it was a winning move from BLUE, because it wasn't BLUE who just made that move; it was red. The same counts the other way around in the second case.
  
  ---
  
  Additionally, the initial call into the algorithm seems overly complicated. I am not sure what the intended use of the `tmp` variable there is, or that `dropToColumn()` call. I would rewrite it to be more like:
  
  ```
  @Override
  public int nextMove(C4Game game) {
      C4Field field = game.getCurrentField();
  
      NextMove mv = null;
  
      if(game.getPlayerToMove().getSymbol().equals(C4Symbol.BLUE)){
          mv = max(field, -1);
      }
      else{
          mv = min(field, -1);
      }
  
      return mv.getMoveIndex();
  }
  
  ```
  
  This will require an adaptation of the `max()` and `min()` methods such that they skip the whole checking-for-wins thing if the previous `movePlayed` equals `-1`.
  
  With the code you currently have there, you do not perform a minimax search for the optimal move in the current game state; instead you first arbitrarily modify the current game state using that `tmp.dropToColumn()` call, and perform the minimax search in that arbitrarily modified game state. The optimal move to play in such an arbitrarily-modified game state will tend not to be the optimal move in the game state that you really are in.
  
  > **Comments:**
  > **username_0**: Removing those lines resulted in exactly the same behaviour as before.  
  > **username_1**: @username_0 I'm not seeing any other mistakes right now... (what I wrote in my answer may or may not be a true mistake, depending on how isWinningMove() is implemented). How sure are you that it actually is playing poorly? Can you easily defeat an agent using this algorithm yourself? How do the games end if you let this agent play itself? If they always end in draws, it may mean that a game of that board size is always a draw under perfect play, and then you may see strange moves being played as long as they don't lead to direct losses.  
  > **username_0**: Yes, I can easily win against it. Because it always plays the leftmost first move, at index 0. Then i play index 2, it plays 0 again. I block on 0 (so it doesn't connect 3 in a column), it then plays index 1 making it straight-forward for me to also play index 1 and have the winning diagonal. If it plays itself, the 1st player always win, but very soon. Only about half of the board gets filled.  
  > **username_0**: Yes. RED_WIN = -1; DRAW = 0; BLUE_WIN = +1;  
  > **username_0**: Please see my edit.  
  > **username_1**: @username_0 Yes, the new code you edited into the question looks... suspect. Can't tell for sure since I don't understand what `dropToColumn()` does. I edited into my answer how I would have written that function  
  > **username_0**: Yeah, sorry, "dropToColumn" is actually "playMove", I forgot to rename it when I pasted it. Anyway, your edit seemed to have solved the problem on a first glance. Let me test it a bit more before I accept your answer!  
  > **username_1**: @username_0 Also added an explanation of why the code you originally had likely wouldn't work correctly here (see final paragraph)  
  
  ---
  
  