AI not stopping win in one move

Rulerofzeworld commented 3 years ago

Code

from easyAI import TwoPlayerGame, Human_Player, AI_Player, Negamax
from easyAI.games import ConnectFour

ai = Negamax(8)
game = ConnectFour( [  AI_Player( ai ), Human_Player() ] )
game.play()

Game

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

Move #1: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .

Player 2 what do you play ? 3

Move #2: player 2 plays 3 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . X . . .

Move #3: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .
O . . X . . .

Player 2 what do you play ? 2

Move #4: player 2 plays 2 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .
O . X X . . .

Move #5: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .
O . . . . . .
O . X X . . .

Player 2 what do you play ? 0

Move #6: player 2 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
X . . . . . .
O . . . . . .
O . . . . . .
O . X X . . .

Move #7: player 1 plays 1 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
X . . . . . .
O . . . . . .
O . . . . . .
O O X X . . .

Player 2 what do you play ? 2

Move #8: player 2 plays 2 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
X . . . . . .
O . . . . . .
O . X . . . .
O O X X . . .

Move #9: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . . . . . .
O . X . . . .
O O X X . . .

Player 2 what do you play ? 3

Move #10: player 2 plays 3 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . . . . . .
O . X X . . .
O O X X . . .

Move #11: player 1 plays 2 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . O . . . .
O . X X . . .
O O X X . . .

Player 2 what do you play ? 1

Move #12: player 2 plays 1 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . O . . . .
O X X X . . .
O O X X . . .

Move #13: player 1 plays 3 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . O O . . .
O X X X . . .
O O X X . . .

Player 2 what do you play ? 1

Move #14: player 2 plays 1 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O X O O . . .
O X X X . . .
O O X X . . .
>>>

Issue

The AI is setup to look 8 moves ahead, yet is unable to spot the win in one move to stop it.

Zulko commented 3 years ago

Thanks for reporting this. I believe I know what's up, I'll provide a fix in the next ~24h.

Zulko commented 3 years ago

So here's what's up:

In your example, it is not just a loss in one move, it is a desperate situation for the "0" (they will always lose if "X" plays perfectly).
A weakness of Negamax is that, it its standard form, it does not make any difference between a loss in one move and a loss in 4 moves, so when in a desperate situation, it will act randomly.
EasyAI has a tweak to improve this: there is a small penalty on the "depth" of an outcome, so that a loss in 5 turns is preferred to a loss in 1 turn, and a win in 1 turn is preferred over a win in 5 turns.
What your example is showing is that this tweak was buggy. I fixed it and added a test based on your example. Try upgrading EasyAI and let me know if that works for you.

Rulerofzeworld commented 3 years ago

Thanks for the great explanation! Just upgraded EasyAI and ran the same code.

>>> from easyAI import TwoPlayerGame, Human_Player, AI_Player, Negamax
>>> from easyAI.games import ConnectFour
>>> ai = Negamax(8)
>>> game = ConnectFour( [  AI_Player( ai ), Human_Player() ] )
>>> game.play()

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

Move #1: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .

Player 2 what do you play ? 3

Move #2: player 2 plays 3 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . X . . .

Move #3: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .
O . . X . . .

Player 2 what do you play ? 2

Move #4: player 2 plays 2 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .
O . X X . . .

Move #5: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
O . . . . . .
O . . . . . .
O . X X . . .

Player 2 what do you play ? 0

Move #6: player 2 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
X . . . . . .
O . . . . . .
O . . . . . .
O . X X . . .

Move #7: player 1 plays 1 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
X . . . . . .
O . . . . . .
O . . . . . .
O O X X . . .

Player 2 what do you play ? 2

Move #8: player 2 plays 2 :

0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
X . . . . . .
O . . . . . .
O . X . . . .
O O X X . . .

Move #9: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . . . . . .
O . X . . . .
O O X X . . .

Player 2 what do you play ? 3

Move #10: player 2 plays 3 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . . . . . .
O . X X . . .
O O X X . . .

Move #11: player 1 plays 5 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . . . . . .
O . X X . . .
O O X X . O .

Player 2 what do you play ? 2

Move #12: player 2 plays 2 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . . . . . .
O . X . . . .
O . X X . . .
O O X X . O .

Move #13: player 1 plays 2 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . O . . . .
O . X . . . .
O . X X . . .
O O X X . O .

Player 2 what do you play ? 4

Move #14: player 2 plays 4 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . O . . . .
O . X . . . .
O . X X . . .
O O X X X O .

Move #15: player 1 plays 4 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . O . . . .
O . X . . . .
O . X X O . .
O O X X X O .

Player 2 what do you play ? 3

Move #16: player 2 plays 3 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . O . . . .
O . X X . . .
O . X X O . .
O O X X X O .

Move #17: player 1 plays 3 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . O O . . .
O . X X . . .
O . X X O . .
O O X X X O .

Player 2 what do you play ? 1

Move #18: player 2 plays 1 :

0 1 2 3 4 5 6
-------------
. . . . . . .
O . . . . . .
X . O O . . .
O . X X . . .
O X X X O . .
O O X X X O .

Move #19: player 1 plays 0 :

0 1 2 3 4 5 6
-------------
O . . . . . .
O . . . . . .
X . O O . . .
O . X X . . .
O X X X O . .
O O X X X O .

Player 2 what do you play ? 1

Move #20: player 2 plays 1 :

0 1 2 3 4 5 6
-------------
O . . . . . .
O . . . . . .
X . O O . . .
O X X X . . .
O X X X O . .
O O X X X O .

Definitely playing better now, still seems to give up at the end though. I assume that's just an issue with Negamax?

Zulko commented 3 years ago

Yeah I believe that's the limit. In that case the AI will lose next turn (if it blocks the current opportunity in column #1, it creates another opportunity in the same column, so it doesn't see any particular good in that move).

Rulerofzeworld commented 3 years ago

Alrighty thanks. Any recommendations for making it stronger before I close this?

Zulko commented 3 years ago

Not off the top of my head. Others have contributed alternatives to Negamax like SSS (see this file) maybe they'd work better for connect4?

Rulerofzeworld commented 3 years ago

Is there a way to make it randomly pick a top move if it sees them all as equal? Just tried testing SSS against Negamax, and it's just doing this...

0 1 2 3 4 5 6
-------------
X . . . . . .
O . . . . . .
X . . . . . .
O . . . . . .
X . . . . . .
O O . . . . .

Which makes it rather difficult to test which one is better.

JohnAD commented 3 years ago

Introducing even a small amount of randomness to the scoring can severely break a negamax algorithm. I don't recommend it.

Instead I recommend introducing short-term tactics into the scoring. So, instead of a score being strictly 100 or 0 to represent win/lose, make win=100, lose=-100, and anything else have a fractional value between -50.0 and +50.0 depending on the "state" of the board.

The challenge is coming up with the scoring rules for those fractional state values.

I've got a video where I demonstrate this with a Mancala game (Kalah rules) I was writing. I ended up resorting to a genetic algorithm to discover the best tactical rules. Hopefully with Connect 4 you don't have to go to such extreme measures.

But the motive was the same: Negamax was making unwise short term moves because it had no long term method of winning that it could see in the horizon. Adding the tactics changed all this and made much better gameplay.

If interested in seeing the video from the series: https://youtu.be/Y6P-_sTYQcM

Zulko / easyAI