Wskazówka prędkości

Cluedo / Clue to klasyczna gra planszowa z nieodpartym elementem dedukcyjnym. Speed ​​Clue to wariant dla 3-6 graczy, który podkreśla ten element, używając tylko kart. W rezultacie jedyna różnica między standardowym Cluedo i Speed ​​Clue polega na tym, że każdy gracz, który nadal bierze udział w grze, może przedstawić w swojej turze wszelkie sugestie, które mu się podobają, zamiast czekać na dotarcie do określonego pokoju dzięki łasce rzutu kostką i sugestiom innych graczy. Jeśli nigdy wcześniej nie grałeś w Cluedo lub chcesz mieć pewność wyraźnych różnic między obiema wersjami, możesz znaleźć tutaj kompletną regułę Wskazówki prędkości .

Cel

Napisz i prześlij program AI, aby zagrać w Speed ​​Clue przed 15 maja 2014 r. 00:00 GMT. Po tym czasie poprowadzę turniej z wykorzystaniem wszystkich legalnych zgłoszeń. Uczestnik, którego AI wygra najwięcej gier w turnieju, wygrywa wyzwanie.

Specyfikacje AI

Możesz pisać swoją sztuczną inteligencję w prawie każdym wybranym języku, używając dowolnych technik, o ile tylko ściśle używa protokołu aplikacji przez połączenie TCP / IP do grania w gry z serwerem. Szczegółowe objaśnienie wszystkich ograniczeń można znaleźć tutaj .

Jak grać

Zacznij od rozwidlenia repozytorium GitHub konkursu . Dodaj katalog do entrieskatalogu nazwanego przy użyciu nazwy użytkownika StackExchange i opracuj kod w tym folderze. Kiedy będziesz gotowy, aby przesłać zgłoszenie, poproś o wycofanie ze swoimi poprawkami, a następnie postępuj zgodnie z tymi instrukcjami, aby ogłosić swój wpis na tej stronie.

Podałem trochę kodu i plików JAR w corekatalogu na początek; zapoznaj się z moją witryną, aby uzyskać przybliżony przewodnik po materiałach. Ponadto inni gracze przesyłają kod pomocnika oprócz swoich wpisów, aby pomóc ci rozpocząć pracę. Poświęć trochę czasu na zapoznanie się z wpisami i nie zapomnij przetestować wpisu pod kątem wpisów innych przed przesłaniem!

Wyniki

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

Powyższe wyniki pokazują procent wygranych, które każda zakwalifikowana AI miała z 25 200 ważnych meczów, w których uczestniczyła. W sumie było 30 000 meczów, które wliczały się do wyników, i 6100 lub więcej, które zostały zdyskontowane, gdy 01zostały zdyskwalifikowane.

Wyróżnienie musi znaleźć się w 01AI ray . Moje początkowe testy wykazały, że był najsilniejszy i spodziewałem się, że wygra konkurencję. Wydaje się jednak, że ma bardzo sporadyczny błąd, który, o ile mogę się domyślić, prowadzi go do wyeliminowania wszystkich możliwych rozwiązań. Turniej zakończył wszystkie trzyosobowe mecze i rozpoczął czteroosobowe mecze (12 000 meczów w!), Kiedy 01wykryto błąd. Jeśli wezmę pod uwagę tylko wyniki trzech graczy, wyniki wyglądają następująco:

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%

Planowałem przeprowadzić eksplorację danych dotyczących wyników, ale jestem wyczerpany. Miałem trudności techniczne z uruchomieniem konkurencji przez cały czas (awarie zasilania, ponowne uruchomienie systemu), co wymagało całkowitego przepisania serwera konkursowego w celu zapisania jego postępu. Skomentuję i zatwierdzę wszystkie zmiany w kodzie ze wszystkimi plikami wyników, które zostały wygenerowane na wypadek, gdyby ktoś był nadal zainteresowany. Jeśli zdecyduję się również na eksplorację danych, moje wyniki zostaną również dodane do repozytorium.

Dzięki za grę!

AI01 - Python 3

Nie mogę jeszcze znaleźć dla niego lepszej nazwy :-P.

Identyfikator : ray-ai01

Technologia : Python 3

Wybrane : tak

Argumenty :ai01.py identifier port

Opis : Praca przez wnioskowanie. Kiedy liczba kart, których właściciel nie jest znany, jest mniejsza niż próg, AI zaczyna eliminować wszystkie niemożliwe rozwiązania poprzez rekurencyjne globalne wnioskowanie. W przeciwnym razie używa wnioskowania lokalnego.

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

Kod AI można znaleźć tutaj .

SimpleCluedoPlayer.java

Ta klasa używa AbstractCluedoPlayer, która obsługuje wszystkie operacje we / wy i pozwala logice pracować z prostym typem interfejsu. Cała sprawa jest na githubie .

To z dużym prawdopodobieństwem pokonuje losowego gracza (w najgorszym przypadku potrzeba 15 sugestii, podczas gdy losowy gracz przyjmuje średnio 162), ale łatwo go pokonać. Oferuję to, aby piłka się toczyła.

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

Identyfikator: gamecoder-SpockAI

Wpis repo: kliknij tutaj

Wybrane: tak

Technologia: Java 7 oparta nacom.sadakatsu.clue.jar

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

Opis:

SpockAIjest graczem Speed ​​Clue opartym na klasie Knowledge, którą napisałem. TheKnowledgeKlasa reprezentuje wszystkie możliwe stany, że gra może być podane co działo się do tej pory. Reprezentuje rozwiązania gry i możliwe ręce graczy jako zestawy i wykorzystuje iteracyjne dedukcje, aby zredukować te zestawy tak dalece, jak to możliwe, za każdym razem, gdy coś się uczy. SpockAIużywa tej klasy do ustalenia, które sugestie mają zapewnić najbardziej pomocne wyniki w najgorszym przypadku, i losowo wybiera jedną z tych sugestii na swoją kolej. Kiedy musi obalić sugestię, próbuje albo pokazać kartę, która już pokazała sugerującą sztuczną inteligencję, albo pokazać kartę z kategorii, dla której ograniczył najmniej możliwości. Robi oskarżenie tylko wtedy, gdy zna rozwiązanie.

Heurystyka, której użyłem do ustalenia najlepszej sugestii, jest następująca. Po wyciągnięciu wszystkich informacji z sugestii, możliwe rozwiązanie i możliwe zestawy kart gracza zostaną zmniejszone (chyba że sugestia nie ujawni żadnych nowych informacji). Teoretycznie najlepszą sugestią jest ta, która najbardziej zmniejsza liczbę możliwych rozwiązań. W przypadku remisu zakładam, że lepsza jest sugestia, która najbardziej zmniejsza liczbę możliwych rozdań dla graczy. Tak więc dla każdej sugestii próbuję każdego możliwego wyniku, który nie prowadzi do sprzeczności w wiedzy. Zakłada się, że którykolwiek wynik ma najmniejszą poprawę w liczeniu rozwiązań / rozdań, będzie wynikiem sugestii. Następnie porównuję wyniki wszystkich sugestii i wybieram, który z nich ma najlepszy wynik. W ten sposób gwarantuję optymalny zysk w najgorszym przypadku.

Rozważam dodanie analizy kombinacji sił brutalnych możliwych rozwiązań i możliwych rąk gracza SpockAI jeszcze silniejszym, ale ponieważ SpockAIjest to już najwolniejszy, najbardziej wymagający zasobów wpis, prawdopodobnie to pominę.

Zrzeczenie się:

Zamierzałem wypuścić AI na ten konkurs kilka tygodni temu. W tej chwili nie mogłem zacząć pisać AI aż do piątku w zeszłym tygodniu i ciągle znajdowałem śmieszne błędy w kodzie. Z tego powodu jedynym sposobem, w jaki mogłem zabrać się SpockAIdo pracy przed upływem terminu, było użycie dużej puli wątków. Efektem końcowym jest to, że (obecnie) SpockAI może osiągnąć + 90% wykorzystanie procesora i 2 GB + użycie pamięci (choć obwiniam za to śmieciarz). Zamierzam wziąć udział SpockAIw konkursie, ale jeśli inni uznają, że jest to naruszenie zasad , przyznam tytuł „zwycięzcy” drugiemu miejscu, aby SpockAIwygrać. Jeśli czujesz się w ten sposób, zostaw komentarz do tego efektu na tej odpowiedzi.

InferencePlayer.java

Pełny kod na Github (uwaga: używa tego samego, AbstractCluedoPlayerco mój wcześniej SimpleCluedoPlayer).

Prawdziwym rdzeniem tego gracza jest jego PlayerInformationklasa (tutaj lekko przycięta):

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

Ujednolica informacje na temat sugestii, których gracz nie odrzucił (wskazując, że nie ma żadnej z tych kart), sugestii, które odrzucił (wskazując, że posiadają przynajmniej jedną z tych kart) oraz kart, których lokalizacja jest pewna. Następnie iteracyjnie stosuje kilka podstawowych zasad, aby zagęścić te informacje w swojej istocie.

Nie sądzę, aby można było uzyskać więcej deterministycznych informacji (z wyjątkiem fałszywych oskarżeń, które, jak zakładam, są zbyt rzadkie, aby się tym przejmować), chociaż mogłem coś przeoczyć. Nie jest potencjał dla bardziej wyrafinowanego odtwarzacza do prawdopodobieństw szacują, że gracz ma karty X Y ...

Innym obszarem, który prawdopodobnie dopuszcza znaczną poprawę, jest podjęcie decyzji, którą sugestię wprowadzić. Próbuję zmaksymalizować zdobywanie informacji przy użyciu dość niezgrabnego podejścia o dużej sile, ale jest wiele źle uzasadnionych heurystów w ocenie względnych zalet wiedzy uzyskanej z różnych hipotetycznych podejrzeń. Nie zamierzam jednak stroić heurystyki, dopóki ktoś inny nie wystawi godnego przeciwnika.

CluePaddle (ClueStick / ClueBat / ClueByFour) - C #

Napisałem ClueBot, klient C #, dla którego łatwo jest zaimplementować AI i różne AI, w tym najpoważniejszą próbę o nazwie CluePaddle. Kod znajduje się na https://github.com/jwg4/SpeedClueContest/tree/clue_paddle z prośbą o ściągnięcie, aby scalić go w górę.

ClueStick to proof-of-concept, który w zasadzie zgaduje i ignoruje większość tego, co się dzieje. ClueBat to kolejna głupia sztuczna inteligencja, z tym wyjątkiem, że próbuje wykorzystać lukę w ClueStick, aby zmusić ją do fałszywych oskarżeń. ClueByFour jest rozsądną sztuczną inteligencją, ponieważ zawiera rozsądne sugestie i zapamiętuje karty, które pokazali inni.

CluePaddle jest najbardziej inteligentny. Próbuje dowiedzieć się, kto ma to, co opiera się nie tylko na tym, jakie zaoferowano odrzucenia, ale także na podstawie tego, którzy gracze nie zaoferowali odrzucenia danej sugestii. Nie bierze pod uwagę liczby kart, które każdy gracz ma w bankomacie, ale należy to naprawić. Zawiera kilka dość długich klas, więc nie opublikuję tutaj całego kodu, ale poniższa metoda nadaje smak.

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

Jeśli czwórka gra przeciwko sobie, CluePaddle wygrywa zdecydowanie najwięcej gier, a ClueByFour jest drugi, a pozostałe dwie nigdzie.

Tylko CluePaddle jest konkurencyjnym wejściem (jak dotąd). Stosowanie:

CluePaddle.exe identifier port

Jeśli ktoś chce mieć C # AI, tylko utworzyć projekt ConsoleApplication w soltution, wdrożenie IClueAIinterfejsu w klasie, a następnie dokonać Programpochodzą od ProgramTemplatei skopiować to, co dla innych projektów zrobić Main(). Jedyną zależnością jest NUnit do testowania jednostkowego i możesz łatwo usunąć wszystkie testy z kodu (ale nie, po prostu zainstaluj NUnit).