I went to a board game night with a buddy in Sunnyvale and had a good time playing this stupid simple game called "Don't L.L.A.M.A."
While playing it I couldn't stop thinking about writing an engine / bot.
The page is here. You can sit down against any of the bots, watch them play each other with every hand shown, run hundreds of games between them in the arena, read what each bot does, and write your own bot in the browser and seat it at the table.
I had a python game engine built within an hour or two. It could play random legal moves. I later rewrote it in C++ for the speed. I thought I'd use the C++ engine to generate a bunch of training examples and use those examples later on to train a model in python.
But then I thought it'd be even more fun to expose the C++ engine in the browser by exporting a wasm binary with bindings that allow the game to be manipulated with javascript.
I then created a simple bot loosely modeled how I play L.L.A.M.A. In a 4-player game against 3 other bots that play randomly it wins 850/1000 games or so. This isn't too impressive though.
I've tried several ML strategies.
Reinforcement Learning is the obvious approach. I tossed some code together early on but found it hard to get something that could beat anything other than random-move bots.
After those early attempts, I went on to make many modifications to the core engine and framework and fixed some bugs.
I also came up with another ML-based bot that uses simulation to "try" out each legal move then play 5000 games with a random policy from that point. I used whichever action had the most wins to create a label to go with the state the bot initially saw. The bot with this policy would win against other simpler bots 60% of the time in a 4-player game. I used these labels to create a simple supervised classification model to predict that label given the state. This model correctly picked the best action 72% of the time. All this being said, I found it difficult to get good results in actual games. I'll return to this idea later.
Fixing all those mistakes and seeing some hope in the previous approach made me curious to try the RL approach again. Eventually I was able to make a bot that quickly becomes significantly better than the basic heuristic bots. The [messy] code for this is here.
Some things I learned is that a model can become overly trained on a particular player order or bot setup. In real life this is also true. If my turn is always right before a player who does irrational moves, I'd play differently (probably more conservatively) than someone who behaves more predictably. With this information I made it a point to constantly vary the competitors' policies and overall player order for each game played in the training.
Anyways, I'm kind of burnt out on this at the moment. I may return to it again in the future. It's a great way to learn!
The engine had a scoring bug the whole time: when a player went out, every other player who had not quit was given a token back instead of being charged for the cards in their hand. The real rules charge everyone still holding cards, quit or not. Every number above was measured on that wrong game. After fixing it (and a pile of smaller bugs), the RL bot turned out to have learned to never quit and is now the weakest of the real bots, winning about 12% of 4-player games against three copies of the simple heuristic bot.
The engine now also has a proper search bot, JosephSearchBotV1 on the page.
For every decision it deals the cards it cannot see at random a few hundred
times, plays each legal move out with a rule based policy, scores the round
with the real rules, and picks the move with the best average chance of
winning the game. It never peeks at hidden cards. In 4-player games it wins
about 52% against three copies of my original heuristic bot and 47% against
the supervised bot plus two heuristic bots, where 25% is an even share. The
rule based rollout policy is available on its own as JosephHeuristicBotV1
and is a decent bot by itself (37% against three of the original heuristic
bots). Both run inside the wasm engine, so they play against any bot you write
on the page.
JosephSearchBotV2 adds opponent inference: it discounts sampled deals in
which another player holds a card they declined to play, or quit with an
expensive hand. It is a couple of points stronger than V1 against the simpler
bots and even with it otherwise.
JosephSearchBotV3 swaps the hand tuned win estimate for one fitted to
240,000 rounds of arena self play, so it knows what a lead is worth at each
stage of the game. It wins about 36% of 4-player games against three of the
rule based bots, a few points more than V2.
JosephSearchBotV4 searches a tree over the rest of the round (information
set Monte Carlo tree search) instead of a single playout per move. It plays
as well as V3 but no better, which says lookahead through its own later
decisions is worth little in this game.
JosephNeuralBotV1 is the search bot distilled into a small neural network
trained on 1.2 million of its decisions, using only what is visible from the
seat. It decides in microseconds and plays about as well as the first search
bot: 30% against three rule based bots and 46% against three copies of my
original bot. JosephSearchBotV5 runs the search with that network in place
of the rule based rollout policy and plays even with V3.
JosephNeuralBotV2 is the one to play against. The search bots are strong
but slow, so this is the search bot distilled again, properly: a network with
two hidden layers trained on 6.7 million of the search bot's decisions to
match its value for every legal move rather than just its choice, and given
the round's public history as input so it can tell which cards the other
players are unlikely to hold. It decides in microseconds and plays nearly as
well as the search bot it learned from, ahead of it at some tables: across a
gauntlet of ten tables of two to six players against every other bot it
wins 1.70 times its even share of games, against 1.45 for the first
network and 1.71 for the search bot.