search

Flutter-Buddies / tic_tac_no

Complex variants of tic-tac-toe game
MIT License
19 stars 10 forks source link

Smarter AI #3

Open slovnicki opened 3 years ago

joeyda3rd commented 3 years ago

Do you think just a legacy type AI where they just know the rules and value moves? Or do we want to try and ML train an AI?

slovnicki commented 3 years ago

I want to try ML at some point, but as I recall when I built this game last time, very simple "AI" who just knows how to win and, let's say, prefers to send you to already won grids to play in, is sufficient for being a non-trivial opponent.

I was thinking of 4 AIs:

First 3 can be made without any ML, just some ifs.

I'm gonna make the random AI these days, to show how it connects to the GameBloc, and then the other 2 can be made very similarly.

In essence, the AI class will have a function Square makeMove(Grid grid) that accepts the Grid representing the current state of the game board so any checks about the board can be done as pleased. It returns a chosen Square.

I think I'll also create some more branches for ai implementations

blopez24 commented 3 years ago

You may want to look into using a Minimax Algorithm. We can create 3 heuristic/evaluation functions for easy/medium/impossible AI levels.

I recently created this for connect four school project.

slovnicki commented 3 years ago

Thanks @blopez24 I think @dmorawetz had the similar idea so maybe we could start exploring the minimax soon. I made a ai/minimax branch for it so we can develop that there.

I'm just not sure will the minimax be able to handle that much branching, even with alpha-beta pruning.

blopez24 commented 3 years ago

I believe so.

blopez24 commented 3 years ago

It definitely needs a max_depth parameter. For my connect four project, it was a 6 x 7 board and I used minimax w/ alpha-beta pruning. It was able to go to a depth of 7 w/ a time of ~ 1 second. A depth of 6 was less than 1 seconds.

dmorawetz commented 3 years ago

@blopez24 I had exactly the same thought. What bugs me though is the restriction of the inner grid you are allowed to play next. It's not just a bigger grid, but an extra restriction. I can't wrap my head around this.