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.
Adjustable parameters include:
- 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:
advancedturn(currentturn) => next turn's id
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.
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.
[Please log in to post a comment]