23
\$\begingroup\$

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!

\$\endgroup\$
  • 4
    \$\begingroup\$ Can you make a copy of your server available for entrants to test against? \$\endgroup\$ – Peter Taylor Apr 13 '14 at 12:55
  • \$\begingroup\$ you must accept two port numbers: the first will be the port to which your program will listen, and the second will be the port to which your program will send., Why two ports? \$\endgroup\$ – Hasturkun Apr 13 '14 at 13:30
  • 1
    \$\begingroup\$ @PeterTaylor, I will make a copy of the server available as soon as I have written it. Why do you think I am giving a month? ;) \$\endgroup\$ – sadakatsu Apr 13 '14 at 18:19
  • \$\begingroup\$ @Hasturkun, The architecture I have planned for the server is that it will start your submissions via command line. It will choose which port each program will use to send it messages so that it can easily identify which program is which (note that the protocol does not include any identifiers). In addition, each program needs to know to which port to send messages so that the server can actually receive messages. These are the two ports that each submission must receive as command line arguments. \$\endgroup\$ – sadakatsu Apr 13 '14 at 18:24
  • 1
    \$\begingroup\$ The only networking program I have written uses UDP. I decided to use TCP/IP to (1) get to understand any differences between the two and (2) to use the technology that best supports the lock-step player updates I need for this to work. \$\endgroup\$ – sadakatsu Apr 14 '14 at 3:29
5
\$\begingroup\$

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) >= 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 < 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) >= 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 & 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 & 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] > 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.

\$\endgroup\$
  • \$\begingroup\$ Could you make a pull request with your AI? I'd like to get it into the contest repo. \$\endgroup\$ – sadakatsu May 3 '14 at 14:13
  • \$\begingroup\$ @gamecoder I've made a stronger AI01 and sent a pull request. \$\endgroup\$ – Ray May 3 '14 at 15:39
  • 1
    \$\begingroup\$ As things currently stand, your 01 is the strongest. In the trials I run, it consistently wins ~67% of the matches in which it competes. I'm hoping we'll see some solid entries before the contest ends that can challenge it. \$\endgroup\$ – sadakatsu May 6 '14 at 4:49
  • \$\begingroup\$ Check out my SpockAI. It performs pretty well against 01. I don't know whether it will win the competition, but I'm glad to see your win count reduced ; ) \$\endgroup\$ – sadakatsu May 14 '14 at 16:49
  • \$\begingroup\$ @gamecoder Actually, I've updated my AI several days ago according to the new rules. I'm glad to see your new entry. It seems to perform well but I didn't test it many times due to it's inefficient. Maybe you can make it faster so that we are easier to test. \$\endgroup\$ – Ray May 14 '14 at 17:35
4
\$\begingroup\$

SimpleCluedoPlayer.java

This class uses AbstractCluedoPlayer, which handles all the I/O and lets the logic work with a simple typed interface. The whole thing is on github.

This beats the random player with high probability (in the worst case it takes 15 suggestions, whereas the random player takes an average of 162), but it will be easily beaten. I offer it to get the ball rolling.

package org.cheddarmonk.cluedoai;

import java.io.IOException;
import java.io.PrintStream;
import java.net.UnknownHostException;
import java.util.*;

/**
 * A simple player which doesn't try to make inferences from partial information.
 * It merely tries to maximise the information gain by always making suggestions involving cards which
 * it does not know to be possessed by a player, and to minimise information leakage by recording who
 * has seen which of its own cards.
 */
public class SimpleCluedoPlayer extends AbstractCluedoPlayer {
    private Map<CardType, Set<Card>> unseenCards;
    private Map<Card, Integer> shownBitmask;
    private Random rnd = new Random();

    public SimpleCluedoPlayer(String identifier, int serverPort) throws UnknownHostException, IOException {
        super(identifier, serverPort);
    }

    @Override
    protected void handleReset() {
        unseenCards = new HashMap<CardType, Set<Card>>();
        for (Map.Entry<CardType, Set<Card>> e : Card.byType.entrySet()) {
            unseenCards.put(e.getKey(), new HashSet<Card>(e.getValue()));
        }

        shownBitmask = new HashMap<Card, Integer>();
        for (Card myCard : myHand()) {
            shownBitmask.put(myCard, 0);
            unseenCards.get(myCard.type).remove(myCard);
        }
    }

    @Override
    protected Suggestion makeSuggestion() {
        return new Suggestion(
            selectRandomUnseen(CardType.SUSPECT),
            selectRandomUnseen(CardType.WEAPON),
            selectRandomUnseen(CardType.ROOM));
    }

    private Card selectRandomUnseen(CardType type) {
        Set<Card> candidates = unseenCards.get(type);
        Iterator<Card> it = candidates.iterator();
        for (int idx = rnd.nextInt(candidates.size()); idx > 0; idx--) {
            it.next();
        }
        return it.next();
    }

    @Override
    protected Card disproveSuggestion(int suggestingPlayerIndex, Suggestion suggestion) {
        Card[] byNumShown = new Card[playerCount()];
        Set<Card> hand = myHand();
        int bit = 1 << suggestingPlayerIndex;
        for (Card candidate : suggestion.cards()) {
            if (!hand.contains(candidate)) continue;

            int bitmask = shownBitmask.get(candidate);
            if ((bitmask & bit) == bit) return candidate;
            byNumShown[Integer.bitCount(bitmask)] = candidate;
        }

        for (int i = byNumShown.length - 1; i >= 0; i--) {
            if (byNumShown[i] != null) return byNumShown[i];
        }

        throw new IllegalStateException("Unreachable");
    }

    @Override
    protected void handleSuggestionResponse(Suggestion suggestion, int disprovingPlayerIndex, Card shown) {
        if (shown != null) unseenCards.get(shown.type).remove(shown);
        else {
            // This player never makes a suggestion with cards from its own hand, so we're ready to accuse.
            unseenCards.put(CardType.SUSPECT, Collections.singleton(suggestion.suspect));
            unseenCards.put(CardType.WEAPON, Collections.singleton(suggestion.weapon));
            unseenCards.put(CardType.ROOM, Collections.singleton(suggestion.room));
        }
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, Card shown) {
        shownBitmask.put(shown, shownBitmask.get(shown) | (1 << suggestingPlayerIndex));
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, int disprovingPlayerIndex) {
        // Do nothing.
    }

    @Override
    protected Suggestion makeAccusation() {
        Set<Card> suspects = unseenCards.get(CardType.SUSPECT);
        Set<Card> weapons = unseenCards.get(CardType.WEAPON);
        Set<Card> rooms = unseenCards.get(CardType.ROOM);
        if (suspects.size() * weapons.size() * rooms.size()  == 1) {
            return new Suggestion(suspects.iterator().next(), weapons.iterator().next(), rooms.iterator().next());
        }

        return null;
    }

    @Override
    protected void recordAccusation(int accusingPlayer, Suggestion accusation, boolean correct) {
        // Do nothing.
    }

    //*********************** Public Static Interface ************************//
    public static void main(String[] args) throws Exception {
        try {
            System.setOut(new PrintStream("/tmp/speed-cluedo-player" + args[0]+".log"));
            new SimpleCluedoPlayer(args[0], Integer.parseInt(args[1])).run();
        } catch (Throwable th) {
            th.printStackTrace(System.out);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Very nice, clean code. I doubt anyone looking at the test server or random player feel that way. I also think that you can't have a simpler AI than this ^_^ \$\endgroup\$ – sadakatsu Apr 18 '14 at 16:54
3
\$\begingroup\$

InferencePlayer.java

Full code on Github (note: this uses the same AbstractCluedoPlayer as my earlier SimpleCluedoPlayer).

The true core of this player is its PlayerInformation class (here slightly trimmed):

private static class PlayerInformation {
    final PlayerInformation[] context;
    final int playerId;
    final int handSize;
    Set<Integer> clauses = new HashSet<Integer>();
    Set<Card> knownHand = new HashSet<Card>();
    int possibleCards;
    boolean needsUpdate = false;

    public PlayerInformation(PlayerInformation[] context, int playerId, boolean isMe, int handSize, Set<Card> myHand) {
        this.context = context;
        this.playerId = playerId;
        this.handSize = handSize;
        if (isMe) {
            knownHand.addAll(myHand);
            possibleCards = 0;
            for (Card card : knownHand) {
                int cardMask = idsByCard.get(card);
                clauses.add(cardMask);
                possibleCards |= cardMask;
            }
        }
        else {
            possibleCards = allCardsMask;
            for (Card card : myHand) {
                possibleCards &= ~idsByCard.get(card);
            }

            if (playerId == -1) {
                // Not really a player: this represents knowledge about the solution.
                // The solution contains one of each type of card.
                clauses.add(suspectsMask & possibleCards);
                clauses.add(weaponsMask & possibleCards);
                clauses.add(roomsMask & possibleCards);
            }
        }
    }

    public void hasCard(Card card) {
        if (knownHand.add(card)) {
            // This is new information.
            needsUpdate = true;
            clauses.add(idsByCard.get(card));

            // Inform the other PlayerInformation instances that their player doesn't have the card.
            int mask = idsByCard.get(card);
            for (PlayerInformation pi : context) {
                if (pi != this) pi.excludeMask(mask);
            }

            if (knownHand.size() == handSize) {
                possibleCards = mask(knownHand);
            }
        }
    }

    public void excludeMask(int mask) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        if ((mask & possibleCards) != 0) {
            // The fact that we have none of the cards in the mask contains some new information.
            needsUpdate = true;
            possibleCards &= ~mask;
        }
    }

    public void disprovedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        // Exclude cards which we know the player doesn't have.
        needsUpdate = clauses.add(mask(suggestion.cards()) & possibleCards);
    }

    public void passedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        excludeMask(mask(suggestion.cards()));
    }

    public boolean update() {
        if (!needsUpdate) return false;

        needsUpdate = false;

        // Minimise the clauses, step 1: exclude cards which the player definitely doesn't have.
        Set<Integer> newClauses = new HashSet<Integer>();
        for (int clause : clauses) {
            newClauses.add(clause & possibleCards);
        }
        clauses = newClauses;

        if (clauses.contains(0)) throw new IllegalStateException();

        // Minimise the clauses, step 2: where one clause is a superset of another, discard the less specific one.
        Set<Integer> toEliminate = new HashSet<Integer>();
        for (int clause1 : clauses) {
            for (int clause2 : clauses) {
                if (clause1 != clause2 && (clause1 & clause2) == clause1) {
                    toEliminate.add(clause2);
                }
            }
        }
        clauses.removeAll(toEliminate);

        // Every single-card clause is a known card: update knownHand if necessary.
        for (int clause : clauses) {
            if (((clause - 1) & clause) == 0) {
                Card singleCard = cardsById.get(clause);
                hasCard(cardsById.get(clause));
            }
        }

        // Every disjoint set of clauses of size equal to handSize excludes all cards not in the union of that set.
        Set<Integer> disjoint = new HashSet<Integer>(clauses);
        for (int n = 2; n <= handSize; n++) {
            Set<Integer> nextDisjoint = new HashSet<Integer>();
            for (int clause : clauses) {
                for (int set : disjoint) {
                    if ((set & clause) == 0) nextDisjoint.add(set | clause);
                }
            }
            disjoint = nextDisjoint;
        }

        for (int set : disjoint) excludeMask(~set);

        return true;
    }
}

It unifies information on suggestions which the player didn't disprove (indicating that they hold none of those cards), suggestions which they did disprove (indicating that they hold at least one of those cards), and cards whose location is certain. Then it iteratively applies some basic rules to compact that information into its essence.

I don't think there's any more deterministic information to be obtained (except from via false accusations, which I'm assuming to be too rare to bother with), although I may have overlooked something. There is potential for a more sophisticated player to estimate probabilities that player X has card Y...

The other area which probably admits significant improvement is in deciding which suggestion to make. I attempt to maximise the information gain using a fairly clunky heavy-force approach, but there's a lot of poorly justified heuristic in evaluating the relative merits of the knowledge gained from different hypothetical disproofs. However, I'm not going to try tuning the heuristics until someone else posts a worthy opponent.

\$\endgroup\$
  • \$\begingroup\$ I cannot get either your SimpleCluedoPlayer or your InferencePlayer to run. I ran ant in the "SpeedClueContest/entries/peter_taylor/" directory and successfully generated the JARs. I've tried relative and absolute paths to these JARs, passing them "identifier" and "portNumber" in that order, but the TestServer hangs waiting for the "identifier alive" message for each of them. I looked for and cannot find "/tmp/speed-cluedo-player"+identifier+".log". Have I messed up the process somehow? \$\endgroup\$ – sadakatsu Apr 21 '14 at 19:02
  • \$\begingroup\$ @gamecoder, I probably shouldn't hard-code /tmp. It should be a simple patch; I'll look into it shortly. \$\endgroup\$ – Peter Taylor Apr 21 '14 at 19:29
  • 1
    \$\begingroup\$ Your fix works; I've merged it into the repo. Now I get to read through InferencePlayer carefully to make sure there are enough differences between it and the LogicalAI I had started working on >___< \$\endgroup\$ – sadakatsu Apr 22 '14 at 1:02
  • \$\begingroup\$ Here comes your opponent :-) \$\endgroup\$ – Ray Apr 27 '14 at 18:57
  • \$\begingroup\$ @Ray, excellent. I'll try to dissect your AI and see how it differs from mine at some point: on a cursory glance, it seems to use a similar analysis. \$\endgroup\$ – Peter Taylor Apr 27 '14 at 20:43
3
+100
\$\begingroup\$

SpockAI

Identifier: gamecoder-SpockAI

Repo Entry: click here

Selected: Yes

Technology: Java 7 based upon com.sadakatsu.clue.jar

Arguments: {identifier} portNumber [logOutput: true|false]

Description:

SpockAI is a Speed Clue player built upon a class called Knowledge that I wrote. The Knowledge class represents all the possible states that the game could have given what has happened thus far. It represents the game's solutions and players' possible hands as sets, and uses iterative deductions to reduce these sets as far as possible every time something is learned. SpockAI uses this class to determine which suggestions are assured to have the most helpful worst-case results and randomly selects one of those suggestions on its turns. When it needs to disprove a suggestion, it tries to either show a card it has already shown the suggesting AI or to show it a card from the category for which it has reduced the possibilities the least. It only makes an accusation when it knows the solution.

The heuristic I used for determining the best suggestion is as follows. After all information has been learned from a suggestion, the possible solution and possible player hand sets will have been reduced (unless the suggestion reveals no new information). Theoretically, the best suggestion is the one that most reduces the number of possible solutions. In the case of a tie, I assume that a suggestion that most reduces the number of possible hands for players is better. So, for each suggestion, I try every possible outcome that does not lead to a contradiction in knowledge. Whichever outcome has the least improvement in solution/hand counts is assumed to be the result the suggestion will have. Then I compare all the suggestions' results, and pick which one has the best result. In this way, I guarantee optimal worst-case information gain.

I am considering adding a brute force combination analysis of possible solutions and possible player hands to make SpockAI even stronger, but since SpockAI is already the slowest, most resource-intensive entry, I will probably skip that.

Disclaimer:

I had intended to release an AI for this contest weeks ago. As it stands, I wasn't able to start writing my AI until Friday last week, and I kept finding ridiculous bugs in my code. Because of this, the only way I was able to get SpockAI to work before the deadline was to use a large thread pool. The end result is that (currently) SpockAI can hit +90% CPU utilization and 2GB+ memory usage (though I blame the garbage collector for this). I intend to run SpockAI in the contest, but if others feel that is a violation of the rules, I will award the title of "winner" to second place should SpockAI win. If you you feel this way, please leave a comment to that effect on this answer.

\$\endgroup\$
2
\$\begingroup\$

CluePaddle (ClueStick / ClueBat / ClueByFour) - C#

I have written ClueBot, a C# client for which it is straightforward to implement AIs, and various AIs, including the most serious attempt called CluePaddle. The code is at https://github.com/jwg4/SpeedClueContest/tree/clue_paddle with a pull request started to merge it into upstream.

ClueStick is a proof-of-concept which basically just guesses and ignores most of what happens. ClueBat is another stupid AI, except that it tries to exploit a flaw in ClueStick to force it to do false accusations. ClueByFour is a reasonable AI in that it makes reasonable suggestions and remembers the cards it is shown by others.

CluePaddle is the most intelligent. It tries to figure out who has what based not only on what disproofs have been offered, but also based on which players didn't offer a disproof of a given suggestion. It doesn't take into account how many cards each player has atm but this is to be fixed. It includes a couple of quite long classes so I won't post the whole code here, but the following method gives a flavor.

public void Suggestion(int suggester, MurderSet suggestion, int? disprover, Card disproof)
{
  List<int> nonDisprovers = NonDisprovers(suggester, disprover).ToList();

  foreach (var player in nonDisprovers)
  {
    m_cardTracker.DoesntHaveAnyOf(player, suggestion);
  }

  if (disprover != null && disproof == null)
  {
    // We know who disproved it but not what they showed.
    Debug.Assert(disprover != m_i, "The disprover should see the disproof");
    Debug.Assert(suggester != m_i, "The suggester should see the disproof");
    m_cardTracker.DoesntHaveAllOf(suggester, suggestion);
    m_cardTracker.HasOneOf((int)disprover, suggestion);
  }

  if (disproof != null)
  {
    // We know who disproved it and what they showed.
    Debug.Assert(disprover != null, "disproof is not null but disprover is null");
    m_cardTracker.DoesHave((int)disprover, disproof.Value);
  }
}

If the 4 play against each other, CluePaddle wins by far the most games, with ClueByFour second and the other two nowhere.

Only CluePaddle is a competitive entry (so far). Usage:

CluePaddle.exe identifier port

If anyone else wants to make a C# AI, just create a ConsoleApplication project in the soltution, implement the IClueAI interface in a class, and then make your Program derive from ProgramTemplate and copy what the other projects do for Main(). The only dependency is NUnit for unit testing and you could easily remove all the testing from the code (but don't, just install NUnit).

\$\endgroup\$
  • \$\begingroup\$ I have tried to compile your AIs and test them in the ContestServer (soon to be posted). The CluePaddle project does not compile, claiming that NUnit is not installed even though the other projects do compile. Those that do compile end up stalling during the testing, and Java reports a connection reset error. Could you help me determine whether I may have done something wrong? \$\endgroup\$ – sadakatsu May 6 '14 at 1:09
  • \$\begingroup\$ Correction: ClueStick is the only AI that stalls when I try to start it up. The other two compete in the trial tournament and eventually get disqualified for the same violations. ClueByFour gets disqualified for failing to repeat an undisproved suggestion it makes as an accusation when it does not hold any of the cards. ClueBat gets disqualified for making accusations that has cards it has either been shown or has in its hand. Please check out the revised AI restrictions to ensure compliance. \$\endgroup\$ – sadakatsu May 6 '14 at 4:42
  • \$\begingroup\$ @gamecoder Do you have NUnit installed? If you can't install it I can conditionally remove the unit testing code. CluePaddle is my actual entry - I am not too worried about the violations by the other two since they are not really playing to win. \$\endgroup\$ – jwg May 6 '14 at 5:48
  • \$\begingroup\$ I also have some updates to CluePaddle. I will do a pull request for these later. \$\endgroup\$ – jwg May 6 '14 at 5:50
  • \$\begingroup\$ I did install NUnit. I was able to explore its namespaces in MSVS using your other projects' references. I'll look forward to your pull request. \$\endgroup\$ – sadakatsu May 6 '14 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.