euchre.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "RANKS = ['A', 'K', 'Q', 'J', '10', '9']\n",
    "SUITS = ['♠', '♣', '♡', '♢']\n",
    "\n",
    "SCORING = {5: 2, 4: 1, 3: 1, 2: 0, 1: 0, 0: 0}\n",
    "OPPO = {5: 2, 4: 2, 3: 2, 2: 0, 1: 0, 0: 0}\n",
    "\n",
    "def euchre_deck():\n",
    "    return [(rank, suit) for rank in RANKS for suit in SUITS]\n",
    "\n",
    "def card_to_bits(card):\n",
    "    return 1 << (len(RANKS) * SUITS.index(card[1]) + RANKS.index(card[0]))\n",
    "\n",
    "def cards_to_bits(cards):\n",
    "    return sum(card_to_bits(card) for card in cards)\n",
    "\n",
    "def bits_to_card(bits):\n",
    "    bit_pos = bin(bits)[::-1].index('1')\n",
    "    return (RANKS[bit_pos % len(RANKS)], SUITS[bit_pos // len(RANKS)])\n",
    "\n",
    "def bits_to_cards(bits):\n",
    "    return [bits_to_card(1 << b) for b in range(24) if (1 << b) & bits]\n",
    "\n",
    "def deck_to_state(deck):\n",
    "    return (sum(card_to_bits(c) for c in deck[:5]),\n",
    "            sum(card_to_bits(c) for c in deck[5:10]),\n",
    "            sum(card_to_bits(c) for c in deck[10:15]),\n",
    "            sum(card_to_bits(c) for c in deck[15:20]),\n",
    "            card_to_bits(deck[20]),\n",
    "            0, 0, 0, 0, 0)\n",
    "\n",
    "def render_cards(bits):\n",
    "    cards = bits_to_cards(bits)\n",
    "    return ' '.join(''.join(c) for c in cards)\n",
    "\n",
    "assert card_to_bits(('Q', '♡')) == 16384\n",
    "assert bits_to_card(16384) == ('Q', '♡')\n",
    "\n",
    "assert [bits_to_card(0b1000 << (s * len(RANKS))) for s in range(4)] == [('J', s) for s in SUITS]\n",
    "assert [bits_to_card(0b1 << (s * len(RANKS))) for s in range(4)] == [('A', s) for s in SUITS]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# state: (player 0 hand, player 1 hand, player 2 hand, player 3 hand, turned up,\n",
    "#         trump suit, led suit, declared team tricks, declaring player, next player)\n",
    "\n",
    "class EuchreBase:\n",
    "    def do_pass(self, state, action):\n",
    "        p0, p1, p2, p3, tu, _, ls, _, _, np = state\n",
    "        if np == 3:\n",
    "            tu, ls = 0, (bin(tu)[::-1].index('1') // len(RANKS) + 1)  # turn down the card and stash the suit\n",
    "        return (p0, p1, p2, p3, tu, 0, ls, 0, 0, (np + 1) % 4)\n",
    "\n",
    "    def do_pickup(self, state, action):\n",
    "        p0, p1, p2, p3, tu, _, _, _, _, np = state\n",
    "        # dealer goes next, to discard\n",
    "        return (p0, p1, p2, p3 | tu, 0, bin(tu)[::-1].index('1') // len(RANKS) + 1, 0, 0, np, 3)\n",
    "\n",
    "    def do_declare(self, state, action):\n",
    "        trump = int(action.split()[1])\n",
    "        p0, p1, p2, p3, _, _, _, _, _, np = state\n",
    "        return (p0, p1, p2, p3, 0, trump + 1, 0, 0, np, 0)\n",
    "\n",
    "    def do_discard(self, state, action):\n",
    "        card = 1 << int(action.split()[1])\n",
    "        p0, p1, p2, p3, _, ts, _, _, dp, _ = state\n",
    "        return (p0, p1, p2, p3 - card, 0, ts, 0, 0, dp, 0)\n",
    "\n",
    "    def do_play(self, state, action):\n",
    "        card = 1 << int(action.split()[1])\n",
    "        p0, p1, p2, p3, tu, ts, ls, dt, dp, np = state\n",
    "        tu |= card\n",
    "        np = (np + 1) % 4\n",
    "        played = bin(tu).count('1')\n",
    "        if played == 1:\n",
    "            ls = bin(card)[::-1].index('1') // len(RANKS) + 1\n",
    "        if played == 4:\n",
    "            winning_card = self.highest_card(tu, ls - 1, ts - 1)\n",
    "            winner = next(p for p in range(4) if state[p] & winning_card)\n",
    "            if winner & 1 == dp & 1:  # winning player is on same team as player who called suit\n",
    "                dt += 1\n",
    "            # update\n",
    "            p0 &= ~tu\n",
    "            p1 &= ~tu\n",
    "            p2 &= ~tu\n",
    "            p3 &= ~tu\n",
    "            tu, ls, np = 0, 0, winner\n",
    "        return (p0, p1, p2, p3, tu, ts, ls, dt, dp, np)\n",
    "\n",
    "    def highest_card(self, cards, led, trump):\n",
    "        right, left = self.right_bower(trump), self.left_bower(trump)\n",
    "        if right & cards:\n",
    "            return right\n",
    "        if left & cards:\n",
    "            return left\n",
    "        trump_cards = cards & self.cards_of_suit(trump, trump)\n",
    "        if trump_cards:\n",
    "            return trump_cards & -trump_cards\n",
    "        suit_cards = cards & self.cards_of_suit(led, trump)\n",
    "        return suit_cards & -suit_cards\n",
    "\n",
    "    def next_state(self, state, action):\n",
    "        token = action.split()[0]\n",
    "        return getattr(self, f'do_{token}')(state, action)\n",
    "\n",
    "    def legal_actions_bids(self, state):\n",
    "        if state[4] == 0:  # the card has been turned down, its suit is in state[6]\n",
    "            suits = [f'declare {i}' for i, s in enumerate(SUITS) if i != state[6] - 1]\n",
    "            if state[9] != 3:\n",
    "                suits.append('pass')  # not the dealer, so not screwed\n",
    "            return suits\n",
    "        return ['pass', 'pickup']\n",
    "\n",
    "    def legal_actions_discard(self, state):\n",
    "        hand = state[3]\n",
    "        return [f'discard {pos}' for pos in range(24) if (1 << pos) & hand]\n",
    "\n",
    "    def legal_actions_lead(self, state):\n",
    "        hand = state[state[9]]\n",
    "        return [f'play {pos}' for pos in range(24) if (1 << pos) & hand]\n",
    "\n",
    "    def legal_actions_follow(self, state):\n",
    "        hand = state[state[9]]\n",
    "        trump_suit = state[5] - 1\n",
    "        led_suit = state[6] - 1\n",
    "\n",
    "        matching_cards = self.cards_of_suit(led_suit, trump_suit) & hand\n",
    "        if not matching_cards:\n",
    "            matching_cards = hand\n",
    "\n",
    "        return [f'play {pos}' for pos in range(24) if (1 << pos) & matching_cards]\n",
    "\n",
    "    def legal_actions(self, state):\n",
    "        if state[5] == 0:  # trump suit not declared, bidding phase\n",
    "            return self.legal_actions_bids(state)\n",
    "        if bin(state[3]).count('1') == 6:  # dealer picked up the card, now must discard\n",
    "            return self.legal_actions_discard(state)\n",
    "        if state[4] == 0:  # nothing turned up, we lead\n",
    "            return self.legal_actions_lead(state)\n",
    "        return self.legal_actions_follow(state)\n",
    "\n",
    "class Jacks(EuchreBase):\n",
    "    def right_bower(self, trump):\n",
    "        return 0b1000 << (trump * len(RANKS))\n",
    "\n",
    "    def left_bower(self, trump):\n",
    "        return 0b1000 << ((trump ^ 1) * len(RANKS))\n",
    "\n",
    "    def cards_of_suit(self, suit, trump):\n",
    "        base = 0b111111 << (suit * len(RANKS))\n",
    "        if trump & 2 != suit & 2:  # not of the same color as the trump suit, so no bower adjustment\n",
    "            return base\n",
    "        return base ^ self.left_bower(trump)\n",
    "\n",
    "class Aces(EuchreBase):\n",
    "    def right_bower(self, trump):\n",
    "        return 0b1 << (trump * len(RANKS))\n",
    "\n",
    "    def left_bower(self, trump):\n",
    "        return 0b1 << ((trump ^ 1) * len(RANKS))\n",
    "\n",
    "    def cards_of_suit(self, suit, trump):\n",
    "        base = 0b111111 << (suit * len(RANKS))\n",
    "        if trump & 2 != suit & 2:  # not of the same color as the trump suit, so no bower adjustment\n",
    "            return base\n",
    "        return base ^ self.left_bower(trump)\n",
    "\n",
    "class NoBowers(EuchreBase):\n",
    "    def right_bower(self, trump):\n",
    "        return 0\n",
    "\n",
    "    def left_bower(self, trump):\n",
    "        return 0\n",
    "\n",
    "    def cards_of_suit(self, suit, trump):\n",
    "        return 0b111111 << (suit * len(RANKS))\n",
    "\n",
    "assert ({bits_to_card(1 << b) for b in range(24) if (1 << b) & Jacks().cards_of_suit(0, 0)} == \n",
    "        {('A', '♠'), ('K', '♠'), ('Q', '♠'), ('J', '♠'), ('10', '♠'), ('9', '♠'), ('J', '♣')})\n",
    "assert ({bits_to_card(1 << b) for b in range(24) if (1 << b) & Jacks().cards_of_suit(1, 0)} == \n",
    "        {('A', '♣'), ('K', '♣'), ('Q', '♣'), ('10', '♣'), ('9', '♣')})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#game = Jacks()\n",
    "\n",
    "#deck = euchre_deck()\n",
    "#random.shuffle(deck)\n",
    "#initial_state = deck_to_state(deck)\n",
    "\n",
    "#print(initial_state)\n",
    "#print(game.legal_actions(initial_state))\n",
    "\n",
    "#for hand in initial_state[:5]:\n",
    "#    print(bits_to_cards(hand))\n",
    "\n",
    "#state = game.next_state(initial_state, 'pickup')\n",
    "#print(state)\n",
    "#for hand in state[:5]:\n",
    "#    print(bits_to_cards(hand))\n",
    "#print(game.legal_actions(state))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#game = Jacks()\n",
    "#actions = ['pass', 'pass', 'pass', 'pickup', 'discard 23', 'play 6',\n",
    "#           'play 10', 'play 11', 'play 8', 'play 19', 'play 22', 'play 21',\n",
    "#           'play 5', 'play 3', 'play 9', 'play 4', 'play 15', 'play 1',\n",
    "#           'play 17', 'play 13', 'play 14', 'play 16', 'play 20', 'play 12', 'play 7']\n",
    "#state = (1704512, 4207632, 2148480, 8454434, 8, 0, 0, 0, 0, 0)\n",
    "#print(f'p0: {render_cards(state[0])}\\n'\n",
    "#      f'p1: {render_cards(state[1])}\\n'\n",
    "#      f'p2: {render_cards(state[2])}\\n'\n",
    "#      f'p3: {render_cards(state[3])}\\n\\n'\n",
    "#      f'{render_cards(state[4])}  -- player {state[9]} to go.\\n\\n')\n",
    "#for action in actions:\n",
    "#    assert action in game.legal_actions(state)\n",
    "#    state = game.next_state(state, action)\n",
    "#    print(f'p0: {render_cards(state[0])}\\n'\n",
    "#          f'p1: {render_cards(state[1])}\\n'\n",
    "#          f'p2: {render_cards(state[2])}\\n'\n",
    "#          f'p3: {render_cards(state[3])}\\n\\n'\n",
    "#          f'{render_cards(state[4])}  -- player {state[9]} to go.\\n\\n')\n",
    "\n",
    "#print(game.legal_actions(state))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#print(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def resolve(state, game, tree):\n",
    "    # returns: (sum of tricks taken by makers,\n",
    "    #           sum of tricks taken by defenders,\n",
    "    #           sum of points by makers,\n",
    "    #           sum of points by defenders,\n",
    "    #           minimax tricks taken by makers,\n",
    "    #           number of outcomes)\n",
    "    if state in tree:\n",
    "        return tree[state]\n",
    "    legal = game.legal_actions(state)\n",
    "    if not legal:\n",
    "        tricks = state[7]\n",
    "        return (tricks, 5 - tricks, SCORING[tricks], OPPO[5 - tricks], tricks, 1)\n",
    "    children = [game.next_state(state, action) for action in legal]\n",
    "    results = [resolve(S, game, tree) for S in children]\n",
    "    team = state[8] & 1\n",
    "    f = max if team == (state[9] & 1) else min\n",
    "    value = (sum(r[0] for r in results),\n",
    "             sum(r[1] for r in results),\n",
    "             sum(r[2] for r in results),\n",
    "             sum(r[3] for r in results),\n",
    "             f(r[4] for r in results),\n",
    "             sum(r[5] for r in results))\n",
    "    tree[state] = value\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "games = [('Jacks', Jacks()), ('Aces', Aces()), ('No Bowers', NoBowers())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "deck = euchre_deck()\n",
    "random.shuffle(deck)\n",
    "initial_state = deck_to_state(deck)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p0: A♠ 10♠ Q♣ A♢ Q♢, p1: Q♠ J♠ 9♠ K♣ 9♣, p2: K♠ 10♣ J♡ 9♡ 10♢, p3: J♣ K♡ Q♡ 10♡ K♢, turned up: A♡\n",
      "\n",
      "                        tricks  points  points   tricks  outcomes\n",
      "                        maker   maker   defend  minimax\n",
      "                        (avg)   (avg)   (avg)            (num)\n",
      "Jacks\n",
      "  maker: 0, suit: ♡ --  1.832   0.153   1.693        1   6888672\n",
      "  maker: 1, suit: ♡ --  3.168   0.847   0.307        4   6888672\n",
      "  maker: 2, suit: ♡ --  1.832   0.153   1.693        1   6888672\n",
      "  maker: 3, suit: ♡ --  3.168   0.847   0.307        4   6888672\n",
      "  maker: 0, suit: ♠ --  1.474   0.124   1.752        0   306056\n",
      "  maker: 0, suit: ♣ --  1.449   0.067   1.867        0   519472\n",
      "  maker: 0, suit: ♢ --  3.359   0.933   0.325        5   987156\n",
      "  maker: 1, suit: ♠ --  3.526   1.012   0.248        5   306056\n",
      "  maker: 1, suit: ♣ --  3.551   1.036   0.133        5   519472\n",
      "  maker: 1, suit: ♢ --  1.641   0.163   1.675        0   987156\n",
      "  maker: 2, suit: ♠ --  1.474   0.124   1.752        0   306056\n",
      "  maker: 2, suit: ♣ --  1.449   0.067   1.867        0   519472\n",
      "  maker: 2, suit: ♢ --  3.359   0.933   0.325        5   987156\n",
      "  maker: 3, suit: ♠ --  3.526   1.012   0.248        5   306056\n",
      "  maker: 3, suit: ♣ --  3.551   1.036   0.133        5   519472\n",
      "  maker: 3, suit: ♢ --  1.641   0.163   1.675        0   987156\n",
      "Aces\n",
      "  maker: 0, suit: ♡ --  1.685   0.148   1.705        0   2831544\n",
      "  maker: 1, suit: ♡ --  3.315   0.915   0.295        5   2831544\n",
      "  maker: 2, suit: ♡ --  1.685   0.148   1.705        0   2831544\n",
      "  maker: 3, suit: ♡ --  3.315   0.915   0.295        5   2831544\n",
      "  maker: 0, suit: ♠ --  2.623   0.547   0.910        2   522168\n",
      "  maker: 0, suit: ♣ --  2.777   0.648   0.727        3   795636\n",
      "  maker: 0, suit: ♢ --  3.285   0.899   0.388        4   649296\n",
      "  maker: 1, suit: ♠ --  2.377   0.455   1.090        3   522168\n",
      "  maker: 1, suit: ♣ --  2.223   0.363   1.273        2   795636\n",
      "  maker: 1, suit: ♢ --  1.715   0.194   1.612        1   649296\n",
      "  maker: 2, suit: ♠ --  2.623   0.547   0.910        2   522168\n",
      "  maker: 2, suit: ♣ --  2.777   0.648   0.727        3   795636\n",
      "  maker: 2, suit: ♢ --  3.285   0.899   0.388        4   649296\n",
      "  maker: 3, suit: ♠ --  2.377   0.455   1.090        3   522168\n",
      "  maker: 3, suit: ♣ --  2.223   0.363   1.273        2   795636\n",
      "  maker: 3, suit: ♢ --  1.715   0.194   1.612        1   649296\n",
      "No Bowers\n",
      "  maker: 0, suit: ♡ --  1.058   0.039   1.922        0   6743448\n",
      "  maker: 1, suit: ♡ --  3.942   1.237   0.078        5   6743448\n",
      "  maker: 2, suit: ♡ --  1.058   0.039   1.922        0   6743448\n",
      "  maker: 3, suit: ♡ --  3.942   1.237   0.078        5   6743448\n",
      "  maker: 0, suit: ♠ --  2.623   0.547   0.910        2   522168\n",
      "  maker: 0, suit: ♣ --  2.230   0.389   1.222        3   720072\n",
      "  maker: 0, suit: ♢ --  3.285   0.899   0.388        4   649296\n",
      "  maker: 1, suit: ♠ --  2.377   0.455   1.090        3   522168\n",
      "  maker: 1, suit: ♣ --  2.770   0.634   0.778        2   720072\n",
      "  maker: 1, suit: ♢ --  1.715   0.194   1.612        1   649296\n",
      "  maker: 2, suit: ♠ --  2.623   0.547   0.910        2   522168\n",
      "  maker: 2, suit: ♣ --  2.230   0.389   1.222        3   720072\n",
      "  maker: 2, suit: ♢ --  3.285   0.899   0.388        4   649296\n",
      "  maker: 3, suit: ♠ --  2.377   0.455   1.090        3   522168\n",
      "  maker: 3, suit: ♣ --  2.770   0.634   0.778        2   720072\n",
      "  maker: 3, suit: ♢ --  1.715   0.194   1.612        1   649296\n",
      "\n",
      "CPU times: user 5min 8s, sys: 2.39 s, total: 5min 10s\n",
      "Wall time: 5min 11s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "print(f'p0: {render_cards(initial_state[0])}, '\n",
    "      f'p1: {render_cards(initial_state[1])}, '\n",
    "      f'p2: {render_cards(initial_state[2])}, '\n",
    "      f'p3: {render_cards(initial_state[3])}, '\n",
    "      f'turned up: {render_cards(initial_state[4])}\\n')\n",
    "print(\"                        tricks  points  points   tricks  outcomes\\n\"\n",
    "      \"                        maker   maker   defend  minimax\\n\"\n",
    "      \"                        (avg)   (avg)   (avg)            (num)\")\n",
    "for name, game in games:\n",
    "    print(name)\n",
    "    state = initial_state\n",
    "    bid_final = []\n",
    "\n",
    "    queue = deque()\n",
    "    queue.append(state)\n",
    "\n",
    "    while queue:\n",
    "        state = queue.popleft()\n",
    "        legal = game.legal_actions(state)\n",
    "        bid_final.extend(game.next_state(state, action) for action in legal\n",
    "                         if action == 'pickup' or action.startswith('declare'))\n",
    "        queue.extend(game.next_state(state, action) for action in legal if action == 'pass')\n",
    "\n",
    "    for bid_state in bid_final:\n",
    "        tree = {}\n",
    "        sum_t, sum_oppo_t, sum_p, sum_oppo_p, minimax, num = resolve(bid_state, game, tree)\n",
    "\n",
    "        print(f'  maker: {bid_state[8]}, suit: {SUITS[bid_state[5] - 1]} --'\n",
    "              f'  {sum_t/num:0.3f}   {sum_p/num:0.3f}   {sum_oppo_p/num:0.3f}        {minimax}   {num}')\n",
    "\n",
    "print('')"
   ]
  },
  {
   "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}