Tri Peaks AI

tripeaks.py

"""A small script that implements a Tri Peaks game as well as a Tri Peaks
approximate solver. The solver uses several heuristics to make moves, that a
human would be able to perform.

More information at https://en.wikipedia.org/Tri_Peaks_(game)

Solver improvement idea: take into account the probability of uncovering a card
that would increase the popping sequence length.

Architecture improvement idea: use a TriPeaksState class to store information
relative to the game state, that can be easily parsed from a real game
screenshot and passed as an argument to the solver.

by Yohan Chalier (https://yohan.chalier.fr)
on December 24, 2019
"""

import enum
import random
import functools


@enum.unique
class CardColor(enum.Enum):
    """Color of a playing card."""

    SPADES = 0
    HEARTS = 1
    CLUBS = 2
    DIAMONDS = 3


@enum.unique
class CardValue(enum.Enum):
    """Value of a playing card."""

    TWO = 0
    THREE = 1
    FOUR = 2
    FIVE = 3
    SIX = 4
    SEVEN = 5
    EIGHT = 6
    NINE = 7
    TEN = 8
    JACK = 9
    QUEEN = 10
    KING = 11
    ACE = 12


@functools.total_ordering
class Card:
    """Representation of a playing card."""

    def __init__(self, color, value):
        self.color = color
        self.value = value

    def __eq__(self, other):
        return self.color == other.color\
            and self.value == other.value

    def __lt__(self, other):
        return self.value.value < other.value.value

    def __repr__(self):
        color_map = {
            CardColor.SPADES: "♠",
            CardColor.HEARTS: "♥",
            CardColor.CLUBS: "♣",
            CardColor.DIAMONDS: "♦",
        }
        value_map = {
            CardValue.TWO: "2",
            CardValue.THREE: "3",
            CardValue.FOUR: "4",
            CardValue.FIVE: "5",
            CardValue.SIX: "6",
            CardValue.SEVEN: "7",
            CardValue.EIGHT: "8",
            CardValue.NINE: "9",
            CardValue.TEN: "X",
            CardValue.JACK: "J",
            CardValue.QUEEN: "Q",
            CardValue.KING: "K",
            CardValue.ACE: "A"
        }
        return value_map[self.value] + color_map[self.color]


def generate_deck():
    """Generate a 52 cards deck."""
    return [
        Card(color, value)
        for color in CardColor
        for value in CardValue
    ]


PARENTS_MAP = {
    1: [],
    2: [],
    3: [],
    4: [1],
    5: [1],
    6: [2],
    7: [2],
    8: [3],
    9: [3],
    10: [4],
    11: [4, 5],
    12: [5],
    13: [6],
    14: [6, 7],
    15: [7],
    16: [8],
    17: [8, 9],
    18: [9],
    19: [10],
    20: [10, 11],
    21: [11, 12],
    22: [12],
    23: [13],
    24: [13, 14],
    25: [14, 15],
    26: [15],
    27: [16],
    28: [16, 17],
    29: [17, 18],
    30: [18],
}


CHILDREN_MAP = dict()
for k, v in PARENTS_MAP.items():
    CHILDREN_MAP.setdefault(k, list())
    for vv in v:
        CHILDREN_MAP.setdefault(vv, list())
        CHILDREN_MAP[vv].append(k)


PLACEHOLDER = """
      %s             %s             %s
    %s  %s         %s  %s         %s  %s
  %s  %s  %s     %s  %s  %s     %s  %s  %s
%s  %s  %s  %s %s  %s  %s  %s %s  %s  %s  %s

   Deck (%d):   %s
"""


class IllegalMove(Exception):
    """The player tried to make a move that the game rules do not allow."""


class LossEnd(Exception):
    """The TriPeaks game is lost."""


def valid_pair(card_a, card_b):
    """Return True iif. card A and card B values are sequential."""
    if card_a.value == card_b.value:
        return False
    if card_a > card_b:
        return valid_pair(card_b, card_a)
    if card_a.value.value + 1 == card_b.value.value:
        return True
    if card_a.value == CardValue.TWO and card_b.value == CardValue.ACE:
        return True
    return False


class TriPeaksNode:
    """Logical location of a card within the game."""

    def __init__(self, position, card):
        self.position = position
        self.card = card
        self.revealed = False
        self.popped = False

    def __eq__(self, other):
        return self.position == other.position

    def __lt__(self, other):
        return self.position < other.position

    def __str__(self):
        if self.popped:
            return "  "
        if not self.revealed:
            return "**"
        return str(self.card)

    def __hash__(self):
        return self.position


class SequenceNode:
    """A move in a sequence of possible moves."""

    def __init__(self, position, card, popables):
        self.position = position
        self.card = card
        self.popables = popables
        self.children = list()

    def __repr__(self):
        return str(self.card)

    def __str__(self, indent=0):
        text = "|\t" * indent + str(self.card)
        for children in self.children:
            text += "\n" + children.__str__(indent + 1)
        return text

    def depth(self):
        """Return the length of the longest sequence starting from this move."""
        children_depth = [child.depth() for child in self.children]
        if len(children_depth) == 0:
            return 1
        return 1 + max(children_depth)

    def discovered(self, tri_peaks, prefix=None):
        """Return the maximal number of discovered nodes starting from this
        move."""
        if prefix is None:
            prefix = list()
        if len(self.children) == 0:
            score = 0
            popped = set()
            for node in tri_peaks.nodes.values():
                if node.popped:
                    popped.add(node.position)
            predict_popped = frozenset(popped.union(prefix + [self.position]))
            for node in tri_peaks.nodes.values():
                if node.revealed or node.popped:
                    continue
                if len(set(CHILDREN_MAP[node.position])
                       .difference(predict_popped)) == 0:
                    score += 1
            return score
        return max([
            child.discovered(tri_peaks, prefix + [self.position])
            for child in self.children
        ])


class TriPeaks:
    """Representation of the TriPeaks game."""

    def __init__(self):
        self.deck = generate_deck()
        random.shuffle(self.deck)
        self.nodes = {
            i: TriPeaksNode(i, self.deck.pop())
            for i in range(1, 31)
        }
        for i in range(19, 31):
            self.nodes[i].revealed = True
        self.waste = self.deck.pop()
        self.remaining = len(self.nodes)

    def __str__(self):
        return PLACEHOLDER % tuple(
            sorted(self.nodes.values())
            + [len(self.deck), self.waste]
        )

    def _pop(self, position):
        if not self.nodes[position].revealed:
            raise IllegalMove()
        if self.nodes[position].popped:
            raise IllegalMove()
        if not valid_pair(self.nodes[position].card, self.waste):
            raise IllegalMove()
        self.nodes[position].popped = True
        for parent in PARENTS_MAP[position]:
            free = True
            for children in CHILDREN_MAP[parent]:
                free = free and (self.nodes[children].popped)
            if free:
                self.nodes[parent].revealed = True
        self.waste = self.nodes[position].card
        self.remaining -= 1

    def _draw(self):
        if len(self.deck) == 0:
            raise LossEnd
        self.waste = self.deck.pop()

    def _play(self, input_function, display):
        while self.remaining > 0:
            if display:
                print(self)
            next_move = input_function()
            try:
                if next_move is None:
                    self._draw()
                else:
                    self._pop(next_move)
            except LossEnd:
                if display:
                    print("You lost.")
                return False
        if display:
            print("You won.")
        return True

    def find_sequences(self):
        """Return the best move to make next."""
        popables = set(
            (position, node)
            for position, node in self.nodes.items()
            if node.revealed and not node.popped
        )
        root = SequenceNode(None, self.waste, popables)
        buffer = [root]
        while len(buffer) > 0:
            sequence_node = buffer.pop(0)
            for position, tri_peaks_node in sequence_node.popables:
                if valid_pair(sequence_node.card, tri_peaks_node.card):
                    child = SequenceNode(
                        position,
                        tri_peaks_node.card,
                        sequence_node.popables
                        .difference([(position, tri_peaks_node)])
                    )
                    sequence_node.children.append(child)
                    buffer.append(child)
        next_moves = [
            (seq_node, seq_node.depth(), seq_node.discovered(self))
            for seq_node in root.children
        ]
        next_moves.sort(key=lambda x: (-x[1], -x[2]))
        if len(next_moves) == 0:
            return None
        return next_moves[0][0].position

    def human_play(self, display=True):
        """Start a game with human interation."""
        def input_function():
            choice = input("Next move > ")
            if choice == "":
                return None
            return int(choice)
        return self._play(input_function, display)

    def computer_play(self, display=True):
        """Start a game using the solver."""
        return self._play(self.find_sequences, display)


def manual_test():
    """Start a game with human interaction."""
    TriPeaks().human_play()


def computer_test():
    """Start a game using the solver."""
    TriPeaks().computer_play()


def estimate_win_rate(rounds=1000):
    """Compute an empirical estimation of the solver winning rate."""
    stats = {False: 0, True: 0}
    for _ in range(rounds):
        stats[TriPeaks().computer_play(display=False)] += 1
    return stats[True] / (stats[False] + stats[True])