3

Cart #nisiwojeho-2 | 2022-06-15 | Code ▽ | License: CC4-BY-NC-SA
3

Been working on a generic monte-carlo tree search algorithm, which can be supplied w the rules for any turn-based game (even games w/ randomness!) and, after as much time as you like (given pico8's memory), turn out the best move it can think of.

• How intelligent the ai is (how many times it's allowed to explore the state tree)
• How much time the ai has to explore the state tree
• How adventurous the ai is (how likely it is to explore paths that might not immediately show promise)

The ai assumes that your game is structured as such
a gamestate (or "board") is a single table representing a possible state of the game
a board also has a "turn id", representing whose turn it is at that state

The ai just needs for the game to have the following functions:

copyboard(board) => copy of the board
allpossiblemoves(board) => table w all possible moves in a given state
result(board,move) => a board w the move done on it
rate(board,player) => a rating of how good the board is for that player (turn id)
winner(board) => returns the turn id of the winner, or nil if there are no winners
isterminal(board) => bool - is the game over?

Once you have those written for your game, you can just call bestmove(board). It will search 324 times through the state space using a Monte Carlo Tree Search technique in order to find the best move it can. 324 is about as many times as I could get before pico8 ran out of memory. It's not really enough for a greeaat Monte Carlo exploration, but it's enough for a moderately competent ai :) In the future, I might look for ways to store the board state in a smaller package. (right now it's 64 strings lol)

Plugged it into a game of connect 4 to see how it works :)

Right now it's a little bit messy, but will be polishing the algorithm soon and sharing it on the forums.

P#113193 2022-06-15 17:21 ( Edited 2022-06-15 17:51)

1

I don't think connect 4 is the best game to use this with, at least not without a failsafe to have the ai always block a 1-turn win. Most of the strategy is setting up traps that allow you to win if the opponent makes a specific play, so the ai being open to any of the moves available makes it only a matter of time before the ai does the thing that lets the player win.

Also, in my first game against the ai, I played center and it responded in the corner. I'll admit that I'm not the best connect 4 player, but that's the most blatantly bad opening move I can think of.

P#113195 2022-06-15 17:43
:: dw817

Yeah, the AI is not very good, @ohhcurtains. I won pretty easily, straight horizontal line in minimal moves. The code for the computer's brain needs work.

P#113216 2022-06-16 03:46