simple-halite-crossentropy-rl.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Turtle runs - RL with the smoothed Crossentropy Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import numpy as np\n",
    "from collections import namedtuple\n",
    "from time import time\n",
    "\n",
    "import xxhash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "actions = ['N', 'E', 'S', 'W', 'O']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Turtle():\n",
    "    def __init__(self, position, halite):\n",
    "        self.position = position\n",
    "        self.halite = halite"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GameState():\n",
    "    def __init__(self, game_map, position, halite):\n",
    "        self.game_map = game_map\n",
    "        self.position = position\n",
    "        self.halite = halite\n",
    "        \n",
    "    def __eq__(self, other):\n",
    "        return (self.game_map == other.game_map).all() and self.position == other.position and self.halite == other.halite\n",
    "\n",
    "    def __contains__(self, key):\n",
    "        return key in self.numbers\n",
    "    \n",
    "    def __bytes__(self):\n",
    "        return bytes(self.game_map) + bytes(self.position) + bytes(self.halite)\n",
    "\n",
    "    def __hash__(self):\n",
    "        xxh64 = xxhash.xxh64(bytes(game.reset()))\n",
    "        return xxh64.intdigest()\n",
    "    \n",
    "    def get_nn_repr(self):\n",
    "        hal_std_scaled = (self.game_map.reshape(-1,) - 500) / 1000\n",
    "        pos_indicator = [0] * 25\n",
    "        pos_indicator[self.position[0] * 5 + self.position[1]] = 1\n",
    "        return list(hal_std_scaled) + pos_indicator + [self.halite / 1000]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SimpleHalite():\n",
    "    def __init__(self, height, width, start_pos):\n",
    "        np.random.seed(42)\n",
    "        self.game_map = np.random.randint(1, 1000, size=(height, width))\n",
    "        self.game_map[start_pos] = 0\n",
    "        self.orig_map = self.game_map.copy()\n",
    "        self.turtle = Turtle(start_pos, 0)\n",
    "        self.turn = 1\n",
    "        self.max_turns = 50\n",
    "        self.halite = 0\n",
    "        self.base = start_pos\n",
    "        self.height = height\n",
    "        self.width = width\n",
    "        self.actions = ['N', 'E', 'S', 'W', 'O']\n",
    "    \n",
    "    def get_state(self):\n",
    "        game_state = GameState(self.game_map.copy(), self.turtle.position, self.turtle.halite)\n",
    "        return game_state\n",
    "    \n",
    "    def get_possible_actions(self):\n",
    "        return self.actions\n",
    "    \n",
    "    def reset(self):\n",
    "        self.game_map = self.orig_map.copy()\n",
    "        self.turtle = Turtle(self.base, 0)\n",
    "        self.turn = 1\n",
    "        self.halite = 0\n",
    "        return self.get_state()\n",
    "        \n",
    "    def step(self, action):\n",
    "        reward = 0\n",
    "        if action == 'O':\n",
    "            mined_halite = self.game_map[self.turtle.position] // 4\n",
    "            self.game_map[self.turtle.position] -= mined_halite\n",
    "            self.turtle.halite += min(1000, mined_halite)\n",
    "        else:\n",
    "            if action == 'N':\n",
    "                cost_halite = self.game_map[self.turtle.position] // 10\n",
    "                new_pos = tuple([sum(x) for x in zip(self.turtle.position, (0, 1))])\n",
    "            elif action == 'E':\n",
    "                cost_halite = self.game_map[self.turtle.position] // 10\n",
    "                new_pos = tuple([sum(x) for x in zip(self.turtle.position, (1, 0))])\n",
    "            elif action == 'S':\n",
    "                cost_halite = self.game_map[self.turtle.position] // 10\n",
    "                new_pos = tuple([sum(x) for x in zip(self.turtle.position, (0, -1))])\n",
    "            elif action == 'W':\n",
    "                cost_halite = self.game_map[self.turtle.position] // 10\n",
    "                new_pos = tuple([sum(x) for x in zip(self.turtle.position, (-1, 0))])\n",
    "            #print(cost_halite, self.turtle.halite)\n",
    "            if cost_halite <= self.turtle.halite:\n",
    "                #print(\"moving turtle to {}\".format(new_pos))\n",
    "                self.turtle = Turtle(new_pos, self.turtle.halite - cost_halite)\n",
    "            else:\n",
    "                mined_halite = self.game_map[self.turtle.position] // 4\n",
    "                self.game_map[self.turtle.position] -= mined_halite\n",
    "                self.turtle.halite += min(1000, mined_halite)                \n",
    "        self.turtle.position = (self.turtle.position[0] % self.width, \n",
    "                                self.turtle.position[1] % self.height)\n",
    "        if self.turtle.position == self.base:\n",
    "            self.halite += self.turtle.halite\n",
    "            reward = self.turtle.halite\n",
    "            self.turtle.halite = 0\n",
    "        self.turn += 1\n",
    "        return self.get_state(), reward, self.turn == self.max_turns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy(game_state, turn, policy_mapping=None):\n",
    "    if policy_mapping is not None and (game_state.position, game_state.halite) in policy_mapping:\n",
    "        for map_action in policy_mapping[(game_state.position, game_state.halite)]:\n",
    "            if (map_action[0] == game_state.game_map).all():\n",
    "                return np.random.choice(actions, p=map_action[1])\n",
    "    return np.random.choice(actions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Needs to be a tuple rather than a list as start_pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "game = SimpleHalite(5, 5, (2, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "game.reset()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 200\n",
    "M = 10\n",
    "alpha = 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_to_policy_mapping(policy_mapping, game_map, position, halite, action_probs):\n",
    "    if (position, halite) not in policy_mapping:\n",
    "            policy_mapping[(position, halite)] = []\n",
    "    policy_mapping[(position, halite)].append((game_map, action_probs))\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ArrayWrapper():\n",
    "    def __init__(self):\n",
    "        self.els = []\n",
    "    \n",
    "    def append(self, obj):\n",
    "        self.els.append(obj)\n",
    "        \n",
    "    def __contains__(self, obj):\n",
    "        for el in self.els:\n",
    "            if (el == obj).all():\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#policy_mapping = {}\n",
    "for j in range(M):\n",
    "    now = time()\n",
    "    state_action_maps = []\n",
    "    final_rewards = []\n",
    "    for i in range(N):\n",
    "        state_action_map = []\n",
    "        game_state = game.reset()\n",
    "        done = False\n",
    "        total_reward = 0\n",
    "        while not done:\n",
    "            action = policy(game_state, turn, policy_mapping)\n",
    "            state_action_map.append((game_state, action))\n",
    "            game_state, reward, done = game.step(action)\n",
    "            total_reward += reward\n",
    "        state_action_maps.append(state_action_map)\n",
    "        final_rewards.append(total_reward)\n",
    "    print(j, np.mean(final_rewards))\n",
    "    elite_games = np.argsort(final_rewards)[N//5:]\n",
    "    maps_to_keep = np.array(state_action_maps)[elite_games]\n",
    "    full_map = {}\n",
    "    for sam in maps_to_keep:\n",
    "        for sap in sam:\n",
    "            if (sap[0].position, sap[0].halite) not in full_map:\n",
    "                full_map[(sap[0].position, sap[0].halite)] = []\n",
    "            full_map[(sap[0].position, sap[0].halite)].append((sap[0].game_map, sap[1]))\n",
    "    print(\"Entries in policy mapping:\", sum(len(x) for x in policy_mapping.values()))\n",
    "    print(\"Number of keys:\", len(policy_mapping.keys()))\n",
    "    updated, not_updated = 0, 0\n",
    "    for ((position, halite), saps) in full_map.items():\n",
    "        done_policies = ArrayWrapper()\n",
    "        for (state_map, action) in saps:\n",
    "            if state_map not in done_policies:\n",
    "                done_policies.append(state_map)\n",
    "                subset = [a for (s, a) in saps if (s == state_map).all()]\n",
    "                action_probs = []\n",
    "                action_probs_raw = []\n",
    "                for action in actions:\n",
    "                    action_probs.append((subset.count(action) + 1) / (len(subset) + 5))\n",
    "                    action_probs_raw.append(subset.count(action) / len(subset))\n",
    "                if (position, halite) in policy_mapping: \n",
    "                    found = False\n",
    "                    for ix, (game_map, probs) in enumerate(policy_mapping[position, halite]):\n",
    "                        if (game_map == state_map).all():\n",
    "                            policy_mapping[(position, halite)][ix] = \\\n",
    "                                (state_map, alpha * np.array(action_probs_raw) + (1 - alpha) * np.array(probs))\n",
    "                            updated += 1\n",
    "                            found = True\n",
    "                            break\n",
    "                    if not found:\n",
    "                        not_updated += 1\n",
    "                        add_to_policy_mapping(policy_mapping, state_map, position, halite, action_probs)\n",
    "                else:\n",
    "                    not_updated += 1\n",
    "                    add_to_policy_mapping(policy_mapping, state_map, position, halite, action_probs)\n",
    "    print(\"Updated: {}, not updated: {}\".format(updated, not_updated))\n",
    "    print(\"Iteration took {:.0f} seconds\".format(time() - now))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approximate crossentropy method "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use a NN to encode the state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neural_network import MLPClassifier\n",
    "agent = MLPClassifier(hidden_layer_sizes=(128,128),\n",
    "                      activation='relu',\n",
    "                      warm_start=True, #keep progress between .fit(...) calls\n",
    "                      max_iter=2 #make only 1 iteration on each .fit(...)\n",
    "                     )\n",
    "n_actions = len(game.get_possible_actions())\n",
    "#initialize agent to the dimension of state an amount of actions\n",
    "agent.fit([game.reset().get_nn_repr()]*n_actions, game.get_possible_actions())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_approx_cem(game, agent, n_iter, n_sessions):\n",
    "    all_actions = game.get_possible_actions()\n",
    "    for j in range(n_iter):\n",
    "        now = time()\n",
    "        state_action_pairs_list = []\n",
    "        final_rewards = []\n",
    "        max_probs = []\n",
    "        for i in range(n_sessions):\n",
    "            state_action_pairs = []\n",
    "            game_state = game.reset()\n",
    "            done = False\n",
    "            total_reward = 0\n",
    "            while not done:\n",
    "                nn_game_state = game_state.get_nn_repr()\n",
    "                probs = agent.predict_proba([nn_game_state])[0] \n",
    "                max_probs.append(max(probs))\n",
    "                action = np.random.choice(all_actions, p=probs)\n",
    "                state_action_pairs.append((nn_game_state, action))\n",
    "                game_state, reward, done = game.step(action)\n",
    "                total_reward += reward\n",
    "            state_action_pairs_list.append(state_action_pairs)\n",
    "            final_rewards.append(total_reward)\n",
    "        print(j, np.mean(final_rewards))\n",
    "        elite_games = np.argsort(final_rewards)[n_sessions//5:]\n",
    "        pairs_to_keep = np.array(state_action_pairs_list)[elite_games]\n",
    "        elite_states = [sap[0] for sam in pairs_to_keep for sap in sam]\n",
    "        elite_actions = [sap[1] for sam in pairs_to_keep for sap in sam]\n",
    "        agent.fit(X=elite_states, y=elite_actions)\n",
    "        print(\"Iteration took {:.0f} seconds\".format(time() - now))\n",
    "        print(\"Mean certainty on best action: {}\".format(np.mean(max_probs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_approx_cem(game, agent, 20, 2000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "f = open(r'./policy.pickle', 'wb')\n",
    "pickle.dump(policy_mapping, f)\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class QLearningAgent:\n",
    "    def __init__(self, alpha, epsilon, discount, possible_actions):\n",
    "        \"\"\"\n",
    "        Q-Learning Agent\n",
    "        \"\"\"\n",
    "        self.possible_actions = possible_actions\n",
    "        self._qvalues = {}\n",
    "        self.alpha = alpha\n",
    "        self.epsilon = epsilon\n",
    "        self.discount = discount\n",
    "\n",
    "    def get_qvalue(self, state, action):\n",
    "        \"\"\" Returns Q(state,action) \"\"\"\n",
    "        if state in self._qvalues:\n",
    "            if action not in self._qvalues[state]:\n",
    "                self._qvalues[state][action] = 0\n",
    "        else:\n",
    "            self._qvalues[state] = {}\n",
    "            for action in self.possible_actions:\n",
    "                self._qvalues[state][action] = 0\n",
    "        return self._qvalues[state][action]\n",
    "\n",
    "    def set_qvalue(self,state,action,value):\n",
    "        \"\"\" Sets the Qvalue for [state,action] to the given value \"\"\"\n",
    "        if state not in self._qvalues:\n",
    "            self._qvalues[state] = {}\n",
    "        self._qvalues[state][action] = value\n",
    "\n",
    "    def get_value(self, state):\n",
    "        \"\"\"\n",
    "        V(s) = max_over_action Q(state,action) over possible actions.\n",
    "        \"\"\"\n",
    "        possible_actions = self.possible_actions\n",
    "\n",
    "        #If there are no legal actions, return 0.0\n",
    "        if len(possible_actions) == 0:\n",
    "            return 0.0\n",
    "\n",
    "        value = max(self.get_qvalue(state, a) for a in possible_actions)\n",
    "\n",
    "        return value\n",
    "\n",
    "    def update(self, state, action, reward, next_state):\n",
    "        \"\"\"\n",
    "        Q(s,a) := (1 - alpha) * Q(s,a) + alpha * (r + gamma * V(s'))\n",
    "        \"\"\"\n",
    "        gamma = self.discount\n",
    "        learning_rate = self.alpha\n",
    "        new_q_val = (1 - learning_rate) * self.get_qvalue(state, action) + learning_rate * (reward + gamma * self.get_value(next_state))\n",
    "        self.set_qvalue(state, action, new_q_val)\n",
    "\n",
    "    \n",
    "    def get_best_action(self, state):\n",
    "        \"\"\"\n",
    "        Compute the best action to take in a state (using current q-values). \n",
    "        \"\"\"\n",
    "        possible_actions = self.possible_actions\n",
    "        best_action = possible_actions[np.argmax([self.get_qvalue(state, a) for a in possible_actions])]\n",
    "        return best_action\n",
    "\n",
    "    def get_action(self, state):\n",
    "        \"\"\"\n",
    "        Compute the action to take in the current state, including exploration.  \n",
    "        With probability self.epsilon, take a random action.\n",
    "            Otherwise - the best policy action (self.getPolicy).\n",
    "        \"\"\"\n",
    "        if np.random.uniform() < self.epsilon:\n",
    "            return np.random.choice(self.possible_actions)\n",
    "        else:\n",
    "            return self.get_best_action(state)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "agent = QLearningAgent(alpha=0.5, epsilon=0.25, discount=0.99, \n",
    "                       possible_actions=game.get_possible_actions())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_qlearning_agent(game, agent, n_iter, n_sessions):\n",
    "    for j in range(n_iter):   \n",
    "        now = time()\n",
    "        final_rewards = []\n",
    "        for i in range(n_sessions):\n",
    "            game_state = game.reset()\n",
    "            done = False\n",
    "            total_reward = 0\n",
    "            while not done:\n",
    "                action = agent.get_action(game_state)\n",
    "                next_game_state, reward, done = game.step(action)\n",
    "                agent.update(game_state, action, reward, next_game_state)\n",
    "                game_state = next_game_state\n",
    "                total_reward += reward\n",
    "            final_rewards.append(total_reward)\n",
    "        print(\"Iteration took {:.0f} seconds\".format(time() - now))\n",
    "        print(\"Mean reward on iteration {}: {}\".format(np.mean(final_rewards)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_qlearning_agent(game, agent, 3, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}