Jocly UCT

From Jocly Wiki
Jump to: navigation, search

The default artificial intelligence engine in Jocly is based on the alpha-beta algorithm, however all new implemented games now use UCT (Upper Confidence Tree), a Monte-Carlo Tree Search algorithm and most older games have been updated to support this method. For an introduction to game algorithms, check this article.

In Jocly, the AI is configured by level. When describing a level in the game model configuration, you must specify the engine to be used and a number of associated parameters, for instance, the basic Chess implementation defines a model like:

{
    ...
    "levels": [
        {
            "ai": "uct",
            "playoutDepth": 0,
            "minVisitsExpand": 1,
            "c": 0.6,
            "ignoreLeaf": false,
            "uncertaintyFactor": 3,
            "name": "easy",
            "label": "Easy",
            "maxNodes": 1000
        },
        {
            "ai": "uct",
            "playoutDepth": 0,
            "minVisitsExpand": 1,
            "c": 0.6,
            "ignoreLeaf": false,
            "uncertaintyFactor": 3,
            "name": "fast",
            "label": "Fast [1sec]",
            "maxDuration": 1,
            "isDefault": true
        },
        ...
    ],
    ...
}

Any level definition must be hold those parameters:

  • name: a machine-readable name for the level. Make sure all levels have different names
  • label: the level name to be displayed to the user
  • isDefault: if set to true, this corresponding level will be the one used by default

The main level parameters related to the AI are:

  • ai: must be the string "uct"
  • c: the exploration parameter of the Monte Carlo tree search algorithm. It is often chosen empirically
  • maxDuration: the maximum number of seconds for the AI to search for the next move
  • maxNodes: the maximum number of different nodes to be explored

There is generally no need to define both max parameters, but you need set at least one. maxDuration produces a constant search time, so the AI level will depend on the CPU it is running on, maxNodes controls the memory to be used, this produces a constant AI level, but the duration will vary considerably depending on how powerful the player's CPU is.

Some other UCT related AI parameters are briefly explained below but should not be modified unless you are an expert:

  • playoutDepth: the number of moves to be run in the playouts (heuristic-based moves to be played from a search tree leaf). In practice, unless you have excellent heuristics, we noticed the outcome is better not using playouts (set to value 0)
  • minVisitsExpand: the number of search visits in order to expand a node. 1 is a good value
  • ignoreLeaf: if set, nodes that have not been expand do not participate in back propagating the best move evaluation in the search tree
  • uncertaintyFactor: a constant that motivates the computer to play the best move sooner than latter. Otherwise, the computer may not choose to play a winning move as it sees it can play it later