King of the Hill: Speed Clue AI Speed Clue

Cluedo/Clue is a classic board game with a compelling deduction gameplay
component.  Speed Clue is a 3-6 player variant that emphasizes this component by
using only the cards.  The result is that the only difference between standard
Cluedo and Speed Clue is that each player still in the game may make any
suggestion he pleases on his turn instead of waiting to reach a specific room at
the mercy of dice rolls and other players' suggestions.  If you have never
played Cluedo before, or want to be certain of the explicit differences between
the two versions, you may find a complete Speed Clue rule set here.



Goal

Write and submit an AI program to play Speed Clue before 15 May 2014 00:00 GMT.
After that time, I will run a tournament using all the legal entries.  The
entrant whose AI wins the most games in the tournament wins the challenge.



AI Specifications

You can write your AI in pretty much any language you choose, using whatever
techniques you use, so long as it strictly uses the application protocol
over a TCP/IP connection to play games with the server.  A detailed explanation
of all the restrictions can be found here.



How to Play

Start by forking the contest GitHub repository.  Add a directory under the
entries directory named using your StackExchange user name, and develop
your code in that folder.  When you are ready to submit your entry, make a pull
request with your revisions, then follow these instructions for announcing
your entry on this site.

I have provided some code and JARs in the core directory for getting you
started; see my site for a rough guide for the materials.  In addition,
other players are submitting helper code in addition to their entries to help
you get up and running.  Take some time to explore the entries, and don't forget
to test your entry against others' entries before submitting!



Results

Place | User         | AI                 | Result
------+--------------+--------------------+-------------------------------------------------------
    1 | gamecoder    | SpockAI            | 55.75%
    2 | Peter Taylor | InferencePlayer    | 33.06%
    3 | jwg          | CluePaddle         | 20.19%
    4 | Peter Taylor | SimpleCluedoPlayer |  8.34%
    5 | gamecoder    | RandomPlayer       |  1.71%
 ---- | ray          | 01                 | Player "ray-01" [3] sent an invalid accuse message: ""


The results above show the win percentage each qualified AI had of the 25,200 valid matches in which it participated.  There were 30,000 matches in total that counted toward the results, and 6,100 or so that were discounted when 01 was disqualified.

An honorable mention needs to go to ray's 01 AI.  My initial testing showed that it was the strongest, and I expected it to win the competition.  However, it appears to have a very intermittent bug that, as far as I can guess, leads it to eliminate all possible solutions.  The tournament had finished all the three-player matches and had started the four player matches (12,000 games in!) when 01's bug was revealed.  If I just consider the 3-player match standings, the results look like this:

Place | User         | AI                 | Result
------+--------------+--------------------+--------
    1 | ray          | 01                 | 72.10%
    2 | gamecoder    | SpockAI            | 51.28%
    3 | Peter Taylor | InferencePlayer    | 39.97%
    4 | Peter Taylor | SimpleCluedoPlayer | 17.65%
    5 | jwg          | CluePaddle         | 16.92%
    6 | gamecoder    | RandomPlayer       |  2.08%


I had planned on doing some data mining on the results, but I am exhausted.  I had technical difficulties in getting the competition to run all the way through (power failures, system reboots) that necessitated completely rewriting the contest server to save its progress as it proceeded.  I will comment and commit all the changes to the code with all the results files that were generated in case anyone is still interested.  If I decide to do the data mining as well, my results will also be added to the repository.



Thanks for Playing!
AI01 - Python 3

I can't find a better name for it yet :-P .

Identifier: ray-ai01

Technology: Python 3

Selected: yes

Arguments: ai01.py identifier port

Description: Work by inference. When the number of cards that the owner is not known is less than a threshold, this AI starts to eliminate all impossible solutions by recursive global inference. Otherwise, it use local inference.

#!/usr/bin/env python
import itertools

from speedclue.playerproxy import Player, main
from speedclue.cards import CARDS
from speedclue.protocol import BufMessager

# import crash_on_ipy


class Card:
    def __init__(self, name, type):
        self.name = name
        self.possible_owners = []
        self.owner = None
        self.in_solution = False
        self.disproved_to = set()
        self.type = type

    def __repr__(self):
        return self.name

    def log(self, *args, **kwargs):
        pass

    def set_owner(self, owner):
        assert self.owner is None
        assert self in owner.may_have
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.owner = owner
        owner.must_have.add(self)
        self.type.rest_count -= 1

    def set_as_solution(self):
        # import pdb; pdb.set_trace()
        assert self.owner is None
        self.type.solution = self
        self.in_solution = True
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.type.rest_count -= 1

    def __hash__(self):
        return hash(self.name)


class CardType:
    def __init__(self, type_id):
        self.type_id = type_id
        self.cards = [Card(name, self) for name in CARDS[type_id]]
        self.rest_count = len(self.cards)
        self.solution = None


class PlayerInfo:
    def __init__(self, id):
        self.id = id
        self.must_have = set()
        self.may_have = set()
        self.selection_groups = []
        self.n_cards = None

    def __hash__(self):
        return hash(self.id)

    def set_have_not_card(self, card):
        if card in self.may_have:
            self.may_have.remove(card)
            card.possible_owners.remove(self)

    def log(self, *args, **kwargs):
        pass

    def update(self):
        static = False
        updated = False
        while not static:
            static = True
            if len(self.must_have) == self.n_cards:
                if not self.may_have:
                    break
                for card in self.may_have:
                    card.possible_owners.remove(self)
                self.may_have.clear()
                static = False
                updated = True
            if len(self.must_have) + len(self.may_have) == self.n_cards:
                static = False
                updated = True
                for card in list(self.may_have):
                    card.set_owner(self)

            new_groups = []
            for group in self.selection_groups:
                group1 = []
                for card in group:
                    if card in self.must_have:
                        break
                    if card in self.may_have:
                        group1.append(card)
                else:
                    if len(group1) == 1:
                        group1[0].set_owner(self)
                        updated = True
                        static = False
                    elif group1:
                        new_groups.append(group1)
            self.selection_groups = new_groups

            if len(self.must_have) + 1 == self.n_cards:
                # There is only one card remain to be unknown, so this card must
                # be in all selection groups
                cards = self.may_have.copy()
                for group in self.selection_groups:
                    if self.must_have.isdisjoint(group):
                        cards.intersection_update(group)

                for card in self.may_have - cards:
                    static = False
                    updated = True
                    self.set_have_not_card(card)

        # assert self.must_have.isdisjoint(self.may_have)
        # assert len(self.must_have | self.may_have) &gt;= self.n_cards
        return updated


class Suggestion:
    def __init__(self, player, cards, dplayer, dcard):
        self.player = player
        self.cards = cards
        self.dplayer = dplayer
        self.dcard = dcard
        self.disproved = dplayer is not None


class AI01(Player):
    def prepare(self):
        self.set_verbosity(0)

    def reset(self, player_count, player_id, card_names):
        self.log('reset', 'id=', player_id, card_names)
        self.fail_count = 0
        self.suggest_count = 0
        self.card_types = [CardType(i) for i in range(len(CARDS))]
        self.cards = list(itertools.chain(*(ct.cards for ct in self.card_types)))
        for card in self.cards:
            card.log = self.log
        self.card_map = {card.name: card for card in self.cards}
        self.owned_cards = [self.card_map[name] for name in card_names]
        self.players = [PlayerInfo(i) for i in range(player_count)]
        for player in self.players:
            player.log = self.log
        self.player = self.players[player_id]
        for card in self.cards:
            card.possible_owners = list(self.players)
        n_avail_cards = len(self.cards) - len(CARDS)
        for player in self.players:
            player.may_have = set(self.cards)
            player.n_cards = n_avail_cards // player_count \
                + (player.id &lt; n_avail_cards % player_count)
        for card in self.owned_cards:
            card.set_owner(self.player)
        for card in self.cards:
            if card not in self.owned_cards:
                self.player.set_have_not_card(card)
        self.suggestions = []
        self.avail_suggestions = set(itertools.product(*CARDS))
        self.possible_solutions = {
            tuple(self.get_cards_by_names(cards)): 1
            for cards in self.avail_suggestions
        }
        self.filter_solutions()

    def filter_solutions(self):
        new_solutions = {}
        # assert self.possible_solutions
        join = next(iter(self.possible_solutions))
        for sol in self.possible_solutions:
            for card, type in zip(sol, self.card_types):
                if card.owner or type.solution and card is not type.solution:
                    # This candidate can not be a solution because it has a
                    # card that has owner or this type is solved.
                    break
            else:
                count = self.check_solution(sol)
                if count:
                    new_solutions[sol] = count
                    join = tuple(((x is y) and x) for x, y in zip(join, sol))
        self.possible_solutions = new_solutions
        updated = False
        for card in join:
            if card and not card.in_solution:
                card.set_as_solution()
                updated = True
                self.log('found new target', card, 'in', join)

        # self.dump()
        return updated

    def check_solution(self, solution):
        """
        This must be called after each player is updated.
        """
        players = self.players
        avail_cards = set(card for card in self.cards if card.possible_owners)
        avail_cards -= set(solution)
        if len(avail_cards) &gt;= 10:
            return 1
        count = 0

        def resolve_player(i, avail_cards):
            nonlocal count
            if i == len(players):
                count += 1
                return
            player = players[i]
            n_take = player.n_cards - len(player.must_have)
            cards = avail_cards &amp; player.may_have
            for choice in map(set, itertools.combinations(cards, n_take)):
                player_cards = player.must_have | choice
                for group in player.selection_groups:
                    if player_cards.isdisjoint(group):
                        # Invalid choice
                        break
                else:
                    resolve_player(i + 1, avail_cards - choice)

        resolve_player(0, avail_cards)
        return count

    def suggest1(self):
        choices = []
        for type in self.card_types:
            choices.append([])
            if type.solution:
                choices[-1].extend(self.player.must_have &amp; set(type.cards))
            else:
                choices[-1].extend(sorted(
                    (card for card in type.cards if card.owner is None),
                    key=lambda card: len(card.possible_owners)))

        for sgi in sorted(itertools.product(*map(lambda x:range(len(x)), choices)),
                key=sum):
            sg = tuple(choices[i][j].name for i, j in enumerate(sgi))
            if sg in self.avail_suggestions:
                self.avail_suggestions.remove(sg)
                break
        else:
            sg = self.avail_suggestions.pop()
            self.fail_count += 1
            self.log('fail')
        self.suggest_count += 1
        return sg

    def suggest(self):
        sg = []
        for type in self.card_types:
            card = min((card for card in type.cards if card.owner is None),
                key=lambda card: len(card.possible_owners))
            sg.append(card.name)
        sg = tuple(sg)

        if sg not in self.avail_suggestions:
            sg = self.avail_suggestions.pop()
        else:
            self.avail_suggestions.remove(sg)
        return sg

    def suggestion(self, player_id, cards, disprove_player_id=None, card=None):
        sg = Suggestion(
            self.players[player_id],
            self.get_cards_by_names(cards),
            self.players[disprove_player_id] if disprove_player_id is not None else None,
            self.card_map[card] if card else None,
        )
        self.suggestions.append(sg)
        # Iter through the non-disproving players and update their may_have
        end_id = sg.dplayer.id if sg.disproved else sg.player.id
        for player in self.iter_players(sg.player.id + 1, end_id):
            if player is self.player:
                continue
            for card in sg.cards:
                player.set_have_not_card(card)
        if sg.disproved:
            # The disproving player has sg.dcard
            if sg.dcard:
                if sg.dcard.owner is None:
                    sg.dcard.set_owner(sg.dplayer)
            else:
                # Add a selection group to the disproving player
                sg.dplayer.selection_groups.append(sg.cards)
            self.possible_solutions.pop(tuple(sg.cards), None)

        self.update()

    def update(self):
        static = False
        while not static:
            static = True
            for card in self.cards:
                if card.owner is not None or card.in_solution:
                    continue
                if len(card.possible_owners) == 0 and card.type.solution is None:
                    # In solution
                    card.set_as_solution()
                    static = False

            for type in self.card_types:
                if type.solution is not None:
                    continue
                if type.rest_count == 1:
                    card = next(card for card in type.cards if card.owner is None)
                    card.set_as_solution()
                    static = False

            for player in self.players:
                if player is self.player:
                    continue
                if player.update():
                    static = False

            if self.filter_solutions():
                static = False

    def iter_players(self, start_id, end_id):
        n = len(self.players)
        for i in range(start_id, start_id + n):
            if i % n == end_id:
                break
            yield self.players[i % n]

    def accuse(self):
        if all(type.solution for type in self.card_types):
            return [type.solution.name for type in self.card_types]
        possible_solutions = self.possible_solutions
        if len(possible_solutions) == 1:
            return next(possible_solutions.values())
        # most_possible = max(self.possible_solutions, key=self.possible_solutions.get)
        # total = sum(self.possible_solutions.values())
        # # self.log('rate:', self.possible_solutions[most_possible] / total)
        # if self.possible_solutions[most_possible] &gt; 0.7 * total:
        #     self.log('guess', most_possible)
        #     return [card.name for card in most_possible]
        return None

    def disprove(self, suggest_player_id, cards):
        cards = self.get_cards_by_names(cards)
        sg_player = self.players[suggest_player_id]
        cards = [card for card in cards if card in self.owned_cards]
        for card in cards:
            if sg_player in card.disproved_to:
                return card.name
        return max(cards, key=lambda c: len(c.disproved_to)).name

    def accusation(self, player_id, cards, is_win):
        if not is_win:
            cards = tuple(self.get_cards_by_names(cards))
            self.possible_solutions.pop(cards, None)
            # player = self.players[player_id]
            # for card in cards:
            #     player.set_have_not_card(card)
            # player.update()
        else:
            self.log('fail rate:', self.fail_count / (1e-8 + self.suggest_count))
            self.log('fail count:', self.fail_count, 'suggest count:', self.suggest_count)

    def get_cards_by_names(self, names):
        return [self.card_map[name] for name in names]

    def dump(self):
        self.log()
        for player in self.players:
            self.log('player:', player.id, player.n_cards,
                sorted(player.must_have, key=lambda x: x.name),
                sorted(player.may_have, key=lambda x: x.name),
                '\n    ',
                player.selection_groups)
        self.log('current:', [type.solution for type in self.card_types])
        self.log('possible_solutions:', len(self.possible_solutions))
        for sol, count in self.possible_solutions.items():
            self.log('  ', sol, count)
        self.log('id|', end='')

        def end():
            return ' | ' if card.name in [g[-1] for g in CARDS] else '|'

        for card in self.cards:
            self.log(card.name, end=end())
        self.log()
        for player in self.players:
            self.log(' *'[player.id == self.player.id] + str(player.id), end='|')
            for card in self.cards:
                self.log(
                    ' ' + 'xo'[player in card.possible_owners or player is card.owner],
                    end=end())
            self.log()


if __name__ == '__main__':
    main(AI01, BufMessager)


The AI code can be found here.