negamax algorithm for a 3-in-a-row game on a 3x4 grid (rows x columns)

Question

I'm struggling with the negamax-algorithm for 3-in-a-row game on a 3x4 (rows x columns) grid. It is played like the well known 4-in-a-row, i.e. the pieces are dropped (NOT like TicTacToe). Let's call the players R and B. R had the first move, B's moves are controlled by negamax. Possible moves are 1, 2, 3, or 4. This the position in question which was reached after R: move 3 --> B: move 1 --> R: move 3:

  1   2   3   4

|   |   |   |   |

|   |   | R |   |

| B |   | R |   |

Now, in order to defend against move 3 by R, B has to play move 3 itself, but it refuses to do so. Instead it plays move 1 and the game is over after R's next move.

I spent the whole day looking for an error in my negamax implementation which works perfectly for a 3x3 grid, by the way, but I couldn't find any.

Then I started thinking: Another explanation for the behavior of the negamax-algorithm would be that B is lost in all variations no matter what, after R starts the game with move 3 on a 3x4-grid.

Can anybody refute this proposition or point me to a proof (which I would prefer ;-))?

Thanks, RSel

Answer 1

Proof that B3 loses as well:

B3: R(1,2,4)->R1; B(1,2,4)->B2 (loses), so B1; R(2,4)->R2 Loses, so R4; B(2,4)->B2 loses, so B4; R loses on either choice now ...so R1 will lose for R - so R won't choose it.

B3: R(1,2,4)->R2 loses since B2, so R won't choose it B3: R(1,2,4)->R4; B2 (forced); R2 (forced); B loses on R's next move

...so, B3 loses for B as well as B1...so B has lost in this situation.

EDIT: Just in case anyone is wondering about the other B options (2,4) at the end of "B3: R(1,2,4)->R1; B(1,2,4)->B2 (loses), so B1"...they are irrelevant, since as soon as Red chooses R1, this scenario shows that B (computer) can choose B1 and win. It doesn't really matter what happens with B's other choices - this choice will win, so Red can't choose R1 or he will lose.

Answer 2

It is, in fact, a won game from the start. And can be played through fairly easily by hand. I will assume that B avoids all of the 1-move wins for R, and will mark moves by color, and spot in the grid where the play happens.

1. R3,1
  ... B1,1  2. R3,2 B3,3  3. R4,1 B2,1  4. R2,2 (and R1,2 or R4,2 wins next)
  ... B2,1  2. R3,2 B3,3  3. R2,2 B2,3  4. R1,1 (and R1,2 or R1,3 wins next)
  ... B3,2  2. R2,1 (and R1,1 or R4,1 wins next)
  ... B4,1  2. R2,1 B1,1  3. R3,2 B3,3  4. R2,2 (and R1,2 or R4,2 wins next)

As for your algorithm, I'm going to suggest that you modify it to prefer wins over losses, and prefer distant losses over near losses. If you do that, it will "try harder" to avoid the inevitable loss.