Typescript based monte-carlo acyclic graph search algorithm for multiplayer games

Overview

monte-conti

Description

monte-conti is a typescript based monte-carlo acyclic graph search algorithm for multiplayer games. It can be used in any turn-based strategic multiplayer games.
It is designed to used for simple webgame AI. Thus, this library includes only a few features for small bundle size, while giving reasonable decisions without any prior knowledge of the game.
Implementation detailes are followed from Enhancements for Multi-Player Monte-Carlo Tree Search without progresive history improvements. Uses UCT1 based node selection.

Defining Your Game Rule

GameState

First, you need to define a game state. It should uniquely identify your game state.
If your game is a simple number-counting game, then GameState is a single number.
If it is chess game, GameState can be a array of numbers, [6, 5, 4, 3, 2, 4, 5, 6, 1, 1, ...] as 6 repesents rook, 5 represents knight, 4 repesents bishop, etc.

GameRule

Second, you should define a game rule object that implements GameRule interface. It consists of following methods.

export interface GameRule<GameState> {
    numPlayer: number;
    initialState: GameState;
    getKey: (state: GameState) => string;
    getPlayer: (state: GameState) => number;
    isEnd: (state: GameState) => boolean;
    getReward: (state: GameState) => number[];
    getChildren: (state: GameState) => GameState[];
    getRandomChild: (state: GameState) => GameState| undefined;
}
  • numPlayer: number is the number of players.
  • initialState: GameState is the initial state of the game.
  • getKey: (state: GameState) => string is a hash function for your gameState. It should give unique string for each game state.
  • getPlayer: (state: GameState) => number gives current player to play. Players are specified as integer 0, 1, 2, ... which is matched to index of the reward array.
  • isEnd: (state: GameState) => boolean returns true if input gamestate is end of the game. Else, return false.
  • getReward: (state: GameState) => number[] gives reward of the state for each players. It consist of [reward for player 0, reward for the player 1, reward for player 2, ...]
  • getChildren: (state: GameState) => GameState[] gives a complete array of the available next game states.
  • getRandomChild: (state: GameState) => GameState | undefined gives a random next state. If it is the end of the game so that no more move is available, it returns undefined.

Example Game Rules

Nim Game

Originally, nim game is a two-player game with pile of objects. Each player can remove 1 to 3 of objects from pile. The player who took last object win the game. You can get more information on wiki.
Here, we will consider 3-player nim game with only one pile of 31 objects. Each player can remove 1 to 3 objects. Complete code is available in src/example/NimGameRule.ts.

Rule Definition

We chose the game state as number of obeject removed from pile. Starting from 0, it is incremented 1, 2, or 3 at each turn. If it reach 31, the player who played in that turn earn 1 point. Others get 0 point.

  • numPlayer is set to 3. This is not hard-coded so that you may choose any number.
  • getKey simply calls toString method of the state integer.

Usage

Assume Ai playes first. From the starting state 0, the AI should decide how many number of objects to remove.
You should decide how many time it iterates. The strategy become more and more precise as it iterates, but it will comsume time. About thousand iteration was appropriate in this example, with taking less than one second.

// Initialize a monte-carlo search graph for nim game rule starting from 0.
const sg = new MonteCarloSearchGraph(0, nimGameRule);
// iterate 1000 times
const pick = sg.monteCarloSearch(1000);
// prints how many objects it will remove.
console.log(pick);

Actually, there is no obvious winning-choice in turn 0 of three player game. Thus, it will give arbitrary number picked from its valid choices.
However, as the game become near to end, the winning choice become obvious. As a extreme case, if there are only three object left, you should take all of them to win. As a result, the following code will always print 31.

// Initialize a monte-carlo search graph for nim game rule starting from 0.
const sg = new MonteCarloSearchGraph(28, nimGameRule);
// iterate 1000 times
const pick = sg.monteCarloSearch(1000);
// prints how many objects it will remove.
console.log(pick);

You can also re-use a graph through the game. You may change search start state via updateRoot method. The AI will become smarter over time as you iterate on each turn.

const sg = new MonteCarloSearchGraph(0, nimGameRule);
const pick = sg.monteCarloSearch(1000);
console.log(pick);

// Assume next player picked state 5
sg.updateRoot(5);
const newPick = sg.monteCarloSearch(1000);
console.log(newPick);
You might also like...

A trivia website game based on origin of objects and concepts from around the world

Origin guesser is a quiz/trivia game in which the user is presented a word, object, or flag and offered a series of multiple choice answers to choose from as to the origin of that concept. Unlike other trivia games, this is concentrated only on origin of objects and concepts questions.

Feb 12, 2022

Aprilbeat is an new open-source, online, fully web-based rhythm game

Aprilbeat! open-source web-based online rhythm game Aprilbeat is an new open-source, online, fully web-based rhythm game. It plays songs in APB format

Oct 17, 2022

Visualize the Directed Acyclic Graph that Git creates to connect Commit, Tree and Blob objects internally.

Visualize the Directed Acyclic Graph that Git creates to connect Commit, Tree and Blob objects internally.

Git Graph Visualize the Directed Acyclic Graph that Git creates to connect Commit, Tree and Blob objects. Hosted at HarshKapadia2.github.io/git-graph.

Aug 21, 2022

Adds links to Discogs pages from various sites. Auto search for music on torrent and other sites. Does multi auto-search on Artist/Discography pages. Auto search local HDDs/filelists using Voidtools Everything search engine.

Discogs Scout: Adds links to Discogs pages from various sites. Auto search for music on torrent and other sites. Does multi auto-search on Artist/Disc

Dec 27, 2022

A personal semantic search engine capable of surfacing relevant bookmarks, journal entries, notes, blogs, contacts, and more, built on an efficient document embedding algorithm and Monocle's personal search index.

A personal semantic search engine capable of surfacing relevant bookmarks, journal entries, notes, blogs, contacts, and more, built on an efficient document embedding algorithm and Monocle's personal search index.

Revery 🦅 Revery is a semantic search engine that operates on my Monocle search index. While Revery lets me search through the same database of tens o

Dec 30, 2022

API, web and mobile application for finding a partner to play online multiplayer games.

API, web and mobile application for finding a partner to play online multiplayer games.

Duo Finder Duo Finder is a simple mobile and web application for gamers looking for partners to play a game with. It's basics was developed during the

Sep 20, 2022

A simple library for Node and the browser that allows you to rapidly develop stateful, socketed multiplayer games and web applications.

gameroom.js Overview gameroom.js is a simple library for Node and the browser that allows you to rapidly develop stateful, socketed multiplayer games

Nov 3, 2022

Grupprojekt för kurserna 'Javascript med Ramverk' och 'Agil Utveckling'

JavaScript-med-Ramverk-Laboration-3 Grupprojektet för kurserna Javascript med Ramverk och Agil Utveckling. Utvecklingsguide För information om hur utv

May 18, 2022

Hemsida för personer i Sverige som kan och vill erbjuda boende till människor på flykt

Getting Started with Create React App This project was bootstrapped with Create React App. Available Scripts In the project directory, you can run: np

May 3, 2022

Kurs-repo för kursen Webbserver och Databaser

Webbserver och databaser This repository is meant for CME students to access exercises and codealongs that happen throughout the course. I hope you wi

Jan 3, 2023

"Jira Search Helper" is a project to search more detail view and support highlight than original jira search

Jira Search Helper What is Jira Search Helper? "Jira Search Helper" is a project to search more detail view and support highlight than original jira s

Dec 23, 2022

CyberGraph is a 3D-graph based, user based social connection explorer

CyberGraph is a 3D-graph based, user based social connection explorer

CyberGraph is a 3D-graph based, user based social connection explorer. It has some cool features like 3d node graph, dynamic loading bar, immersive user experience, cyber mode(10-hops friendship network display) and focus mode(aggregated connection display).

Nov 25, 2022

🌅 Content-aware image resizer based on Seam Carving algorithm

🌅 Content-aware image resizer based on Seam Carving algorithm

Content-aware image resizing might be applied when it comes to changing the image proportions (i.e. reducing the width while keeping the height) and when losing some parts of the image is not desirable.

Dec 30, 2022

Fast and robust triangle-triangle intersection test with high precision for cross and coplanar triangles based on the algorithm by Devillers & Guigue.

fast-triangle-triangle-intersection Fast and robust triangle-triangle intersection test with high precision for cross and coplanar triangles based on

Nov 15, 2022

Tesodev-search-app - Personal Search App with React-Hooks

Tesodev-search-app - Personal Search App with React-Hooks

Tesodev-search-app Personal Search App with React-Hooks View on Heroku : [https://tesodev-staff-search-app.herokuapp.com/] Instructions Clone this rep

Nov 10, 2022

Instant spotlight like search and actions in your browser with Sugu Search.

Instant spotlight like search and actions in your browser with Sugu Search.

Sugu Search Instant spotlight like search and actions in your browser with Sugu Search. Developed by Drew Hutton Grab it today for Firefox and Chrome

Oct 12, 2022

An efficient (and the fastest!) way to search the web privately using Brave Search Engine

Brave Search An efficient (and the fastest) way to search the web privately using Brave Search Engine. Not affiliated with Brave Search. Tested on Chr

Jun 2, 2022

🍭 search-buddy ultra lightweight javascript plugin that can help you create instant search and/or facilitate navigation between pages.

🍭 search-buddy ultra lightweight javascript plugin that can help you create instant search and/or facilitate navigation between pages.

🍭 search-buddy search-buddy is an open‑source ultra lightweight javascript plugin (* 1kb). It can help you create instant search and/or facilitate n

Jun 16, 2022
Owner
null
🎮 Excalibur is a free game engine written in TypeScript for making 2D games in HTML5 canvas

?? An easy to use 2D HTML5 game engine written in TypeScript

Excalibur.js 1.3k Dec 30, 2022
GameApp is a web application that allow users to play nostalgic games such as minesweeper, flappybird, and space invasions.

GameApp is currently being developed. GameApp is a web application that allow users to play nostalgic games such as minesweeper, flappybird, and space

Stephanie Li 2 Feb 21, 2022
🟩 in case you want to cheat on your wordle games

Wordle Solver How to use Enter each right guess in the first grid Enter all letters that you know aren't in a certain position in the second grid For

James Zhang 2 Feb 7, 2022
Generate sound effects and background music for good old-fashioned mini-games

Generate sound effects and background music for good old-fashioned mini-games

ABA Games 11 Aug 1, 2022
A simple app to show NBA games and scores/details.

NBA Remix A simple app to show NBA games and scores/details. Deployment After having run the create-remix command and selected "Vercel" as a deploymen

Willian Justen 195 Dec 9, 2022
A clone of the popular game Wordle made using React, Typescript, and Tailwind

Wordle Clone Go play the real Wordle here Read the story behind it here Try a demo of this clone project here Inspiration: This game is an open source

Hannah Park 2.4k Jan 8, 2023
'Neko Mezashi Attack' - a simple but cute action game made with Vite and TypeScript

'Neko Mezashi Attack' is a simple but cute action game made with Vite and TypeScript. This app is packed all resources including style, graphics and audio into 4KB(4096 chars) JS. No runtime libraries or external resources are required.

yuneco 10 Dec 1, 2022
TypeScript library implementing Chess

Created primarily for our chess React project.

COMP2022 3 Mar 5, 2022
A recreation of the popular game Wordle with additional modes and features. Made with Svelte in Typescript.

A recreation of the popular game Wordle by Josh Wardle (now purchased by the New York Times), with additional modes and features. Hosted on GitHub pag

Mikha Davids 117 Dec 11, 2022
Wordle-remake - A site that is based on the wordle famous video game wordle

About the project The game of Wordle seems to be a pretty famous one. I tried to

LeoJit_15 1 Feb 13, 2022