Improve the minimax AI

[tannerkrewson]

@kevers429 found that the slowest part of the minimax AI is not the minimax itself, but either the tree/noded building process, or the board scanning that happens at each node. Improving these could make the AI run faster and more efficiently.

The scoring algorithm itself could also be tweaked to help the AI better understand if a board state is good or bad.

[kevin-shannon]

the tree unnecessarily gets recomputed each turn there is probably a clever way to reuse the part of the tree that the game path goes down. Also improvements could be made by searching deeper through likely moves, giving up on unpromising move sets, and exploiting symmetry.

[tannerkrewson]

81bd3338539c9150342e2e4acd62bd36955f4289

[tannerkrewson]

when red goes first against AI and drops in 4, 5, 5, then 6, blue makes these moves:

[tannerkrewson]

before 9b9947a018f1783f5be7b3f1315aecb0c218b778, the AI would copy the 2d array of the board 100,000+ times every move. I have replaced the copying with backtracking. Now, only one copy of the board is made per move. this showed marginal time improvements in my limited test:

while testing, I discovered https://github.com/kevers429/connect4/issues/23 which happened before and after these changes were made

[tannerkrewson]

🎉 good progress with 06216ebe23786fe8ad270621bf6daf658f240f8f. only checks for a win based on the previously dropped chip instead of checking the whole board.

[tannerkrewson]

I added a basic lookup table for the score in 40812d9de5060d34e33d448337931c48a5aca707. it seems to have slowed it down. looking into a structure other than string keys with the built in map object to speed it up.

but, couldn't this significantly speed up higher depths late game?

[tannerkrewson]

I prototyped a tree that stores scores. array-tree branch It is structured as 42 nested arrays. If a slot is empty, nest on index 0, red = 1, and blue = 2. For example for a 1x4 board with a score of 32 and chips in this order: empty, red, blue, empty, the array would look like: [[null,[null,null,[32,null,null],null],null,null]. You could add more scores to this same structure using the same pattern.

Buuut it seems to be a bit slower:

I've put in a separate branch because it is slower and more complicated to understand. We might just let it go stale and see if @kevers429 has any ideas.

[tannerkrewson]

We had a 1 second move delay on the AI to prevent it from making its move super fast right after the local player drops their chip. However, our implementation would add 1 second to execution no matter how long the AI took thinking about the move. So, if it took 3 seconds to think about the move, it would actually be 4 seconds until it dropped, because it waited 1 second before it started thinking.

I got rid of this removing the delay, doing the thinking right away, and checking to see if the thinking took longer than 1 second. If it took longer than 1 second, the AI now makes the move right away. If it took less than 1 second, it adds the difference between how long it already took and 1 second, and sets it as the delay.

Both of these scenarios are clear in the screenshots 😄

Before:

After: