{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "def to_bits(*l):\n",
    "    return reduce(lambda r,i: r |(1<<i), l, 0)\n",
    "\n",
    "def winning_patterns():\n",
    "    v1 = to_bits(0,1,2)\n",
    "    h1 = to_bits(0,3,6)\n",
    "    return [v1, v1<<3, v1<<6, h1, h1<<1, h1<<2, to_bits(0,4,8), to_bits(2,4,6)]\n",
    "WINNING_PATTERNS = winning_patterns()\n",
    "\n",
    "class Game:\n",
    "    def __init__(self, board=None, step=-1, result=None):\n",
    "        if board == None:\n",
    "            board = [0, 0]\n",
    "        self.board=[0, 0]\n",
    "        self.load((board, step, result))\n",
    "    \n",
    "    def save(self):\n",
    "        return self.board[:], self.step, self.result\n",
    "    \n",
    "    def load(self, state):\n",
    "        self.board[:], self.step, self.result = state\n",
    "        \n",
    "    def possible_moves(self):\n",
    "        occupied = self.board[0]|self.board[1]\n",
    "        return [i for i in range(9) if occupied&(1<<i) ==0]\n",
    "    \n",
    "    def move(self, i):\n",
    "        self.step+=1\n",
    "        color = self.step&1\n",
    "        occupied = self.board[0]|self.board[1]\n",
    "        assert (occupied >> i)&1 == 0\n",
    "        self.board[color] |= (1<<i)\n",
    "        if any(p&self.board[color] == p for p in WINNING_PATTERNS):\n",
    "            self.end = True\n",
    "            self.result = 2*color-1\n",
    "        elif self.step == 8:\n",
    "            self.result = 0\n",
    "    \n",
    "    def sim_move(self, i):        \n",
    "        color = (self.step+1)&1\n",
    "        board = self.board[:]\n",
    "        board[color] |= (1<<i)\n",
    "        return (board[0]<<9)|board[1]\n",
    "            \n",
    "    def repr(self):\n",
    "        rtn = \"\"\n",
    "        for i in range(9):\n",
    "            is_o = (self.board[0]>>i)&1\n",
    "            is_x = (self.board[1]>>i)&1\n",
    "            p = '.ox'[is_o + 2*is_x]\n",
    "            rtn+=p\n",
    "            if i%3==2:\n",
    "                rtn+=\"\\n\"\n",
    "        return rtn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import choice, random, shuffle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Q=[None]*2**18\n",
    "reg = lambda x: 1. if x is None else -x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result -1\n",
      "color 0 new score 0.1 [-1.0]\n",
      "xxo\n",
      ".oo\n",
      "xox\n",
      "\n",
      "\n",
      "color 1 new score 0.0 [0.1, 0.0]\n",
      ".xo\n",
      ".oo\n",
      "xox\n",
      "\n",
      "\n",
      "color 0 new score 0.0 [None, None, 0.0]\n",
      ".xo\n",
      "..o\n",
      "xox\n",
      "\n",
      "\n",
      "color 1 new score 0.0 [None, None, None, 0.0]\n",
      ".xo\n",
      "..o\n",
      ".ox\n",
      "\n",
      "\n",
      "color 0 new score 0.0 [None, None, None, None, 0.0]\n",
      ".xo\n",
      "..o\n",
      "..x\n",
      "\n",
      "\n",
      "color 1 new score 0.0 [None, None, None, None, None, 0.0]\n",
      ".xo\n",
      "..o\n",
      "...\n",
      "\n",
      "\n",
      "color 0 new score 4.685590000000002e-05 [None, 0.0, -0.00010000000000000003, -0.00010000000000000003, -0.00010000000000000003, 1.0000000000000004e-05, -0.00010000000000000003]\n",
      ".x.\n",
      "..o\n",
      "...\n",
      "\n",
      "\n",
      "color 1 new score -2.7951601083128245e-05 [4.0951000000000015e-05, 4.685590000000002e-05, 4.111102279000002e-05, 4.098229373826158e-05, 4.685590000000002e-05, 0.0010090000000000003, 0.0010090000000000003, 4.685590000000002e-05]\n",
      "...\n",
      "..o\n",
      "...\n",
      "\n",
      "\n",
      "color 0 new score 1.808124087450758e-05 [1.0000000000000005e-07, -1.0000000000000005e-08, -1.0000000000000005e-08, 0.0, 0.0, -2.7951601083128245e-05, 7.574869000000003e-06, -9.100000000000004e-07, -8.290000000000003e-07]\n",
      "...\n",
      "...\n",
      "...\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def run_game(game, verbose = False):\n",
    "    board = (game.board[0]<<9)|game.board[1]\n",
    "    if game.result is not None:\n",
    "        Q[board] = -abs(float(game.result))\n",
    "        if verbose:\n",
    "            print(\"result\", game.result)\n",
    "        return\n",
    "    color = (game.step+1)&1\n",
    "    d = 2*color -1\n",
    "    moves = game.possible_moves()   \n",
    "    boards = [game.sim_move(m) for m in moves]            \n",
    "    r = random()\n",
    "    if r < 0.01:\n",
    "        m = choice(moves)\n",
    "    else:\n",
    "        values = [reg(Q[b]) for b in boards]\n",
    "        m = max(zip(values,moves))[1]\n",
    "    s = game.repr()\n",
    "    game.move(m)\n",
    "    run_game(game, verbose)\n",
    "    estQ = max(-Q[b] for b in boards if Q[b] is not None)\n",
    "    if Q[board] is None:\n",
    "        Q[board] = 0.\n",
    "    Q[board]+=0.1*(estQ-Q[board])\n",
    "    if verbose:\n",
    "        print(\"color\", color, \"new score\", Q[board], [Q[b] for b in boards])   \n",
    "        print(s)\n",
    "        print()\n",
    "for i in range(100):\n",
    "    run_game(Game())\n",
    "run_game(Game(), True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def alphabeta(game, ub=1, lb=-1, level=0, verbose=False):\n",
    "    #print(level, \"alphabeta\", ub, lb)\n",
    "    #print(game.repr())\n",
    "    board = (game.board[0]<<9)|game.board[1]\n",
    "    if game.result is not None:\n",
    "        return abs(game.result), -1\n",
    "    color = (game.step+1)&1\n",
    "    d = 2*color -1\n",
    "    moves = game.possible_moves()\n",
    "    state = game.save()\n",
    "    best_m = None\n",
    "    for m in moves:\n",
    "        game.move(m)\n",
    "        v, _ = alphabeta(game, -lb, -ub, level+1)\n",
    "        game.load(state)\n",
    "        if verbose:\n",
    "            print(m, v, lb)\n",
    "        if v >= ub:\n",
    "            return -ub, best_m\n",
    "        if v > lb:\n",
    "            lb = v\n",
    "            best_m = m\n",
    "    return -lb, best_m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0\n",
      "o..\n",
      "...\n",
      "...\n",
      "\n",
      "0 4\n",
      "o..\n",
      ".x.\n",
      "...\n",
      "\n",
      "0 1\n",
      "oo.\n",
      ".x.\n",
      "...\n",
      "\n",
      "0 2\n",
      "oox\n",
      ".x.\n",
      "...\n",
      "\n",
      "0 6\n",
      "oox\n",
      ".x.\n",
      "o..\n",
      "\n",
      "0 3\n",
      "oox\n",
      "xx.\n",
      "o..\n",
      "\n",
      "0 5\n",
      "oox\n",
      "xxo\n",
      "o..\n",
      "\n",
      "0 7\n",
      "oox\n",
      "xxo\n",
      "ox.\n",
      "\n",
      "0 8\n",
      "oox\n",
      "xxo\n",
      "oxo\n",
      "\n"
     ]
    }
   ],
   "source": [
    "game = Game()\n",
    "while game.result is None:\n",
    "    v, m = alphabeta(game)\n",
    "    print(v,m)\n",
    "    game.move(m)\n",
    "    print(game.repr())"
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}