Geschwindigkeits-Hinweis

Cluedo / Clue ist ein klassisches Brettspiel mit einer überzeugenden Deduktions-Gameplay-Komponente. Speed ​​Clue ist eine 3-6-Spieler-Variante, die diese Komponente hervorhebt, indem sie nur die Karten verwendet. Das Ergebnis ist, dass der einzige Unterschied zwischen Standard Cluedo und Speed ​​Clue darin besteht, dass jeder Spieler, der noch im Spiel ist, einen beliebigen Vorschlag machen kann, anstatt darauf zu warten, einen bestimmten Raum zu erreichen, der Würfeln und den Vorschlägen anderer Spieler ausgeliefert ist. Wenn Sie Cluedo noch nie gespielt haben oder sich der expliziten Unterschiede zwischen den beiden Versionen sicher sein möchten, finden Sie hier möglicherweise einen vollständigen Regelsatz für Geschwindigkeitsinformationen .

Tor

Schreiben und senden Sie ein AI-Programm, um Speed ​​Clue vor dem 15. Mai 2014 um 00:00 Uhr GMT zu spielen. Nach dieser Zeit werde ich ein Turnier mit allen zulässigen Einträgen durchführen. Der Teilnehmer, dessen KI die meisten Spiele des Turniers gewinnt, gewinnt die Herausforderung.

AI-Spezifikationen

Sie können Ihre KI in so gut wie jeder Sprache schreiben, unabhängig von den verwendeten Techniken, sofern das Anwendungsprotokoll für das Spielen mit dem Server über eine TCP / IP-Verbindung verwendet wird. Eine ausführliche Erläuterung aller Einschränkungen finden Sie hier .

Spielanleitung

Beginnen Sie, indem Sie das GitHub-Repository des Wettbewerbs teilen . Fügen Sie unter dem entriesVerzeichnis mit Ihrem StackExchange-Benutzernamen ein Verzeichnis hinzu , und entwickeln Sie den Code in diesem Ordner. Wenn Sie bereit sind, Ihren Eintrag einzureichen, stellen Sie eine Pull-Anfrage mit Ihren Überarbeitungen und befolgen Sie diese Anweisungen, um Ihren Eintrag auf dieser Site bekannt zu geben.

Ich habe Code und JARs im coreVerzeichnis bereitgestellt , um Ihnen den Einstieg zu erleichtern . Eine grobe Anleitung für die Materialien finden Sie auf meiner Website . Darüber hinaus übermitteln andere Spieler zusätzlich zu ihren Einträgen einen Hilfecode, um Ihnen den Einstieg zu erleichtern. Nehmen Sie sich etwas Zeit, um die Einträge zu untersuchen, und vergessen Sie nicht, Ihren Eintrag mit den Einträgen anderer zu vergleichen, bevor Sie ihn einreichen!

Ergebnisse

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: ""

Die obigen Ergebnisse zeigen den Gewinnanteil jeder qualifizierten KI an den 25.200 gültigen Spielen, an denen sie teilgenommen hat. Es gab insgesamt 30.000 Spiele, die für die Ergebnisse angerechnet wurden, und 6.100 wurden abgezinst, als 01die Qualifikation disqualifiziert wurde.

Eine lobende Erwähnung muss an Rays 01KI gehen. Meine ersten Tests zeigten, dass es das stärkste war und ich erwartete, dass es die Konkurrenz gewinnen würde. Es scheint jedoch einen sehr sporadischen Fehler zu geben, der meines Erachtens dazu führt, dass alle möglichen Lösungen beseitigt werden. Das Turnier hatte alle 3-Spieler-Matches beendet und die 4-Spieler-Matches (12.000 Partien!) Gestartet, als 01der Bug aufgedeckt wurde. Wenn ich nur die 3-Spieler-Rangliste betrachte, sehen die Ergebnisse so aus:

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%

Ich hatte vor, Data Mining für die Ergebnisse durchzuführen, bin aber erschöpft. Ich hatte technische Probleme damit, die Konkurrenz vollständig zum Laufen zu bringen (Stromausfälle, Systemneustarts), was es erforderlich machte, den Contest-Server komplett neu zu schreiben, um seinen Fortschritt zu speichern. Ich werde alle Änderungen am Code mit allen Ergebnisdateien kommentieren und festschreiben, die generiert wurden, falls noch jemand daran interessiert ist. Wenn ich mich auch für das Data Mining entscheide, werden meine Ergebnisse auch zum Repository hinzugefügt.

Danke fürs Spielen!

AI01 - Python 3

Ich kann noch keinen besseren Namen dafür finden :-P.

Kennung : ray-ai01

Technologie : Python 3

Ausgewählt : ja

Argumente :ai01.py identifier port

Beschreibung : Arbeiten durch Inferenz. Wenn die Anzahl der Karten, deren Besitzer nicht bekannt ist, einen bestimmten Schwellenwert unterschreitet, beseitigt diese KI alle unmöglichen Lösungen durch rekursive globale Inferenz. Andernfalls wird die lokale Inferenz verwendet.

#!/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)

Den AI-Code finden Sie hier .

SimpleCluedoPlayer.java

Diese Klasse verwendet AbstractCluedoPlayer, die alle E / A behandelt und die Logik mit einer einfachen typisierten Schnittstelle arbeiten lässt. Das Ganze ist auf Github .

Dies schlägt den zufälligen Spieler mit hoher Wahrscheinlichkeit (im schlimmsten Fall sind es 15 Vorschläge, während der zufällige Spieler durchschnittlich 162 nimmt), aber es wird leicht geschlagen. Ich biete es an, um den Ball ins Rollen zu bringen.

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);
        }
    }
}

SpockAI

Kennung: gamecoder-SpockAI

Repo-Eintrag: hier klicken

Ausgewählt: Ja

Technologie: Java 7 basiert aufcom.sadakatsu.clue.jar

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

Beschreibung:

SpockAIist ein Speed ​​Clue-Spieler, der auf einer Klasse basiert Knowledge, die ich geschrieben habe. Die KnowledgeKlasse repräsentiert alle möglichen Zustände, die das Spiel bisher hätte liefern können. Es stellt die Lösungen des Spiels und die möglichen Hände der Spieler als Sätze dar und verwendet iterative Abzüge, um diese Sätze jedes Mal, wenn etwas gelernt wird, so weit wie möglich zu reduzieren. SpockAIVerwendet diese Klasse, um zu bestimmen, welche Vorschläge die hilfreichsten Worst-Case-Ergebnisse liefern, und wählt zufällig einen dieser Vorschläge aus. Wenn ein Vorschlag widerlegt werden muss, wird versucht, entweder eine Karte zu zeigen, die die vorschlagende KI bereits gezeigt hat, oder eine Karte aus der Kategorie, für die die Möglichkeiten am wenigsten reduziert wurden. Es macht nur dann einen Vorwurf, wenn es die Lösung kennt.

Die Heuristik, mit der ich den besten Vorschlag ermittelt habe, lautet wie folgt. Nachdem alle Informationen aus einem Vorschlag gelernt wurden, wurden die mögliche Lösung und die möglichen Spielerhandsätze reduziert (es sei denn, der Vorschlag enthüllt keine neuen Informationen). Theoretisch ist der beste Vorschlag derjenige, der die Anzahl der möglichen Lösungen am meisten reduziert. Bei einem Unentschieden gehe ich davon aus, dass ein Vorschlag, der die Anzahl der möglichen Hände für die Spieler am meisten verringert, besser ist. Deshalb versuche ich für jeden Vorschlag jedes mögliche Ergebnis, das nicht zu einem Widerspruch im Wissen führt. Es wird davon ausgegangen, dass das Ergebnis des Vorschlags das Ergebnis ist, das die geringste Verbesserung der Lösungs- / Handzählung aufweist. Dann vergleiche ich alle Ergebnisse der Vorschläge und wähle aus, welches das beste Ergebnis erzielt. Auf diese Weise garantiere ich einen optimalen Informationsgewinn im ungünstigsten Fall.

Ich denke darüber nach, eine Brute-Force-Kombinationsanalyse möglicher Lösungen und möglicher Spielerhände hinzuzufügen, um SpockAInoch stärker zu werden, aber da dies SpockAIbereits der langsamste und ressourcenintensivste Eintrag ist, werde ich das wahrscheinlich überspringen.

Haftungsausschluss:

Ich hatte vor Wochen vor, eine KI für diesen Wettbewerb zu veröffentlichen. So wie es aussieht, konnte ich erst am Freitag der letzten Woche mit dem Schreiben meiner KI beginnen und fand immer wieder lächerliche Fehler in meinem Code. Aus diesem Grund war die einzige Möglichkeit SpockAI, vor Ablauf der Frist zur Arbeit zu kommen , die Verwendung eines großen Thread-Pools. Das Endergebnis ist, dass (derzeit) SpockAI + 90% CPU-Auslastung und 2 GB + Speicherauslastung erreichen kann (obwohl ich den Garbage Collector dafür verantwortlich mache). Ich habe vor, SpockAIam Wettbewerb teilzunehmen, aber wenn andere meinen, dies verstoße gegen die Regeln , werde ich den Titel "Gewinner" vergeben, um den zweiten Platz zu SpockAIgewinnen. Wenn Sie so denken, hinterlassen Sie bitte einen Kommentar zu dieser Antwort.

InferencePlayer.java

Vollständiger Code auf Github (Hinweis: Dies verwendet den gleichen CodeAbstractCluedoPlayer wie zuvor SimpleCluedoPlayer).

Der wahre Kern dieses Spielers ist seine PlayerInformationKlasse (hier leicht beschnitten):

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;
    }
}

Es vereint Informationen zu Vorschlägen, die der Spieler nicht widerlegt hat (was darauf hinweist, dass er keine dieser Karten besitzt), Vorschläge, die er widerlegt hat (was darauf hinweist, dass er mindestens eine dieser Karten besitzt) und Karten, deren Position sicher ist. Anschließend werden iterativ einige Grundregeln angewendet, um diese Informationen zu ihrer Essenz zu verdichten.

Ich glaube nicht, dass es mehr deterministische Informationen gibt (außer durch falsche Anschuldigungen, die ich für zu selten halte), obwohl ich vielleicht etwas übersehen habe. Es besteht die Möglichkeit, dass ein fortgeschrittener Spieler die Wahrscheinlichkeiten abschätzt, mit denen Spieler X Karte Y hat.

Der andere Bereich, der wahrscheinlich eine signifikante Verbesserung zulässt, ist die Entscheidung, welcher Vorschlag gemacht werden soll. Ich versuche, den Informationsgewinn mit einem ziemlich klobigen Ansatz zu maximieren, aber es gibt eine Menge schlecht begründeter Heuristiken bei der Bewertung der relativen Vorzüge des Wissens, das aus verschiedenen hypothetischen Widerlegungen gewonnen wurde. Ich werde jedoch nicht versuchen, die Heuristik zu optimieren, bis jemand anderes einen würdigen Gegner postet.

CluePaddle (ClueStick / ClueBat / ClueByFour) - C #

Ich habe ClueBot geschrieben, einen C # -Client, für den es einfach ist, AIs zu implementieren, und verschiedene AIs, einschließlich des schwerwiegendsten Versuchs namens CluePaddle. Der Code befindet sich unter https://github.com/jwg4/SpeedClueContest/tree/clue_paddle. Eine Pull-Anforderung wurde gestartet, um den Code in den Upstream zusammenzuführen.

ClueStick ist ein Proof-of-Concept, bei dem die meisten Vorgänge nur erraten und ignoriert werden. ClueBat ist eine andere blöde KI, außer dass sie versucht, einen Fehler in ClueStick auszunutzen, um ihn zu falschen Anschuldigungen zu zwingen. ClueByFour ist insofern eine vernünftige KI, als sie vernünftige Vorschläge macht und sich an die Karten erinnert, die von anderen gezeigt werden.

CluePaddle ist das intelligenteste. Es wird versucht herauszufinden, wer was hat, und zwar nicht nur basierend auf den angebotenen Disproofs, sondern auch basierend darauf, welche Spieler keinen Disproof für einen bestimmten Vorschlag angeboten haben. Es wird nicht berücksichtigt, wie viele Karten jeder Spieler hat, dies muss jedoch behoben werden. Es enthält ein paar ziemlich lange Klassen, so dass ich hier nicht den gesamten Code posten werde, aber die folgende Methode gibt einen Vorgeschmack.

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);
  }
}

Wenn die 4 gegeneinander spielen, gewinnt CluePaddle mit Abstand die meisten Spiele, wobei ClueByFour an zweiter Stelle und die beiden anderen nirgendwo stehen.

Nur CluePaddle ist (bisher) ein Wettbewerbsbeitrag. Verwendung:

CluePaddle.exe identifier port

Wenn jemand anderes eine C # AI erstellen möchte, erstellen Sie einfach ein ConsoleApplication-Projekt in der Lösung, implementieren Sie die IClueAISchnittstelle in einer Klasse und Programleiten Sie dann die Aufgaben ProgramTemplateder anderen Projekte ab und kopieren Sie sie Main(). Die einzige Abhängigkeit ist NUnit für Komponententests, und Sie können problemlos alle Tests aus dem Code entfernen (installieren Sie NUnit jedoch nicht).