connect4_mcts

README.md

connect4_mcts

To install dependencies:

bun install

To run:

bun run index.ts

This project was created using bun init in bun v0.5.9. Bun is a fast all-in-one JavaScript runtime.

connect4_mcts.test.ts

import { expect, test } from "bun:test";
import { exampleMatch, parse, rand_turn, run, mcts } from "./connect4_mcts";

test("rand_turn", () => {
    let game = parse(exampleMatch);
    //console.log(game);
    let turn = rand_turn(game);
    //console.log(turn);
    //console.log(game);
});

test("2 + 2", () => {
    expect(3 + 2).toBe(5);
});

test("rand_game", () => {
    let game = parse(exampleMatch);
    let winner = run(game);
});

test("mcts", () => {
    let game = parse(exampleMatch);
    let move = mcts(game);
    console.log(move);
});

connect4_mcts.ts

export type Player = {
    kind: "user" | "agent";
    username: string;
    agentname?: string;
    game?: string;
}

export type Action = {
    game: string;
    column: number;
}

export type Turn = {
    number: number;
    player: number | null;
    action: Action | null;
    next_player: number;
}

export type State = {
    game: string;
    over: boolean;
    winner: number | null;
    next_player: number;
    board: string[][];
}

export type Match = {
    id: number;
    players: Player[];
    turns: Turn[];
    turn: number;
    state: State;
}

export const exampleMatch: Match = { "id": 1, "players": [{ "kind": "user", "username": "steve" }, { "kind": "agent", "game": "connect4", "username": "steve", "agentname": "youragent" }], "turns": [{ "number": 0, "player": null, "action": null, "next_player": 0 }, { "number": 1, "player": 0, "action": { "game": "connect4", "column": 3 }, "next_player": 1 }, { "number": 2, "player": 1, "action": { "game": "connect4", "column": 2 }, "next_player": 0 }, { "number": 3, "player": 0, "action": { "game": "connect4", "column": 3 }, "next_player": 1 }], "turn": 3, "state": { "game": "connect4", "over": false, "winner": null, "next_player": 1, "board": [[" ", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " "], ["R", " ", " ", " ", " ", " "], ["B", "B", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " "]] } }

// Our representation of a game
type Game = {
    player: number;
    board: Int8Array;
}

export const ourGame: Game = {
    player: 1,
    board: new Int8Array(42),
}

export function parse(match: Match): Game {
    let board = new Int8Array(42);
    for (let col = 0; col < 7; col++) {
        for (let row = 0; row < 6; row++) {
            let piece = match.state.board[col][row];
            if (piece == "R") {
                board[col * 6 + row] = 1;
            } else if (piece == "B") {
                board[col * 6 + row] = 2;
            }
        }
    }
    return {
        player: match.state.next_player + 1,
        board: board,
    }
}

export function rand_col(game: Game): number {
    let col = Math.floor(Math.random() * 7);
    while (game.board[col * 6 + 5] != 0) {
        col = Math.floor(Math.random() * 7);
    }
    return col;
}

export function turn(game: Game, col: number) {
    let row = 0;
    while (game.board[col * 6 + row] != 0) {
        row++;
    }
    game.board[col * 6 + row] = game.player;
    game.player = 3 - game.player;
}

export function rand_turn(game: Game): number {
    let col = rand_col(game);
    turn(game, col);
    return col;
}

export function check(game: Game): number {
    // Check for horizontal wins
    for (let row = 0; row < 6; row++) {
        for (let col = 0; col < 4; col++) {
            let piece = game.board[col * 6 + row];
            if (piece != 0
                && piece == game.board[(col + 1) * 6 + row]
                && piece == game.board[(col + 2) * 6 + row]
                && piece == game.board[(col + 3) * 6 + row]) {
                return piece;
            }
        }
    }

    // Check for vertical wins
    for (let col = 0; col < 7; col++) {
        for (let row = 0; row < 3; row++) {
            let piece = game.board[col * 6 + row];
            if (piece != 0
                && piece == game.board[col * 6 + row + 1]
                && piece == game.board[col * 6 + row + 2]
                && piece == game.board[col * 6 + row + 3]) {
                return piece;
            }
        }
    }

    // Check for diagonal wins
    for (let col = 0; col < 4; col++) {
        for (let row = 0; row < 3; row++) {
            let piece = game.board[col * 6 + row];
            if (piece != 0
                && piece == game.board[(col + 1) * 6 + row + 1]
                && piece == game.board[(col + 2) * 6 + row + 2]
                && piece == game.board[(col + 3) * 6 + row + 3]) {
                return piece;
            }
        }
    }

    // Check for diagonal wins
    for (let col = 0; col < 4; col++) {
        for (let row = 3; row < 6; row++) {
            let piece = game.board[col * 6 + row];
            if (piece != 0
                && piece == game.board[(col + 1) * 6 + row - 1]
                && piece == game.board[(col + 2) * 6 + row - 2]
                && piece == game.board[(col + 3) * 6 + row - 3]) {
                return piece;
            }
        }
    }

    // Check for a tie
    for (let col = 0; col < 7; col++) {
        if (game.board[col * 6 + 5] == 0) {
            return 0;
        }
    }
    return 3;
}

export function run(game: Game): number {
    let winner = check(game);
    while (winner == 0) {
        rand_turn(game);
        winner = check(game);
    }
    return winner;
}

export function mcts(game: Game): number {
    let actions = [];
    for (let col = 0; col < 7; col++) {
        if (game.board[col * 6 + 5] == 0) {
            actions.push(col);
        }
    }

    let scores = new Float32Array(7);
    for (let i = 0; i < 7; i++) {
        scores[i] = -1;
    }
    for (let action of actions) {
        let wins = 0;
        let losses = 0;
        let draws = 0;

        for (let i = 0; i < 10000; i++) {
            const player = game.player;
            let new_game = {
                player: game.player,
                board: game.board.slice(),
            }
            turn(new_game, action)
            const winner = run(new_game);
            if (winner == 3) {
                draws++;
            } else if (winner == player) {
                wins++;
            } else {
                losses++;
            }
        }

        const score = (wins * 1 + losses * -1) / (wins + losses + draws);
        scores[action] = score;
    }

    let best_score = -1;
    let best_action = -1;
    for (let i = 0; i < 7; i++) {
        if (scores[i] > best_score) {
            best_score = scores[i];
            best_action = i;
        }
    }
    return best_action;
}

Dockerfile

FROM debian:stable-slim as get

WORKDIR /bun

RUN apt-get update
RUN apt-get install curl unzip -y
RUN curl --fail --location --progress-bar --output "/bun/bun.zip" "https://github.com/oven-sh/bun/releases/latest/download/bun-linux-x64.zip"
RUN unzip -d /bun -q -o "/bun/bun.zip"
RUN mv /bun/bun-linux-x64/bun /usr/local/bin/bun
RUN chmod 777 /usr/local/bin/bun

FROM debian:stable-slim
COPY --from=get /usr/local/bin/bun /bin/bun
RUN ln -s /bin/bun /bin/bunx && chmod 777 /bin/bunx
WORKDIR /app
ADD connect4_mcts.ts /app/connect4_mcts.ts
ADD index.ts /app/index.ts

CMD ["bun", "run", "/app/index.ts"]

fly.toml

# fly.toml app configuration file generated for connect4-mcts on 2023-05-11T13:30:23-05:00
#
# See https://fly.io/docs/reference/configuration/ for information about how to use this file.
#

app = "connect4-mcts"
kill_signal = "SIGINT"
kill_timeout = 5
primary_region = "ord"
processes = []

[build]

[env]

[experimental]
  auto_rollback = true

[[services]]
  http_checks = []
  internal_port = 3000
  min_machines_running = 0
  processes = ["app"]
  protocol = "tcp"
  script_checks = []
  [services.concurrency]
    hard_limit = 25
    soft_limit = 20
    type = "connections"

  [[services.ports]]
    force_https = true
    handlers = ["http"]
    port = 80

  [[services.ports]]
    handlers = ["tls", "http"]
    port = 443

  [[services.tcp_checks]]
    grace_period = "1s"
    interval = "15s"
    restart_limit = 0
    timeout = "2s"

index.ts

import { type Serve } from "bun";
import { parse, mcts, Match } from "./connect4_mcts";

export default {
    async fetch(req) {
        if (req.method != "POST") {
            return new Response("ok");
        }
        const match = await req.json();
        const game = parse(match as Match);
        const action = mcts(game);
        const response = `{"game":"connect4","column":${action}}`;
        console.log(response);

        return new Response(response);
    },
} satisfies Serve;

package.json

{
  "name": "connect4_mcts",
  "module": "index.ts",
  "type": "module",
  "devDependencies": {
    "bun-types": "^0.5.0"
  }
}

tsconfig.json

{
  "compilerOptions": {
    "lib": [
      "ESNext"
    ],
    "module": "esnext",
    "target": "esnext",
    "moduleResolution": "bundler",
    "strict": true,
    "downlevelIteration": true,
    "skipLibCheck": true,
    "jsx": "react-jsx",
    "allowSyntheticDefaultImports": true,
    "forceConsistentCasingInFileNames": true,
    "allowJs": true,
    "types": [
      "bun-types" // add Bun global
    ]
  }
}