Boardgame.io: AI framework

[tolmar]

It's almost possible to write a generic AI using the existing framework, but there are two problems:

1. There's no way to enumerate legal moves. The ability to pass arbitrary arguments to the moves functions makes for some trouble here. Also the Tic Tac Toe example handles illegal moves by doing nothing, which is ergonomic, but the framework doesn't know it happened.
2. The framework doesn't know when a turn ends. The separate move + end turn calls are nice to make it easy to create games where one player's turn is composed of multiple logical moves, but "can I end turn" and "do I have to end turn" are questions only the caller can answer right now.

[tolmar]

The easiest way to enumerate would be to add an optional "enumerateMoves" function to the Game constructor but this puts a lot of work on the user's plate. I think some sort of "these are the ranges of legal values for the arguments" system would be easier, along with letting moves return errors for conditionally illegal moves. (Checking a move then returning an error is slower and thus a generic AI will be weaker with this approach, but I think that's acceptable. People shouldn't expect the world of a generic AI.)

I don't have any suggestions for the end of turn problem.

[tolmar]

For the actual AI portion I was thinking:

1. Do a generic tree search
2. Break ties randomly
3. Allow an optional heuristic function that scores the value of a non-winning board

It'll be embarrassingly bad if no heuristic function is specified, but still playable enough to debug a game. And there are relatively simple heuristics that can beat most humans at chess with a small search tree.

[nicolodavis]

An optional extra function to implement sounds quite reasonable:

Something like:

(gamestate) => list of next move types with arg ranges

perhaps?

In fact, given that END_TURN can just be treated like just another move, it would fit right in.

Example:

(G) => ({
  TAKE_CARD: [list of card ids in G.board],
  PLAY_CARD: [list of card ids in G.hand],
  END_TURN: []
})

The user could optionally provide weights for these as a heuristic (and doesn't need to even list all possible moves), and the AI code could do some reasonable things like making sure at least one move is made before END_TURN.

What do you think?

[nicolodavis]

This also takes care of the illegal move problem (the function that the user implements only returns legal moves).

[tolmar]

(G) => List of move types and arg ranges seems reasonable.

Since moves take an argument list, arg ranges need to be a list of lists. Chess example:

(G) => ({
MOVE_PIECE: [["a", 2, "a", 3], ["a", 2, "a", 4], ["b", 2, "b", 3] ... ]
})

Discarding illegal moves tends to be tricky and error prone, I think it's still worth adding that to the move function (it can be handy for clients too). That could be as simple as the move function returning falsey instead of a game state, or something else that allows an actual error message to come back. Regardless, the game would neglect to apply the move, and an AI wouldn't try that branch.

If illegal moves can be discarded, I can write the enumeration as:

enumerate: function(G) {
  return CrossProduct(["a", "b", "c", "d", "e", "f", "g", "h"], [1, 2, 3, 4, 5, 6, 7, 8], ["a", "b", "c", "d", "e", "f", "g", "h"], [1, 2, 3, 4, 5, 6, 7, 8]);
}

Which would perform slowly, but be very quick to prototype with.

[tolmar]

AI code could do some reasonable things like making sure at least one move is made before END_TURN.

Some games allow passing (Go), some require exactly one move (Chess), some allow a variable number of moves and passing (Magic), Arimaa* requires 1 to 4 moves.

*Not that the default AI for Arimaa would perform particularly well anyway, but as an example.

[nicolodavis]

re: handling illegal moves

The main reason that I chose to go the current route is because that's how Redux does it, and it's a paradigm that developers are familiar with (i.e. always returning state).

I'm not opposed to changing the paradigm if there is a good reason to do so, though. Let's give it a try. I'll take this as an action item for myself while you work on the enumeration function bit.

Some games allow passing (Go), some require exactly one move (Chess), some allow a variable number of moves and passing (Magic), Arimaa* requires 1 to 4 moves.

If we treat END_TURN as just another move, then this should be taken care of automatically. For example, END_TURN would be the only valid move after 4 moves of Arimaa. For games requiring exactly one move, END_TURN is not a valid move until another move has been made, and so on.

[nicolodavis]

I've started a branch ai that implements the invalid move logic we talked about.

Whenever you're ready, send me a PR to add stuff to this branch with the AI code.

[vdfdev]

Hi! I just heard about your project on HackerNews and it is very similar of what I was trying to do with this project: https://github.com/Felizardo/turnato http://turnato.com

Anyhow, after I launched the first chess and checkers on the website I saw that most people wanted single player option... So I was starting from scratch to have an API compatible with MDPs (Markov decision process) as I want to implement more complex board games that have non-deterministic outcomes (i.e. any game with dice).

So, besides adding legal moves, it would be great to add how much probability each action can lead to a new state. I just finished CS221, and I think this API for MDP would work very well for any board game.

Also, using this standard API will be very helpful for AI researchers trying to implement reinforcement learning algorithms, as we could provide rule implementation of several games in a standard fashion. Let me know what you think, I am more than happy to join efforts 👍

[tolmar]

I haven't had nearly the amount of free time I expected myself to have; feel free to steal any AI work from me.

I can think of two ways to handle random options:

• Make moves return a list of (weight, state) pairs. This changes the API in a way that's less ergonomic for other games, so you'd want to make it a flag (maybe by attaching a specific Symbol to the result?). It's still not the most natural way to express things even for games with random.
• Define a custom randInt(low, high) function that behaves normally when run as a game but gets redefined as "re-run this function with every possible value" when run in simulation. This requires that games are written with a specific random call, but otherwise is more natural. (Also, the code to actually make this work is gross.)

[justrag]

How about adding support for move-validating function, shared between server and client? Proposed move as an argument, and the {legal: false, text: "Why you cannot make this move"} as a result. This way you can use it for the UI, and blocking cheating attempts at server level.

[vdfdev]

@justrag Then you are just delegating the responsibility to know what are the possible moves (the input of this function) to the UI. Which is not great as it is part of the rules of the game.

And any AI algorithm will need a list of possible moves, and if there is a non-deterministic factor (a dice), it will also need the probability for each new state that can happen (rolled 1, rolled 2, rolled 3, etc...)

An algorithm like Minimax will need to create a tree of possible actions and states and calculate the expected reward for each action.

See this article for an introduction on Minimax:
https://medium.freecodecamp.org/simple-chess-ai-step-by-step-1d55a9266977

[vdfdev]

@tolmar I agree that adding weights would be less ergonomic to other users, which is not what we want. However, I think we can use flags like you said and assume if the person does not provide an weight, it is 100% of probability (which is deterministic).

I am going to familiarize myself a little bit more with the current API and propose changes later.

[philihp]

++ to adding some standard way of enumerating legal moves given a state of the game. It's not going to be practical to have a tree search try all possible moves including illegal ones; the state space will blow up after only two or three levels of depth.

[justrag]

@Felizardo I actually meant a function that was being used both in client and server: for the UI to visualize possible moves and for the server before applying reducer.

[GlukKazan]

Hi

I'm doing a similar project: https://glukkazan.github.io/
One of the difficulties in developing is the AI.
I have implementations of UCT https://github.com/GlukKazan/Dagaz/blob/master/src/debug/kernel/controller/ai/uct-ai.js
and alpha-beta pruning https://github.com/GlukKazan/Dagaz/blob/master/src/debug/kernel/controller/ai/ab-ai.js
These algorithms work in simple games such as Kono https://glukkazan.github.io/elimination/kono.htm
But in more difficult games, such as Chess, there is not enough performance to search in depth.

Because I'm using a universal game-model (allowable moves are generated based
on the game description and used to change the state of the game) I can not use
the optimizations commonly used in specialized chess programs. In addition,
I can not use multithreading (for UCT it would be useful). In Chess, in 3-5 seconds
I have time to search for no more than 4 moves in depth (this is not enough for a strong game).

In even more difficult games, such as Tenjiku Shogi https://glukkazan.github.io/shogi/tenjiku-shogi.htm
Performance is not enough even for viewing all the moves of the 1st level!
At every turn, up to 1000 permissible moves are generated, of which I can see no more than 20.
In these conditions, two things come to the fore:

1. Simple heuristic used to pre-sort the list of moves.
2. More perfect game state evaluation function.

Because the evaluation function will be called less often than when searching
for a depth, it can be done more slowly. For example, I can calculate not just
the material balance, but do it after the best move of the enemy (defined by
heuristics too). This approach works, but not yet well enough. The algorithm
looks like this: https://github.com/GlukKazan/Dagaz/blob/master/src/debug/kernel/controller/ai/aggressive-ai-v3.js

Now I'm working on improving the evaluation function, so that it takes into
account the threats of the pieces. Preliminary results are very encouraging:
https://glukkazan.github.io/elimination/maharadja-variant.htm
The white game looks quite reasonable. Of course, this is a very simple
algorithm and knowing its shortcomings can be easily won:
https://www.youtube.com/watch?v=YiKX_bmdTLs&feature=youtu.be

I am working to improve it. I hope that my long narration has not exhausted
You and can be useful. I wish you success in your project!

Best Regards

[vdfdev]

Ok, now that we have a way to know if the game is over and who won, we need to tackle the move enumeration. After this we should be able to implement a tree search or minimax.

@nicolodavis I saw that you are returning undefined for all illegal moves on the ai branch, which seems like a good way to leverage the way reducers work.

So I am going to implement over the weekend something like was proposed by @tolmar:
(G) => ({ MOVE_PIECE: [["a", 2, "a", 3], ["a", 2, "a", 4], ["b", 2, "b", 3] ... ] })

It would be OK for the user of the library to provide invalid moves on this enumeration, because in this case the subsequent move reducer would return undefined, and we can stop exploring this branch.

It would be more efficient to return only the minimal amount of moves to look for, though. But this way we can let the trade-off of ease to develop x efficiency to be on the library user's hands.

[vdfdev]

Ok folks, I wrote a proposal for how the AI framework API should be:
https://docs.google.com/document/d/1RXr12MMOiB6GDw09_h4pfcItZ8t7ocRPxQ0_-etQIY8/edit#

I included everything in a google doc so it is easier for people to comment on specifics, and it is easier to describe the framework as a whole.

Please let me know what you think 👍

[nicolodavis]

I'll spend some time in the next few weeks working on AI stuff (in addition to UI stuff).

My general plan at the moment is to bundle in a generic MCTS bot that is able to play the game with increasingly higher skill depending on how much information the developer provides:

Level 1 (done):

• The user just enumerates the next moves given a game state.

Level 2:

• The user enumerates moves, and also provides a set of objectives to optimize for. The most basic objective is game victory, which is what Level 1 already targets. Level 2, however, also allows setting shorter term objectives (specific to the game's domain) that will allow creating more intelligent bots that know how to gather resources at the beginning of the game and wage wars at the end (for example).

Will probably need to provide some knobs to fine tune node selection and simulation strategies for even more advanced users, but I'll try to make it very minimal config for users that just want something to play the game better than random.

[philihp]

^love this.

[nicolodavis]

Some interactive game tree visualizations coming soon! MCTS is pretty cool.

[nicolodavis]

Level 1 is done! The tutorial now demonstrates how to add AI.

[abdelrahmanabdelnabi]

(This might not be the best place to ask this question) What if I want to implement my own custom AI algorithm? Does the framework support such functionality? Should I just put my AI logic in the enumerate() method and make it return the move my logic has chosen?

[nicolodavis]

I think that is possible but not the most desirable or efficient. We should probably bundle a bot interface that is completely specified by the user instead.

[pathetic-lynx]

Is there any update on this?
Can I use an evaluation function for a gamestate in the objectives to make MCTS faster?

I already reduced iterations and playoutDepth but it is still very slow

[nicolodavis]

Yes, you can use an evaluation function inside the objectives. Let me know how it goes!

[pathetic-lynx]

After reading bot.js I think I need some help on this one. This is what I put in the 'AI' object. I know this is not valid js (although I don't know why).

objectives: (G, ctx, playerID) => {
  return {distanceObjective: {
    checker: (G, ctx) => {
      this.score = evaluate(G, ctx);
      console.log('test');
      return this.score;
    },
    weight: 0,
  }},
},

So objectives is a function that takes (G, ctx, playerID) as arguments (line 130 in bot.js) or only (G, ctx) (line 218). The function should return an object that contains a checker function and weight.

I am confused and did not find any documentation or usage of objectives in the linked projects, maybe you can give me an example?

[HydraOrc]

Can you please allow to pass depth and iterations options to the bots? The values in the code are too heavy for my game and I have to edit node_modules manually

[nemoDreamer]

This might be a touching on #563 and/or #292 , but it seems that in AI's enumerate, ctx.activePlayers is always just { 0: 'stage-name' }, regardless of ctx.currentPlayer's value. Am I good to just query ctx.activePlayers[0] to get the current stage, or is there an official way to retrieve the current stage that the current player is in?

Is there a "bot" way of querying which moves are available to me given my current turn state? It seems that I have to re-invent the turn/stages logic inside enumerate?

[nemoDreamer]

Hi there,
the roadmap shows objectives as done, and after reading the very limited references available, src/ai/ai.test.ts seems to pass this directly to the MCTSBot's constructor:

    const objectives = () => ({
      'play-on-square-0': {
        checker: G => G.cells[0] !== null,
        weight: 10.0,
      },
    });

But there doesn't seem to be any way of defining this via Game.ai, unlike Game.ai.enumerate?
Also, any way to pass in iterations and playoutDepth?

How does one set up a bot as the second player in a local single-player without needing to manually interact with the "AI" debug panel?

In the absence of a docs update, a simple example in /examples would already be a huge help!
Or paste one here, and I'll submit a docs PR!
Thank you 😄

[delucis]

@nemoDreamer The current state of things isn’t really very flexible. Local single player vs bot(s) is the only scenario that is supported in a more or less straightforward way:

import { Local } from 'boardgame.io/multiplayer';
import { MCTSBot, RandomBot } from 'boardgame.io/ai';

const BgioClient = Client({
  game: YourGameObject,
  numPlayers: 3,
  multiplayer: Local({
    bots: {
      '1': MCTSBot,
      '2': RandomBot,
    },
  }),
  // ...
});

This sets up a local master that runs the provided bot for the playerIDs specified in the bots option when it’s their turn. So above, player 0 would be the human player, player 1 would be played by the MCTSBot, and player2 would be played by the RandomBot.

As you can see, you only pass the bot class, which is instantiated internally, so there’s no way currently to configure the options you mentioned — only enumerate, which is passed automatically from the game object.

There is an additional lower-level way to use the AI modules that gives access to more controls, but only if you have access to the plain Javascript client:

import { Client } from 'boardgame.io/client';
import { MCTSBot, Step } from 'boardgame.io/ai';

const client = Client({ game: YourGame, /* ... */ });

const bot = new MCTSBot({
  game: YourGame,
  enumerate: YourGame.ai.enumerate,
  // objectives, iterations, playOutDepth, ...
});

const botPlayerIDs = new Set(['1']);

client.subscribe(state => {
  if (!state) return;
  if (botPlayerIDs.has(state.ctx.currentPlayer)) {
    Step(client, bot);
  }
});

client.start();

I’d say while this works, it’s more of an interim solution until the proper API gets designed for bots. You can even make this work with React by using the Local multiplayer option to have a plain Javascript client communicate with the React client. I’ll update the examples now with an implementation that does just that (see 9f6f80fda9f7b77ad7ac18c1dd2543e49463e4ae).

[nemoDreamer]

Thank you SO MUCH, @delucis ...! And that example is super helpful!

Hey, if we can pass a class to the bots, couldn't it simply be

class CustomMCTSBot extends MCTSBot {
  constructor(config, ...args) {
    super({
        ...config,
        objectives: { /* ... */ },
        iterations: 500,
        playoutDepth: 25,
      },
      ...args
    );
  }
}

... haven't tried yet, might be totally misguided.

Update: yup! Totally works 🤣
Note: it's playoutDepth, not playOutDepth

[nemoDreamer]

Side-note: is it normal with...

objectives: () => {
  "custom-objective": {
    checker: (G, ctx) => {
      return true|false
    }
    weight: 10.0,
  }
}

...for checker to fire _constantly_, even when it's player 0's turn? Do I maybe _have_ to have a Client running for the bot in parallel to mine?

Doh: never mind... It's the JS console that's just trying to catch up to ~25000 console logs... Takes a _while_ 😬
Sorry for the noise!

[delucis]

Nice! Didn’t think of using a derivative class like that. If you wanted to read those options off your game object, you could do that too. (I’d guess something like this should actually be the default behaviour in any case.)

class CustomMCTSBot extends MCTSBot {
  constructor(opts) {
    super({ ...opts, ...opts.game.ai });
  }
}

So your game can then look something like:

const game = {
  ai: {
    enumerate: () => {},
    objectives () => {},
    iterations: 500,
    playoutDepth: 25,
  },
  // ...
};

Should definitely update the “advanced” AI example to use something like this as it’s way simpler than the acrobatics required in that example.

[hermannloose]

I have only played with the library for a few hours but I noticed that the MCTS bot seemed to be ignoring my defined objectives. Looking at https://github.com/boardgameio/boardgame.io/blob/c8c648ebbde906b303a22c2753ec0b34727da2fc/src/client/debug/ai/AI.svelte#L45, it appears they are not passed to the bot when using the debug panel, is that intentional?

[delucis]

@hermannloose I’m not sure what was intended originally, but you can extend the MCTS bot class as described above to pass the objectives through.

[hermannloose]

I don't want to extend the MCTS bot, as it already handles objectives: https://github.com/boardgameio/boardgame.io/blob/c8c648ebbde906b303a22c2753ec0b34727da2fc/src/ai/mcts-bot.ts#L61

What I meant was that when going to the AI section in the debug panel of my game and using the MCTS bot with the "play" or "simulate" buttons, the objectives, if defined, are simply not passed to the MCTS bot instantiated by the debug panel, at the point that I linked to above: https://github.com/boardgameio/boardgame.io/blob/c8c648ebbde906b303a22c2753ec0b34727da2fc/src/client/debug/ai/AI.svelte#L45

[delucis]

Ah, sorry, I missed that this was in the debug panel (rather than with a Local master as above).

Yes, it would probably be good to pass all the ai options from the game object there. Something like:

    bot = new MCTSBot({
      ...client.game.ai,
      game: client.game,
      iterationCallback,
    });