Tic-Tac-Toe minmax AI

[Michael Kerekes]

I have implemented a Tic-Toe-Toe AI using the generalized minmax algorithm that we talked about at the meetup.  I can do a show-and-tell on it at our next meetup.  If anyone want to reply with an improved version that would be nice.  I didn't do the symmetry optimization and the ABish testing is minimal.

It's on github.  Look at game.hs first it has fairly good comments.  Then tictactoe.hs.

You won't be able to run it since I use my custom Prelude which isn't publicly available.

The AI is basically instantaneous.  The algorithm will work for 4x4 boards. But in it's current incarnation will run out of memory.  There are comments at the end of game.hs on how to make it use less memory.

I am open to suggestions on how it can be improved.

[Bryan Grounds]

This is great - thanks for sharing!

I love the use of integers and bitmasks for an efficient board representation. How would you represent an arbitrarily large gamestate with this approach? Would you use a list of integers, or maybe reach for a bitstring abstraction?

I also like how you've defined the `moves` method to return the game's outcome if there are no moves left. I think that's a nice simplification, and a tighter abstraction than having separate `moves` and `result` methods.

By the way, after your comment in our last meeting about Map being an inefficient cache, I tried using a HashMap instead. Execution times for the caching versions of minimax were more than halved with that change alone!

The best version now solves 3x3 in ~18 ms, and 4x4 in 6-7 minutes.

I also simplified my Game type class and removed the monadic constraints.

Code changes and updated benchmarks are public here:

https://gitlab.com/bagrounds/tic-tac-toe

Thanks for all of the feedback!

[Michael Kerekes]

| Would you use a list of integers, or maybe reach for a bitstring abstraction?  

You guessed it, a list of integers, wrapped up as some sort of bitstring abstraction.  In fact, you could just use Integer.  It is an instance of the Bits class.

| I also simplified my Game type class and removed the monadic constraints.  

It's always feels good to make code better as you learn more about your problem.  I don't worry too much about getting things exactly right in the first pass.

--
You received this message because you are subscribed to the Google Groups "SeaHUG" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seattlehaskel...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/seattlehaskell/d6fc810c-0c18-46e4-92d9-8b789fe3d584%40googlegroups.com.

[dav...@gmail.com]

Here's a version of Mike's MinMax code that compiles in the stack environment using the standard Prelude.  I'm interested in the MinMax algorithm and wanted to be able to play with the code to better understand it.   From here on out I will (probably) continue to make changes but this version compiles under stack and (hopefully) preserves the spirit of the original with minimal changes.

[Michael Kerekes]

Nice.  Thanks Dave.

--

You received this message because you are subscribed to the Google Groups "SeaHUG" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seattlehaskel...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/seattlehaskell/07d6c6aa-ea57-4129-a659-a79c12d7c2b6%40googlegroups.com.

[Dave Compton]

For my own better understanding of the MinMax algorithm (and practice at reading and writing Haskell) I've been playing with Mike's MinMax code.  Here's my latest version :  https://github.com/dc25/MinMax

In this version the minmax library generates no IO output.   A Main.hs file in The "app" directory compiles using stack and will step through a game and print out the intermediate results.  A Main.hs file in the "web" directory can be compiled using ghcjs and will display an interactive game in the brower using the same minmax library.   You can play against the algorithm here: https://dc25.github.io/MinMax/

I would be grateful for any feedback.

- Dave

On Friday, October 25, 2019 at 3:33:44 PM UTC-7, michael.kerekes wrote:

Nice.  Thanks Dave.

On Fri, Oct 25, 2019 at 3:15 PM <dav...@gmail.com> wrote:

Here's a version of Mike's MinMax code that compiles in the stack environment using the standard Prelude.  I'm interested in the MinMax algorithm and wanted to be able to play with the code to better understand it.   From here on out I will (probably) continue to make changes but this version compiles under stack and (hopefully) preserves the spirit of the original with minimal changes.

On Monday, October 21, 2019 at 1:26:16 PM UTC-7, michael.kerekes wrote:

I have implemented a Tic-Toe-Toe AI using the generalized minmax algorithm that we talked about at the meetup.  I can do a show-and-tell on it at our next meetup.  If anyone want to reply with an improved version that would be nice.  I didn't do the symmetry optimization and the ABish testing is minimal.

It's on github.  Look at game.hs first it has fairly good comments.  Then tictactoe.hs.

You won't be able to run it since I use my custom Prelude which isn't publicly available.

The AI is basically instantaneous.  The algorithm will work for 4x4 boards. But in it's current incarnation will run out of memory.  There are comments at the end of game.hs on how to make it use less memory.

I am open to suggestions on how it can be improved.

--
You received this message because you are subscribed to the Google Groups "SeaHUG" group.

To unsubscribe from this group and stop receiving emails from it, send an email to seattle...@googlegroups.com.