17.MachineLearning_5z5_Reinforcement_Learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "acc3b972-1754-42c9-9fb3-cb0aa6f2d391",
   "metadata": {},
   "source": [
    "# Warsztaty Python w Data Science\n",
    "\n",
    "---\n",
    "\n",
    "## Machine Learning - część 5 z 5. Reinforcement Learning\n",
    "\n",
    "- ### Gra w kółko i krzyżyk\n",
    "- ### Q-Learning i wzór Bellmana\n",
    "- ### Testy A/B\n",
    "- ### Problem wielorękiego bandyty\n",
    "- ### Wyżarzanie\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21ec48e7-de24-4802-8c66-95c165599255",
   "metadata": {},
   "source": [
    "\n",
    "## Gra w kółko i krzyżyk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e945f648-d7c0-4f29-8800-f02b827feb07",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cell(x):\n",
    "    try:\n",
    "        if x.lower()==\"x\":\n",
    "            return \" X \"\n",
    "        if x.lower()==\"o\":\n",
    "            return \" O \"\n",
    "    except:\n",
    "        pass\n",
    "    return \"   \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "714e476d-0027-4328-90cb-46608900fe6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_state(state):\n",
    "    sep = \"_\"*11+\"\\n\"\n",
    "    ret = []\n",
    "    n=0\n",
    "    for row in state:\n",
    "        ret.append(\"|\".join(map(cell,row)))\n",
    "        n+=1\n",
    "        if n<3:\n",
    "                ret.append(sep)\n",
    "    for line in ret:\n",
    "        print(line)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "530352ba-3f14-45d1-a0a4-a02e5fc59632",
   "metadata": {},
   "outputs": [],
   "source": [
    "state = (('x','o',0.0),\n",
    "         ('o','x',0.0),\n",
    "         (0.0,'o','x'))\n",
    "print_state(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d46722f-40ff-4f40-b248-4fecc960b83b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_won(state):\n",
    "    players = ['x', 'o']\n",
    "    for i in [0,1]:\n",
    "        for row in state:\n",
    "            if row==tuple(players[i]*3): # _\n",
    "                return i, True\n",
    "        for cols in [0, 1, 2]:\n",
    "            if state[0][cols]==state[1][cols] and state[2][cols]==state[0][cols] and state[0][cols]==players[i]: # |\n",
    "                return i, True\n",
    "        if state[0][0]==state[1][1] and state[0][0]==state[2][2] and state[0][0]==players[i]:   # \\\n",
    "                return i, True\n",
    "        if state[2][0]==state[1][1] and state[2][0]==state[0][2] and state[0][2]==players[i]:   # /\n",
    "                return i, True\n",
    "            \n",
    "    return -1, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59c0a069-1ac9-4ffb-b669-cc1bab99f731",
   "metadata": {},
   "outputs": [],
   "source": [
    "has_won(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce3448dd-a735-4bf3-8a9c-650c8fe71847",
   "metadata": {},
   "outputs": [],
   "source": [
    "state = (('o','o','o'),\n",
    "         ('o','x',0.0),\n",
    "         (0.33,'o','x'))\n",
    "print_state(state)\n",
    "has_won(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4bea73e6-3795-4717-bd57-a77d14337f6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "state = (('o','x','o'),\n",
    "         ('o','x',0.0),\n",
    "         ('o','o','x'))\n",
    "print_state(state)\n",
    "has_won(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36b82d5e-dbc7-4257-b348-1055a1de92eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "state = (('o','x','x'),\n",
    "         ('o','x',0.0),\n",
    "         ('x','o','x'))\n",
    "print_state(state)\n",
    "has_won(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56f86525-da2d-48f7-a18a-520434c7af16",
   "metadata": {},
   "outputs": [],
   "source": [
    "state = (('o','x','o'),\n",
    "         ('o','x',0.0),\n",
    "         ('x','o','x'))\n",
    "print_state(state)\n",
    "has_won(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9304484d-51cb-4460-9109-6f663e2c7f97",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_full(state):\n",
    "    for row in state:\n",
    "        for v in row:\n",
    "            if v!=\"x\" and v!=\"o\":\n",
    "                return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2808d62c-a9b7-4069-9442-c326cfca1a18",
   "metadata": {},
   "outputs": [],
   "source": [
    "is_full((('o','x','o'),\n",
    "         ('o','x',0.0),\n",
    "         ('o','o','x')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55ae1a08-b286-4115-b925-516bdc730f95",
   "metadata": {},
   "outputs": [],
   "source": [
    "is_full((('o','x','o'),\n",
    "         ('o','x','x'),\n",
    "         ('o','o','x')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed6acb3c-8bdc-413a-8eec-2e3270ecf59e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_valid_move(state, x, y):\n",
    "    row = state[x]\n",
    "    if row[y]!=\"x\" and row[y]!=\"o\":\n",
    "        return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3f6310fc-8959-45db-bd99-cb51d9c6499b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def new_state(state, x, y, character):\n",
    "    l = []\n",
    "    for row in state:\n",
    "        l.append(list(row))\n",
    "    l[x][y] = character\n",
    "    return (tuple(l[0]), tuple(l[1]), tuple(l[2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "84b54fa2-7dbd-49f6-93d3-8da56a2d214d",
   "metadata": {},
   "outputs": [],
   "source": [
    "state = (('o','x','o'),\n",
    "         ('o','x',0.0),\n",
    "         ('o','o','x'))\n",
    "print_state(new_state(state, 1, 2, \"x\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "11ed7a0f-3763-4e24-97a4-d0152893713a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Player:\n",
    "    def move(state):\n",
    "        return state\n",
    "    def learn(self, won):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b87b9b4f-1a27-44dc-ab86-75641e3b72a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "class HumanPlayer(Player):\n",
    "    def __init__(self, character):\n",
    "        self.character=character\n",
    "        \n",
    "    def move(self, state):\n",
    "        print_state(state)\n",
    "        flag = False\n",
    "        while not flag:\n",
    "            print()\n",
    "            x = int(input(f\"({self.character}) row: \"))\n",
    "            y = int(input(f\"({self.character}) col: \"))\n",
    "            flag=is_valid_move(state, x, y)\n",
    "        print()\n",
    "        \n",
    "        return new_state(state, x, y, self.character)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6dad29e-2276-4ff8-a2b1-0c6255b3bd8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "h = HumanPlayer(\"x\")\n",
    "print_state(\n",
    "    h.move((('o','x','o'),\n",
    "            ('o','x',0.0),\n",
    "            ('o','o','x')))\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00f986ad-4005-4634-8b6f-eb8061f5a3dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def do_game(player0, player1, stats, verbose=False):\n",
    "    state = ((0.0, 0.0, 0.0), (0.0, 0.0, 0.0), (0.0, 0.0, 0.0))\n",
    "    ended = False\n",
    "    full = False\n",
    "    won_won = -1\n",
    "    \n",
    "    while not ended and not full:\n",
    "        state = player0.move(state)\n",
    "        who_won, ended = has_won(state)\n",
    "        full = is_full(state)        \n",
    "        if not ended and not full:\n",
    "            state = player1.move(state)\n",
    "            who_won, ended = has_won(state)\n",
    "            full = is_full(state)\n",
    "    if ended:\n",
    "        stats.append(\"WIN 0\" if who_won==0 else \"WIN 1\")\n",
    "        player0.learn(1.0 if who_won==0 else 0.0)\n",
    "        player1.learn(1.0 if who_won==1 else 0.0)\n",
    "    if full and not ended:\n",
    "        stats.append(\"DRAW\")    \n",
    "        player0.learn(0.5)\n",
    "        player1.learn(0.5)\n",
    "    if verbose:\n",
    "        print(\"DRAW\" if full and not ended else f\"{who_won} has WON!\")\n",
    "        print()\n",
    "        print_state(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f72c23d1-2651-4058-aed4-f3934db8c0a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "print([random.randrange(3) for x in range(100)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "acfe93e0-95fa-4922-8920-f9c470f9246a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class RandomPlayer(Player):\n",
    "    def __init__(self, character):\n",
    "        self.character=character\n",
    "        \n",
    "    def move(self, state):\n",
    "        flag = False\n",
    "        while not flag:\n",
    "            x = random.randrange(3)\n",
    "            y = random.randrange(3)\n",
    "            flag=is_valid_move(state, x, y)\n",
    "       \n",
    "        return new_state(state, x, y, self.character)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "659d29cf-784c-4ec7-b2bc-ea161af6fcad",
   "metadata": {},
   "outputs": [],
   "source": [
    "do_game(HumanPlayer('x'), RandomPlayer('o'), [], True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "754ce503-f31b-424a-8e4a-8d8b98bb7d0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "stats = []\n",
    "\n",
    "for i in range(1_000):\n",
    "    do_game(RandomPlayer('x'), RandomPlayer('o'), stats, False)\n",
    "    \n",
    "print(Counter(stats))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "07b929bb-5f75-4fa7-a346-6e6006fffdd1",
   "metadata": {},
   "outputs": [],
   "source": [
    "1_000_000 == 1000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67e17837-e8f3-490f-98d8-42401ad1f970",
   "metadata": {},
   "outputs": [],
   "source": [
    "1_000.0 == 1000.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "564fb04a-456d-4e27-aa41-6382c8a9faee",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "plt.style.use(\"dark_background\")\n",
    "\n",
    "def plot_games(qstats, label0, label1):\n",
    "    games = range(40, len(qstats), 20)\n",
    "    won0 = [ Counter(qstats[:x])['WIN 0']/x for x in games]\n",
    "    won1 = [ Counter(qstats[:x])['WIN 1']/x for x in games]\n",
    "    draw = [ Counter(qstats[:x])['DRAW']/x for x in games]\n",
    "\n",
    "\n",
    "    fig = plt.figure();\n",
    "    plt.figure(figsize=(20,10));\n",
    "    plt.title('Results ratio');\n",
    "    player0, = plt.plot(games, won0, label=label0);\n",
    "    player1, = plt.plot(games, won1, label=label1);\n",
    "    draws, = plt.plot(games, draw, label=\"Draws\");\n",
    "    plt.legend(handles=[player0, player1,  draws], frameon=True, loc=\"best\",  fontsize=16);\n",
    "    plt.show();\n",
    "\n",
    "plot_games(stats, \"Random Player 0 Won\", \"Random Player 1 Won\");"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "087cb52c-cb9a-4f32-ab3b-0fa75b2bcab9",
   "metadata": {},
   "source": [
    "---\n",
    "# _*Q-Learning*_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2054829-4b47-43f0-847c-43cbf50a06b3",
   "metadata": {},
   "source": [
    "https://en.wikipedia.org/wiki/Markov_chain"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7f1c0db-dd84-4a9f-973d-9f2b3588f0c5",
   "metadata": {},
   "source": [
    "https://en.wikipedia.org/wiki/Q-learning"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff438fd3-764b-41ff-bf34-397a670608be",
   "metadata": {},
   "source": [
    "$\n",
    "Q: S \\times A \\rightarrow I\\!R\n",
    "$\n",
    "---\n",
    "\n",
    "## W danym kroku $s$ podejmujemy akcję $a$ która maksymalizuje $Q$\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ed2c6da-7fd6-4433-ad6f-1149522196ed",
   "metadata": {},
   "source": [
    "\n",
    "## $Q$ Może zostać stabularyzowana (tzn. wsadzona do słownika)\n",
    "## Kluczami są pary `(stan, akcja)` a wartością wynik $Q$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "860ea0c6-2335-4c99-8f27-db4ad8ae3433",
   "metadata": {},
   "source": [
    "---\n",
    "# Uczymy się $Q$ korzytając ze __*Wzoru Bellmana*__\n",
    "\n",
    "\n",
    "$\n",
    "Q^{new}(s_t, a_t) = Q(s_t, a_t) + \\alpha \\cdot ( r_t +  \\gamma \\cdot   \\max_{a}Q(s_{t+1}, a) - Q(s_t, a_t) )\n",
    "$\n",
    "---\n",
    "Upraszczając:\n",
    "\n",
    "$\n",
    "Q^{new}(s_t, a_t) = (1- \\alpha) \\cdot Q(s_t, a_t) + \\alpha \\cdot  \\gamma \\cdot   \\max_{a}Q(s_{t+1}, a)\n",
    "$\n",
    "---\n",
    "\n",
    "\n",
    "\n",
    "$\\alpha$ - Tempo uczenia się\n",
    "\n",
    "$\\gamma$ - Degradacja wagi z odległością od bodźca\n",
    "\n",
    "$r_t$ - nagroda w danym stanie"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99bd2449-81b6-4814-96e1-97161282373e",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd45b98c-3d45-48e4-8931-c0e224fac2d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "α = 0.15 # Tempo uczenia się\n",
    "β = 0.60 # Wartość początkowa `Q` - 'agresja'\n",
    "γ = 0.99 # Degradacja wagi z odległością od bodźca "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a234aae5-5f92-44b6-a048-0d0efe0b86da",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e28087a1-8b15-4431-966b-89de3507992f",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import sample\n",
    "\n",
    "\n",
    "class QPlayer(Player):\n",
    "    def __init__(self, character):\n",
    "        self.character=character\n",
    "        #################################################                     \n",
    "        ## stabularyzowane Q  postaci:                 ##\n",
    "        ## { stan1:                                    ##   \n",
    "        ##     { nowy_stan1: q1, nowy_stan2: q2, ...}, ##\n",
    "        ##   stan2:                                    ##\n",
    "        ##     { nowy_stan3: q3, nowy_stan4: q4, ...}, ##\n",
    "        ##  ... }                                      ##\n",
    "        #################################################                     \n",
    "        self.q_table={}\n",
    "        \n",
    "        self.previous_state=None\n",
    "        self.current_state=((0.0, 0.0, 0.0), (0.0, 0.0, 0.0), (0.0, 0.0, 0.0))\n",
    "        \n",
    "    def initialize_q_table(self, state):    \n",
    "        actions = {}   \n",
    "        for x in range(3):\n",
    "            for y in range(3):\n",
    "                if is_valid_move(state, x, y):\n",
    "                    ##################################\n",
    "                    ## Inicjalizacja przez β (beta) ##\n",
    "                    ##################################\n",
    "                    actions[\n",
    "                        new_state(state, x, y, self.character)\n",
    "                    ] = β\n",
    "        self.q_table[state] = actions\n",
    "        \n",
    "        return actions\n",
    "        \n",
    "    def move(self, state):\n",
    "        \n",
    "        ##############################################################\n",
    "        ## Tworzę powiązanie z ruchem drugiego gracza,              ##\n",
    "        ## Aby w Q-table był ciągły łańcuch od poprzedniego ruchu   ##\n",
    "        ##############################################################\n",
    "        \n",
    "        if self.previous_state:\n",
    "            actions = self.q_table.get(self.current_state, {})\n",
    "            if state not in actions.keys():\n",
    "                actions[state] = β\n",
    "                self.q_table[self.current_state] = actions\n",
    "            \n",
    "        ##############################################################\n",
    "        ## Jeśli w Q-table nie ma akcji powiązanych z obecnym       ##\n",
    "        ## stanem, dopisuje wszystkie możliwe akcje z wagą β (beta) ##\n",
    "        ##############################################################\n",
    "        actions = self.q_table.get(state)\n",
    "        if not actions:\n",
    "            actions = self.initialize_q_table(state)\n",
    "\n",
    "        ##############################################################\n",
    "        ## Biorę najlepsze Q dla akcji w tym stanie                 ##\n",
    "        ##############################################################\n",
    "        best_q = max(actions.values())\n",
    "        \n",
    "        ##############################################################\n",
    "        ## Losuję akcję pośród tych co mają najlepsze Q             ##\n",
    "        ##############################################################\n",
    "        best_actions = [ action for action, q in actions.items() if q==best_q ]\n",
    " \n",
    "        self.previous_state = state\n",
    "        self.current_state = sample(best_actions, 1)[0]\n",
    "\n",
    "        return self.current_state\n",
    "    \n",
    "    def learn(self, learned_weight):\n",
    "        \n",
    "        self.q_table[self.previous_state][self.current_state] = learned_weight\n",
    "        self.previous_state=None\n",
    "        \n",
    "        for state, actions in self.q_table.items():\n",
    "            for next_move, q in actions.items():\n",
    "                next_move_actions = self.q_table.get(next_move)\n",
    "                if next_move_actions:\n",
    "                    best_next_q = max(next_move_actions.values())\n",
    "                   \n",
    "                    #########################\n",
    "                    ##    Wzór Bellmana    ##\n",
    "                    #########################\n",
    "                    actions[next_move] = (1-α)*q + γ*α*best_next_q \n",
    "                    \n",
    "                    self.q_table[state] = actions\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fcdcf33-03f6-4fb2-9fef-f390b4145877",
   "metadata": {},
   "outputs": [],
   "source": [
    "qstats = []\n",
    "qplayer = QPlayer('o')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4db73263-9b59-4a89-83f0-e583db33d012",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "for i in range(1):\n",
    "    do_game(RandomPlayer('x'), qplayer, qstats, False)\n",
    "    \n",
    "print(Counter(qstats))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b9c5310a-aeb8-4c72-929a-9c32901a55fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pprint import pprint \n",
    "pprint(qplayer.q_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4b78fa2-f436-4942-9fbb-395e233efafa",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "for i in range(1):\n",
    "    do_game(RandomPlayer('x'), qplayer, qstats, False)\n",
    "    \n",
    "print(Counter(qstats))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5f5a8ef-4276-4d86-9186-1332dc575c70",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pprint import pprint \n",
    "pprint(qplayer.q_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "01d66228-b443-4b28-8aa3-9f1b12d0db26",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(2_000):\n",
    "    do_game(RandomPlayer('x'), qplayer,  qstats, False)\n",
    "    \n",
    "print(Counter(qstats))\n",
    "plot_games(qstats, \"Random Player 0 Won\", \"Q Player 1 Won\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8d74078-8f12-407d-b17e-2585e0b7965a",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(2_000):\n",
    "    do_game(RandomPlayer('x'), qplayer,  qstats, False)\n",
    "    \n",
    "print(Counter(qstats))\n",
    "plot_games(qstats, \"Random Player 0 Won\", \"Q Player 1 Won\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2fb36696-2a6d-40dd-b0ae-3d064ba61cf7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_2_game(qstats, stats, labelA, labelB):\n",
    "    qgames = range(40, len(qstats), 20)\n",
    "    qwon0 = [ Counter(qstats[:x])['WIN 0']/x for x in qgames]\n",
    "    qwon1 = [ Counter(qstats[:x])['WIN 1']/x for x in qgames]\n",
    "    qdraw = [ Counter(qstats[:x])['DRAW']/x for x in qgames]\n",
    "    games = range(40, len(stats), 20)\n",
    "    won0 = [ Counter(stats[:x])['WIN 0']/x for x in games]\n",
    "    won1 = [ Counter(stats[:x])['WIN 1']/x for x in games]\n",
    "    draw = [ Counter(stats[:x])['DRAW']/x for x in games]\n",
    "\n",
    "\n",
    "    plt.rcParams['figure.figsize'] = [20,10]\n",
    " \n",
    "    fig = plt.figure();\n",
    " \n",
    "    l = fig.add_subplot(121)   \n",
    "    plt.ylim([0.0, 0.9])\n",
    "    player0, = l.plot(qgames, qwon0, label=\"Random Player 0\");\n",
    "    player1, = l.plot(qgames, qwon1, label=labelA);\n",
    "    draws, = l.plot(qgames, qdraw, label=\"Draws\");\n",
    "    l.legend(handles=[player0, player1,  draws], frameon=True, loc=\"best\", fontsize=16);\n",
    "\n",
    "    r = fig.add_subplot(122)  \n",
    "    plt.ylim([0.0, 0.9])\n",
    "    player0, = r.plot(games, won0, label=\"Random Player 0\");\n",
    "    player1, = r.plot(games, won1, label=labelB);\n",
    "    draws, = r.plot(games, draw, label=\"Draws\");\n",
    "    r.legend(handles=[player0, player1,  draws], frameon=True, loc=\"best\", fontsize=16);\n",
    "    plt.show();\n",
    "\n",
    "plot_2_game(qstats, stats, \"Q-Player 1\", \"Random Player 1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a4ed58e8-cb17-4faf-9ecf-9cd163137d69",
   "metadata": {},
   "outputs": [],
   "source": [
    "qstats2 = []\n",
    "for i in range(1_000):\n",
    "    do_game(RandomPlayer('x'), qplayer,  qstats2, False)\n",
    "    \n",
    "print(Counter(qstats2))\n",
    "plot_games(qstats2, \"Random Player 0 Won\", \"Q Player 1 Won\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67b26c40-2abc-4d4f-8013-8356de3c1ccf",
   "metadata": {},
   "source": [
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96290871-5474-462e-abfb-88484d876303",
   "metadata": {},
   "source": [
    "# __*A/B testing*__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f45fb43c-ae14-49ed-9337-4549fe9d7b74",
   "metadata": {},
   "source": [
    "## Za optimizely:\n",
    "\n",
    "### __*A/B testing*__ (also known as split testing or bucket testing) is a method of __*comparing two versions*__ of a webpage or app against each other to determine which one performs __*better*__.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9243e3d-207c-450c-84fa-53bf9324855d",
   "metadata": {},
   "source": [
    "#### Co to znaczy __*better*__\n",
    "- Bounce rate\n",
    "- Conversion\n",
    "- Click-Through Rate\n",
    "- Etc. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "466ed171-c181-44a9-b8e4-884d8f1a5d45",
   "metadata": {},
   "source": [
    "---\n",
    "## A/B Testing ma zazwyczaj dwie fazy\n",
    "- ### __*Eksploracji*__ - sprawdzamy która lepsza jest lepsza\n",
    "- ### __*Eksploatacji*__ - \"lepsza\" wersja działa jako jedyna"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9093235-ce7c-4da5-8835-df872086cbe7",
   "metadata": {},
   "source": [
    "## Wady typowego podejścia\n",
    "- Nie ma płynnego przejścia z 2 wersji na 1\n",
    "- W czasie eksploracji sprawdzamy wiele dużo wersji gorszych od wersji kontrolnej\n",
    "- __*Eksploracja w praktyce nigdy się nie kończy*__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1955f337-8229-4cd5-91ba-3e77c5b425ff",
   "metadata": {},
   "source": [
    "---\n",
    "# Problem Wielorękiego Bandyty\n",
    "\n",
    "![](img\\Las_Vegas_slot_machines.jpg)\n",
    "\n",
    "https://en.wikipedia.org/wiki/Multi-armed_bandit\n",
    "\n",
    "Mamy budżet aby jak najwięcej \"ugrać\". Poszczególni jednoręcy bandyci różnią się między sobą szansą na wygraną. \n",
    "\n",
    "Ile spędzić budzetu na eksplorację najlepszej maszyny, a ile na osiągnięcie wygranej ?\n",
    "\n",
    "Istnieje olbrzymi katalog algorytmów (ang. __bandit algorithms__) które na to odpowiadają.\n",
    "- ε-greedy\n",
    "- soft-max\n",
    "- soft-max z wyżarzaniem\n",
    "- Upper Confidence Bound\n",
    "- Exp3\n",
    "- etc. etc.\n",
    "\n",
    "![](img\\banditalgos.jpg)\n",
    "\n",
    "---\n",
    "## Algorytm ε-zachłanny - ε-greedy\n",
    "\n",
    "- Z prawdopodobieństwem `1-ε`  wybieramy strategię kontrolną `A` do eksploatacji. \n",
    "\n",
    "- Z prawdopodobieństwem `ε` (np. 20%) wybieramy strategię `B`  do eksploracji. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45c80a02-5126-45a9-8159-a1cf628d9167",
   "metadata": {},
   "source": [
    "![](img\\epsilongreedy.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0df6c89-bce8-4004-8802-f0e66248aa01",
   "metadata": {},
   "source": [
    "---\n",
    "## Algorytm Soft-max\n",
    "\n",
    "$r_A$ - proporcja sukcesów w gałęzi `A`\n",
    "\n",
    "$r_B$ - proporcja sukcesów w gałęzi `B`\n",
    "\n",
    "\n",
    "- Z prawdopodobieństwem $$\\frac{r_A}{r_A+r_B}$$ wybieramy strategię kontrolną `A` do eksploatacji. \n",
    "\n",
    "- Z prawdopodobieństwem $$\\frac{r_B}{r_A+r_B}$$ wybieramy strategię `B`  do eksploracji. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99fd4dee-1efd-4ca8-8d25-6e1a658df40d",
   "metadata": {},
   "source": [
    "---\n",
    "## Algorytm Soft-max z wyżarzaniem\n",
    "\n",
    "$r_A$ - proporcja sukcesów w gałęzi `A`\n",
    "\n",
    "$r_B$ - proporcja sukcesów w gałęzi `B`\n",
    "\n",
    "$\\tau$ - \"temperatura\"\n",
    "\n",
    "\n",
    "- Z prawdopodobieństwem $$\\frac{exp(r_A/\\tau)}{exp(r_A/\\tau)+exp(r_B/\\tau)}$$ wybieramy strategię kontrolną `A` do eksploatacji. \n",
    "\n",
    "- Z prawdopodobieństwem $$\\frac{exp(r_B/\\tau)}{exp(r_A/\\tau)+exp(r_B/\\tau)}$$ wybieramy strategię `B`  do eksploracji. \n",
    "\n",
    "---\n",
    "`t = sum(self.counts) + 1`\n",
    "\n",
    "`tau = 1 / math.log(t + 0.0000001)`\n",
    "\n",
    "\n",
    "---\n",
    "## __*Wyżarzanie*__\n",
    "\n",
    "### __*Wyżarzanie*__ - to obniżanie \"temperatury\" czyli zmienności układu z czasem\n",
    "\n",
    "### Dzięki __*wyżarzaniu*__ - system z czasem coraz rzadziej eksploruje.\n",
    "\n",
    "#### __*Hartowanie*__ to zwiększanie temperatury raz na jakiś czas aby \"wybić\" system z minimów lokalnych \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c058f3bb-d437-44cd-82dd-44a76b1e6ff7",
   "metadata": {},
   "source": [
    "---\n",
    "## Q-Player z __*Wyżarzaniem*__\n",
    "\n",
    "Zmniejszamy `α` przez mnożenie przez `γ` co krok - przez co spada zmienność układu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a11ad3c0-ba42-4d70-b6e2-2b14b69a7e4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "α = 0.99  # Tempo uczenia się - \"temperatura\"\n",
    "β = 0.80  # Wartość początkowa `Q` - 'agresja'\n",
    "γ = 0.975 # Degradacja wagi z odległością od bodźca oraz tempo spadku \"temperatury\"\n",
    "\n",
    "class AnnealingQPlayer(QPlayer):\n",
    "    def __init__(self, character):\n",
    "        super().__init__(character)\n",
    "        \n",
    "    def learn(self, learned_weight):\n",
    "        global α\n",
    "        \n",
    "        ################\n",
    "        ## Wyżarzanie ##\n",
    "        ################\n",
    "        α *= γ\n",
    "        \n",
    "        super().learn(learned_weight)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "feb69d60-e8d5-4d5b-81df-f1c4a76d5c99",
   "metadata": {},
   "outputs": [],
   "source": [
    "annealing_qplayer = AnnealingQPlayer('o')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6c290762-a528-4119-bf7f-8780e4216db6",
   "metadata": {},
   "outputs": [],
   "source": [
    "aqstats = []\n",
    "for i in range(2_500):\n",
    "    do_game(RandomPlayer('x'), annealing_qplayer,  aqstats, False)\n",
    "    \n",
    "print(Counter(aqstats))\n",
    "plot_games(aqstats, \"Random Player 0 Won\", \"Annealing Q Player 1 Won\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "416cf20f-28b9-4bf8-8a9b-d4d652eed707",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(2_500):\n",
    "    do_game(RandomPlayer('x'), annealing_qplayer,  aqstats, False)\n",
    "    \n",
    "print(Counter(aqstats))\n",
    "plot_games(aqstats, \"Random Player 0 Won\", \"Annealing Q Player 1 Won\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "95341d10-ead7-46a5-92c5-ce573d4fe49e",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_2_game(qstats, aqstats, \"Q-Player 1\", \"Annealing Q-Player 1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c640618d-f539-4604-94bc-63dd8578aa0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "aqstats2 = []\n",
    "for i in range(1000):\n",
    "    do_game(RandomPlayer('x'), annealing_qplayer,  aqstats2, False)\n",
    "    \n",
    "print(Counter(aqstats2))\n",
    "\n",
    "\n",
    "plot_2_game(qstats2, aqstats2, \"Q-Player 1\", \"Annealing Q-Player 1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94641d69-6378-41ff-998a-00a63b976c83",
   "metadata": {},
   "source": [
    "---\n",
    "# Zadanie 1\n",
    "\n",
    "Zagrajcie w kółko i krzyżyk"
   ]
  }
 ],
 "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}