H3X460N

RL implementation of 2-player perfect information game Hex using markov decision processes to predict future game states

Comment

Inspiration

  • Motivation: Hex is known for its simplicity and yet deep strategic gameplay, as well as its interesting mathematical properties. It has been studied by mathematicians and computer scientists as an example of a game that is easy to understand, but difficult to solve
  • Playing a hex game online and curious about how the game-playing bot works www.lutanho.net/play/hex.html and found that easy mode too easy, and hard mode impossible to beat
  • It has an "Show AI" where it shows 4 probabilistic mappings board acton, states of what the AI neural network would do
  • Move list to track your steps (Nash equilibrium where each action state profile for all players in a game and is used to predict the outcome of their decision-making interaction)

What it does

Objective was to create a Hex bot that could destroy opponents

  • Monte Carlo simulations //“start at center and move outwards” // if i play here as white, what could black play against me? Define a way to represent the state of the board, as well as a way to generate training data for the neural network using reinforcement learning.
  • Monte Carlo tree search algorithm to simulate games between two players and learn the value function of the current state of the board. The value function predicts the probability of winning from a given state - MCTS algorithm to build a tree of the game states and their corresponding values, and use the tree to select moves during gameplay
  • Tile positioning // positions on board == corners, buffers, edges example: piece positioning = can make more moves at the center of the board, can make less moves on the the edge of the board
  • Cube and axial coordinates work on a hex grid https://www.redblobgames.com/grids/hexagons/ * var axial_direction_vectors = [ * Hex(+1, 0), Hex(+1, -1), Hex(0, -1), * Hex(-1, 0), Hex(-1, +1), Hex(0, +1), ]
  • Scoring mechanisms = frontier (points that are touching the outside open squares) vs interior disks (points that are not touching the outside open squares) following the schema of , ,..., ,
extern crate ndarray;
extern crate rand;
extern crate ndarray_rand;

use ndarray::{Array, ArrayD};
use ndarray_rand::{RandomExt, rand::rngs::SmallRng, rand::SeedableRng};
use rand::Rng;
use std::collections::HashMap;

// Define the size of the Hex board
const BOARD_SIZE: usize = 11;

// Define the number of simulations to run for each move
const SIMULATIONS: usize = 100;

// Define the neural network architecture
const INPUT_SHAPE: [usize; 4] = [1, 3, BOARD_SIZE, BOARD_SIZE];
const CONV1_FILTERS: usize = 64;
const CONV1_KERNEL_SIZE: [usize; 2] = [3, 3];
const CONV1_ACTIVATION: &str = "relu";
const CONV2_FILTERS: usize = 32;
const CONV2_KERNEL_SIZE: [usize; 2] = [3, 3];
const CONV2_ACTIVATION: &str = "relu";
const DENSE1_UNITS: usize = BOARD_SIZE.pow(2);
const DENSE1_ACTIVATION: &str = "softmax";

// Define the learning rate and discount factor
const LEARNING_RATE: f32 = 0.001;
const DISCOUNT_FACTOR: f32 = 0.99;

// Define the number of episodes to train for
const EPISODES: usize = 1000;

// Define the MCTS tree
#[derive(Clone)]
struct Node {
    value: f32,
    visits: usize,
    children: HashMap<[usize; 2], Node>,
}

impl Node {
    fn new(value: f32) -> Self {
        Node {
            value,
            visits: 0,
            children: HashMap::new(),
        }
    }
}

// Define the neural network
fn neural_network(input: &ArrayD<f32>) -> ArrayD<f32> {
    let mut model = Array::zeros((DENSE1_UNITS, 1));
    let mut rng = SmallRng::from_entropy();
    let input = input.clone().into_shape(INPUT_SHAPE).unwrap();
    let mut x = input.to_owned();

    // Define the convolutional layers
    let w1 = Array::random((CONV1_FILTERS, INPUT_SHAPE[1], CONV1_KERNEL_SIZE[0], CONV1_KERNEL_SIZE[1]), rng);
    x = x.dot(&w1).into_dyn().into_dimensionality::<ndarray::Ix4>().unwrap();
    x = x.map(|x| if x < 0.0 { 0.0 } else { x });
    let w2 = Array::random((CONV2_FILTERS, CONV1_FILTERS, CONV2_KERNEL_SIZE[0
  • Advanced techniques like Upper Confidence Bounds for Trees (UCT) and progressive widening could be used to improve the efficiency and effectiveness of the search algorithm using a simple game state representation and the UCT formula for selecting nodes
use std::collections::HashMap;

struct Board {
    // Your board struct here
}
#[derive(Copy, Clone)]
enum Player {
    X,
    O,
}
impl Player {
    fn opposite(&self) -> Player {
        match self {
            Player::X => Player::O,
            Player::O => Player::X,
        }
    }
}
struct GameState {
    board: Board,
    current_player: Player,
}
struct Node {
    state: GameState,
    parent: Option<usize>,
    children: Vec<usize>,
    visits: f32,
    total_reward: f32,
}
impl Node {
    fn new(state: GameState, parent: Option<usize>) -> Node {
        Node {
            state,
            parent,
            children: vec![],
            visits: 0.0,
            total_reward: 0.0,
        }
    }
    fn uct_score(&self, exploration: f32) -> f32 {
        if self.visits == 0.0 {
            return std::f32::INFINITY;
        }
        let exploitation = self.total_reward / self.visits;
        let uct = exploration * (self.parent.unwrap().visits.ln() / self.visits).sqrt();
        exploitation + uct
    }
}
fn uct_search(state: GameState, max_iterations: usize, exploration: f32) -> usize {
    let mut nodes = vec![Node::new(state, None)];
    let mut rng = rand::thread_rng();
    for _ in 0..max_iterations {
        let mut node_idx = 0;
        while !nodes[node_idx].children.is_empty() {
            let best_child_idx = nodes[node_idx]
                .children
                .iter()
                .max_by(|&a, &b| {
                    nodes[*a]
                        .uct_score(exploration)
                        .partial_cmp(&nodes[*b].uct_score(exploration))
                        .unwrap()
                })
                .unwrap();
            node_idx = *best_child_idx;
        }
        let new_state = // Generate new state from current state
            let moves = new_state.board.get_possible_moves();
        let new_node_idx = nodes.len();
        nodes.push(Node::new(new_state, Some(node_idx)));
        nodes[node_idx].children.push(new_node_idx);
        let reward = simulate_game(nodes[new_node_idx].state, &moves, &mut rng);
        let mut backprop_idx = Some(new_node_idx);
        while let Some(idx) = backprop_idx {
            nodes[idx].visits += 1.0;
            nodes[idx].total_reward += reward;
            backprop_idx = nodes[idx].parent;
        }
    }
    let best_child_idx = nodes[0]
        .children
        .iter()
        .max_by(|&a, &b| nodes[*a].visits.partial_cmp(&nodes[*b].visits).unwrap())
        .unwrap();
    *best_child_idx
}
fn simulate_game(state: GameState, moves: &[(usize, usize)], rng: &mut impl rand::Rng) -> f32 {
    let mut current_state = state;
    let mut current_player = current_state.current_player;
    let mut winner = None;
    while winner.is_none() {
        let (i, j) = moves[rng.gen_range(0..moves.len())];
        current_state.board.set_cell(i, j, current_player);
        winner = current_state.board.get_winner();
        current_player = current_player.opposite();
    }
    if winner == Some(Player::

How we built it

  • Rust's syntax is designed to be readable and expressive, making it easier to write and maintain code for complex algorithms like Monte Carlo tree search including machine learning libraries like TensorFlow and reinforcement learning libraries like RustyRL
  • Rust's lightweight threads and low-level control over memory make it easy to write concurrent gamebots that can take advantage of multiple cores making it well-suited for writing gamebots that need to make decisions quickly based on large amounts of data.
  • Test out AI for board games with the same technique which led to Alpha Zero for Go and chess (https://vanshel.com/Hexy/Publications/VAnshelevich-01.pdf)
  • Tracks moves offset coordinates game data example: [b a1,w a2,b f4,w e6,b b9,w g5,b d6,w d7,b c7,w e5,b d5,w e3,b d3,w c8,b b8,w d4,b g2,] with Wolve [https://webdocs.cs.ualberta.ca/~hayward/papers/rptBeijing.pdf] program * Self.top_node = (-1, 0) * Self.bottom_node = (n, 0) * Self.left_node = (0, -1) * Self.right_node = (0, n)
  • End game == winner connects (filled cells) find() function , to check end game find(top_node/bottom_node) or find(left_node/bottom_node) virtual island nodes // overlapping corners, union with virutal nodes , one big island that connects all 4 borders (bad!!), use 2 different disjoint set structures one for red and blue (good but not space efficient) is_win(board,player) for horizontal and vertical wins: * DisjointSet(self.cells + [self.top_node, self.bottom_node]) * DisjointSet(self.cells + [self.left_node, self.right_node])

Challenges we ran into

  • Defense: BLOCKERS box them in, where given a location and a distance, what is visible from that location, not blocked by the opponents - prevent them from reaching the end of the map, cut a line and edge case behaviors at the corners, and edges
use std::collections::HashSet;
fn hex_reachable(start: (i32, i32), movement: i32, blocked: &HashSet<(i32, i32)>) -> HashSet<(i32, i32)> {
    let mut visited: HashSet<(i32, i32)> = HashSet::new();
    visited.insert(start);
    let mut fringes = Vec::with_capacity(movement as usize + 1);
    fringes.push(vec![start]);
    for k in 1..movement {
        fringes.push(Vec::new());
        for hex in &fringes[(k - 1) as usize] {
            for dir in 0..6 {
                let neighbor = hex_neighbor(*hex, dir);
                if !visited.contains(&neighbor) && !blocked.contains(&neighbor) {
                    visited.insert(neighbor);
                    fringes[k as usize].push(neighbor);
                }
            }
        }
    }
    visited
}
fn hex_neighbor(hex: (i32, i32), dir: i32) -> (i32, i32) {
    // Your hex_neighbor function implementation here
}
  • Red//blue or Black//white
  • Error handling like expect("Failed to startup bot")

Accomplishments that we're proud of

What we learned

What's next for H3X460N

  • Use a more efficient data structure for the game board where the current implementation uses a 2D array to represent the Hex board, which can be slow and memory-intensive for large board sizes (data structure graph or a sparse matrix changing the board size board.len() nxn)
  • Each game has dozens of moves creating thousands of board possibility states actions
  • Reinforcement learning model: current implementation uses a simple convolutional neural network with two convolutional layers and one dense layer. A more sophisticated architecture, such as a residual neural network or a graph convolutional network, could be used to improve the accuracy and speed of the neural network
  • To avoid the first player having an unfair advantage, the SWAP rule the secpnd player can play normally, or swap, to steal the first player's first move - change from red to blue and then moving to opposite location (reflection along the diagonal axis) on the board
  • Patterns on the board or player history, could be added to improve the accuracy of the gamebot's predictions and make it more difficult to beat.

Built With

Share this project:

Updates