Programmin Pac-Man

Oprawa

Grasz jako Pac-Man. Chcesz zbierać granulki, owoce i granulki mocy przed kimkolwiek innym, unikając duchów.

Zasady

1. Każdy ważny Pac-Man będzie w jednym labiryncie. Gracz z najwyższym łącznym wynikiem po 10 grach wygra.
2. Gra kończy się, gdy wszyscy Pac-Men nie żyją, wszystkie granulki zniknęły lub minęło 500 tur
3. Jeśli Pac-Man umrze, nadal gra jako duch
4. Zjedzenie granulki mocy sprawi, że będziesz niezwyciężony przez 10 tur i będziesz mógł jeść duchy
5. Jedzenie ducha teleportuje ducha w losowe miejsce
6. Duchy nie mogą jeść niczego oprócz Pac-Men i nie otrzymują żadnych punktów
7. Zjedzenie następujących przedmiotów jako Pac-Man zapewni ci następujące punkty:
   7. Pellet: 10
   8. Power Pellet: 50
   9. Owoc: 100
   10. Duch: 200

Labirynt

Jeśli istnieją n Pac-Men, a potem labiryntem wielkości sqrt(n)*10przez sqrt(n)*10zostaną wygenerowane przy użyciu Algorytm Prima (ze względu na jego niski współczynnik rzeki), a następnie pleciony całkowicie, dając pierwszeństwo do już istniejących ślepych zaułków. Co więcej, ten oplot można wykonać na krawędziach, dzięki czemu istnieje kilka ścieżek od góry do dołu i od lewej do prawej.

Tam będzie:

1. 2n Duchy
2. 4n Power Pellets
3. 2n Owoc
4. n Pac-Men w miejscach, w których kwadraty połączonych sąsiadów są puste.
5. Wszystkie pozostałe puste miejsca zostaną wypełnione granulkami

Dlatego początkowa mapa z 10 graczami będzie wyglądać mniej więcej tak (Duchy = zielony, Pellety = aqua, owoce = czerwony, Pac-Man = żółty):

Wejście wyjście

Na początku gry otrzymasz jedną linię postaci reprezentujących ściany w każdym kwadracie na mapie. Za każdy kwadrat, zaczynając od lewego górnego rogu, przesuwając się w prawo i zawijając do następnego wiersza, otrzymasz cyfrę szesnastkową reprezentującą sytuację na ścianie:

0: No walls
1: North wall
2: East wall
3: East & North wall
4: South wall
5: South & North wall
6: South & East wall
7: Won't occur
8: West wall
9: West & North wall
A: West & East wall
B: Won't occur
C: West & South wall
D: Won't occur
E: Won't occur
F: Won't occur

Krótko mówiąc, Północ = 1, Wschód = 2, Południe = 4 i Zachód = 8, zsumowane.

Następnie, w każdej turze , otrzymasz swoją aktualną pozycję i przedmioty na linii wzroku (jeśli jesteś Pac-Manem. Wszystkie duchy otrzymują wszystkie pola od -5 do +5 od ich względnej pozycji). Twoja linia wzroku będzie zależeć od kierunku, w którym podróżowałeś w ostatnim zakręcie. Jeśli podróżowałeś na północ, dostaniesz wszystkie kwadraty bezpośrednio na północ, wschód i zachód od ciebie, dopóki ściana nie ograniczy twojego widoku plus jeden kwadrat na północnym zachodzie i północnym wschodzie, jeśli żadna ściana nie ograniczy twojego widoku. Jeśli zdecydujesz się nie ruszać, otrzymasz kwadraty we wszystkich 8 kierunkach.

Dla wizualnego Ioznacza niewidzialny, Voznacza widoczny, Poznacza Pac-Man (zakładając, że Pac-Man jest skierowany na północ):

|I I|V|I|
|I V|V V|
|V V P|I|
|I I|I|I|

Każdy kwadrat otrzyma współrzędną, a następnie jej zawartość. Jego zawartość są reprezentowane przez następujące znaki:

1. P: 1 lub więcej Pac-Man
2. G: 1 lub więcej Duchów
3. o: Pellet
4. O: Power pellet
5. F: Kawałek Owocu
6. X: Nic

Jeśli na kwadracie jest duch i coś jeszcze, Gzostanie zwrócone.

Dlatego jeśli byłeś na kwadracie 23,70, po prostu przeniosłeś się na północ, kwadrat nad tobą jest ślepym zaułkiem i zawiera kulę mocy, a masz ściany po obu stronach ciebie, twój wkład byłby następujący:

23,70X 22,70O

Na twoim obecnym polu pokaże się, Gjeśli jesteś Duchem, a Pjeśli na twoim polu jest inny Pac-Man, w przeciwnym razieX

Następnie za pośrednictwem STDOUT zwrócisz następujące elementy:

Pojedynczy znak reprezentujący kierunek ( North, East, South, West lub XStay).

Przed przejściem w danym kierunku możesz również x,ypodać dowolną współrzędną jako , a ściany tego kwadratu zostaną cofnięte (jak opisano powyżej)

Program musi działać nieprzerwanie, dopóki nie Qzostanie przekazany do niego przez STDIN. Programy zostaną uruchomione ponownie dla każdej gry.

Dostęp do innych informacji poza danymi przekazywanymi do STDIN (w tym innymi danymi Pac-Men lub danymi przechowywanymi przez program hosta) jest niedozwolony.

Brak zwrócenia ruchu w ciągu 1000 ms spowoduje zakończenie programu (działającego na mojej dość przyzwoitej maszynie Win8). Otrzymasz 2 sekundy na przetworzenie początkowego układu labiryntu, gdy zostanie podany

Host zostanie napisany w Pythonie, a kod do testowania twojego bota jest już dostępny.

Wyjątkowe przypadki

• Jeśli wielu Pac-Men znajdzie się w tym samym miejscu, nie zdobądź zawartości aktualnego kwadratu, chyba że dokładnie 1 z nich jest niepokonany, w takim przypadku niezwyciężony Pac-Man otrzyma kulkę.
• Pac-Man zjedzony przez Ducha nie zostanie teleportowany gdzie indziej. Jeśli dwóch Pac-Menów jest na kwadracie, a jeden jest niezwyciężony, duch zostanie teleportowany.
• Teleportacja jako duch uniemożliwia ci ruch przez 1 turę. Grając jako duch, po prostu pominiesz swoją turę
• Próba przejścia przez ścianę będzie interpretowana jako „Zostań”

• Każdy z początkowych duchów otrzyma jedną z 4 cech osobowości, jak opisano tutaj , z następującą modyfikacją:

  1. Opisane błędy nie będą duplikowane
  2. Wszystkie będą aktywne od samego początku
  3. Są wrażliwe tylko na gracza, który zjadł granulkę
  4. Będą bezterminowo przełączać się z rozproszenia na pościg, z których każdy ma określoną liczbę zwojów przed przełączeniem
  5. Po przejściu na pogoń znajdą najbliższego Pac-Mana, który będzie go ścigał, i będzie go ścigał przez czas trwania ich pościgu. (Jeśli istnieje remis dla bliskości, Pac-Man zostanie wybrany pseudolosowo)
  6. Blinky nie przyspieszy
  7. Inky wybierze najbliższego ducha, aby oparł swoje obliczenia po przejściu na pościg.
  8. Clyde znajdzie wszystkich graczy 8 pól dalej, a następnie podąży za najdalszym graczem.
  9. Wszystkie duchy oprócz Clyde'a nie będą celowały w gracza znajdującego się w odległości większej niż 5 pól

Przyjmę kod kompilowalny ze standardowego języka lub pliku .exe (z dołączonym kodem).

Wskazówki dotyczące programowania

Możesz z moim kontrolerem. Musisz umieścić folder / bots / your_bot_name / w tym samym katalogu co program. W folderze musisz dodać plik command.txt zawierający polecenie do wykonania programu (np python my_bot.py.:) i bota.

Kod kontrolera znajduje się na Github (kod Pythona, jeśli potrzebujesz grafiki, wymaga Pygame). Testowany na Windowsie i Linuksie

WYNIKI

Ghostbuster: 72 840 punktów

pathy: 54 570 punktów

krótkowzroczny: 50,820 punktów

Unikaj interakcji: 23 580 punktów

fizyk: 18,330 punktów

losowy spacer: 7760 punktów

dumbpac: 4880 punktów

GhostBuster - Python

Wybiera losowe miejsce na mapie, używa algorytmu A *, aby znaleźć najlepszą ścieżkę do przodu. Gdy dotrze do miejsca docelowego, wybierze nowy i będzie kontynuował. Spróbuje unikać duchów, ale przy ograniczonym polu widzenia może czasem na nie wpaść. Uniknie chodzenia w miejscach już odwiedzonych.

• Dodano logikę dla ducha. Wybiera bliski (<8) losowy punkt i przenosi się tam, ignorując wyniki inne niż pacmen
• Dodano logikę niezwyciężoności
• Skorygowane wartości punktowe kwadratów
• Błąd (jeśli jest zbyt dobry i zjada wszystkie kulki, gra z jakiegoś powodu zawiesza się)

Używa kodu Sparra, dziękuję za logikę.

Windows 7, Visual Studios z Python Tools. Powinien działać na polach Linux.

#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

P,G,o,O,F,X = 5,600,-10,-100,-100,10
PreviousSquarePenalty = 10

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
mazeSize = int(math.sqrt(len(maze_desc)))

North,East,South,West = range(4)
DIRECTIONS = ['N','E','S','W']
Euclidian,Manhattan,Chebyshev = range(3)

sign = lambda x: (1, -1)[x<0]
wrap = lambda v : v % mazeSize

class Node(object):

    def __init__(self, x, y, value):
        self.x, self.y = x,y
        self.wallValue = int(value, 16); #Base 16
        self.nodes = {}
        self.item = 'o' # Start as normal pellet

    def connect(self, otherNode, dir):    
        if dir not in self.nodes:
            self.nodes[dir] = otherNode       
            otherNode.nodes[(dir+2)%4] = self

    def distance(self, otherNode, meth = Manhattan):
        xd = abs(otherNode.x - self.x)        
        yd = abs(otherNode.y - self.y)
        xd = min(xd, mazeSize - xd)
        yd = min(yd, mazeSize - yd)
        if meth == Euclidian:
            return math.sqrt(xd * xd + yd * yd)       
        if meth == Manhattan:
            return xd + yd
        if meth == Chebyshev:      
            return max(xd, yd)

    def direction(self, otherNode):
        for key, value in self.nodes.iteritems():
            if value == otherNode:
                return DIRECTIONS[key]            
        return 'ERROR'

    def getScore(self):
        score = eval(self.item)
        for node in self.nodes.values():
            score += eval(node.item)
        return score

    def nearbyGhost(self):
        if self.item == 'G':
            return True
        for node in self.nodes.values():
            if node.item == 'G':
                return True
        return False

    def __hash__(self):  
        return  (391 + hash(self.x))*23 + hash(self.y)

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

    def __ne__(self, other):
        return (self.x, self.y) != (other.x, other.y)

    def __str__(self):
        return str(self.x)+","+str(self.y)

    def __repr__(self):
        return str(self.x)+","+str(self.y)

# Make all the nodes first
nodes = {}
i = 0
for y in range(mazeSize):
    for x in range(mazeSize):       
        nodes[x,y] = Node(x,y,maze_desc[i])  
        i+=1

# Connect all the nodes together to form the maze
for node in nodes.values():
    walls = node.wallValue
    x,y = node.x,node.y    
    if not walls&1:  
        node.connect(nodes[x,wrap(y-1)], North)
    if not walls&2:
        node.connect(nodes[wrap(x+1),y], East)
    if not walls&4:
        node.connect(nodes[x,wrap(y+1)], South)
    if not walls&8:
        node.connect(nodes[wrap(x-1),y], West)

toVisit = set(nodes.values())
currentNode = None
destinationNode = None
previousNode = None
testInvincibilty = False
invincibility = 0
isGhost = False
turns = 0

def aStar(startNode, endNode):
    openSet = set([startNode])
    closedSet = set()
    gScores = {startNode: 0}
    cameFrom = {}
    curNode = startNode  
    while openSet:
        minF = 100000000
        for node in openSet:
            g = gScores[node]
            h = node.distance(endNode)
            f = g+h
            if f < minF:
                minF = f
                curNode = node

        if curNode == endNode:
            path = []
            while curNode != startNode:
                path.insert(0, curNode)
                curNode = cameFrom[curNode]
            return path

        openSet.remove(curNode)
        closedSet.add(curNode)
        for node in curNode.nodes.values():
            if node in closedSet:
                continue
            g = gScores[curNode]
            if isGhost:
                g += 1
                if node.item == 'P':
                    g -= 10 # prefer PacMen
            else:
                s = node.getScore();
                if invincibility > 1:
                    g -= abs(s) # everything is tasty when invincible
                else:
                    g += s
                if previousNode and node == previousNode:
                    g += PreviousSquarePenalty # penalize previous square
            isBetter = False
            if node not in openSet:
                openSet.add(node)
                isBetter = True
            elif g < gScores[node]:
                isBetter = True
            if isBetter:
                gScores[node] = g
                cameFrom[node]=curNode

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    turns += 1

    # break a line of input up into a list of tuples (X,Y,contents)
    info = [input_re.match(item).groups() for item in info.split()]

    # update what we know about all the cells we can see
    for cell in info:
        nodes[int(cell[0]),int(cell[1])].item = cell[2]

    currentNode = nodes[int(info[0][0]),int(info[0][1])]    

    if turns == 1:
        print 'X'
        continue

    if not isGhost and currentNode.item == 'G':
        isGhost = True
        destinationNode = random.sample(nodes.values(), 1)[0]

    if isGhost:     
        while destinationNode == currentNode or currentNode.distance(destinationNode) > 8:
            destinationNode = random.sample(nodes.values(), 1)[0]
    else:     

        if invincibility > 0:
            invincibility -=  1

        if testInvincibilty:
            testInvincibilty = False
            if currentNode.item == 'X':
                invincibility += 10

        while not destinationNode or destinationNode == currentNode:
            destinationNode = random.sample(toVisit, 1)[0]

        if currentNode.item == 'X':
            toVisit.discard(currentNode)

    bestPath = aStar(currentNode, destinationNode)

    nextNode = bestPath[0]

    direction = currentNode.direction(nextNode)

    if not isGhost and nextNode.item == 'O':   
        testInvincibilty = True      

    previousNode = currentNode

    print direction

krótkowzroczny

Ten pac unika sąsiednich duchów, chyba że może je zjeść, przenosi się na sąsiednie owoce lub granulki i idzie losowo w ostateczności.

#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays
# [wall bitmask, item last seen in square]

def chunks(l, n):
    for i in xrange(0, len(l), n):
        yield l[i:i+n]
maze = []
for row in chunks(maze_desc, maze_size):
    maze.append([[int(c,16),'X'] for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

turn = 0
invincibility_over = 0
last_move = None

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    # break a line of input up into a list of tuples (X,Y,contents)
    info = info.split()
    info = [input_re.match(item).groups() for item in info]

    # update what we know about all the cells we can see
    for cell in info:
        maze[int(cell[1])][int(cell[0])][1] = cell[2]

    # current location
    x = int(info[0][0])
    y = int(info[0][1])

    # which directions can we move from our current location?
    valid_directions = []
    # we might consider sitting still
    # valid_directions.append('X')
    walls = maze[y][x][0]
    if not walls&1:
        valid_directions.append('N')
    if not walls&2:
        valid_directions.append('E')
    if not walls&4:
        valid_directions.append('S')
    if not walls&8:
        valid_directions.append('W')

    # which direction has the highest value item?
    best_value = 0
    best_direction = 'X'
    for c in [(x,y-1,'N'),(x+1,y,'E'),(x,y+1,'S'),(x-1,y,'W')]:
        if c[2] in valid_directions:
            # am I a ghost?
            if maze[y][x][1] == 'G':
                if maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
                    best_value = 999
                    best_direction = c[2]
            else:
                if maze[c[1]%maze_size][c[0]%maze_size][1] == 'F':
                    if best_value < 100:
                        best_value = 100
                        best_direction = c[2]
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'O':
                    if best_value < 50:
                        best_value = 50
                        best_direction = c[2]
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'o':
                    if best_value < 10:
                        best_value = 10
                        best_direction = c[2]
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'G':
                    if turn < invincibility_over:
                        # eat a ghost!
                        if best_value < 200:
                            best_value = 200
                            best_direction = c[2]
                    else:
                        # avoid the ghost
                        valid_directions.remove(c[2])

    # don't turn around, wasteful and dangerous
    if last_move:
        reverse = ['N','E','S','W'][['S','W','N','E'].index(last_move)]
        if reverse in valid_directions:
            valid_directions.remove(reverse)

    if best_value == 50:
        invincibility_over = turn + 10      
    if best_direction != 'X':
        # move towards something worth points
        # sys.stderr.write("good\n")
        last_move = best_direction
    elif len(valid_directions)>0:
        # move at random, not into a wall
        # sys.stderr.write("valid\n")
        last_move = random.choice(valid_directions)
    else:
        # bad luck!
        # sys.stderr.write("bad\n")
        last_move = random.choice(['N','E','S','W'])
    print last_move

    turn += 1

unikaj

Unikaj wszystkich duchów jako pacman i wszystkich pacmen, gdy jest duchem. Próbuje uniknąć jakiegokolwiek własnego rodzaju, jeśli to możliwe, a następnie unika obracania o 180, jeśli to możliwe.

#!/usr/bin/env python
import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays of numbers indicating wall positions

def chunks(l, n):
    for i in xrange(0, len(l), n):
        yield l[i:i+n]
maze = []
for row in chunks(maze_desc, maze_size):
    maze.append([[int(c,16),'X'] for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

last_moved = 'X'

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    # break a line of input up into a list of tuples (X,Y,contents)
    info = info.split()
    info = [input_re.match(item).groups() for item in info]

    # location
    x = int(info[0][0])
    y = int(info[0][1])

    # update what we know about all the cells we can see
    for cell in info:
        maze[int(cell[1])][int(cell[0])][1] = cell[2]

    # which directions can we move from our current location?
    valid_directions = []
    walls = maze[y][x][0]
    if not walls&1: 
        valid_directions.append('N')
    if not walls&2:
        valid_directions.append('E')
    if not walls&4:
        valid_directions.append('S')
    if not walls&8:
        valid_directions.append('W')

    bad_directions = []
    for c in [(x,y-1,'N'),(x+1,y,'E'),(x,y+1,'S'),(x-1,y,'W')]:
        if c[2] in valid_directions:
            # am I a ghost?
            if maze[y][x][1] == 'G':
                # it's a pacman, run. interaction is always a risk.
                if maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
                    valid_directions.remove(c[2])
                # another ghost? let me move away.
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == "G":
                    bad_directions.append(c[2])
            else:
                # it's a ghost, run. ghosts are evil.
                if maze[c[1]%maze_size][c[0]%maze_size][1] == "G":
                    valid_directions.remove(c[2])
                # its another pacman, move away!
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
                    bad_directions.append(c[2])

    # if possible to avoid normal contact, do so
    good_directions = list(set(valid_directions) - set(bad_directions))
    if len(good_directions) > 0:
        valid_directions = good_directions

    # if not the only option, remove going backwards from valid directions
    if len(valid_directions) > 1:
        if last_moved == 'N' and 'S' in valid_directions:
            valid_directions.remove('S')
        elif last_moved == 'S' and 'N' in valid_directions:
            valid_directions.remove('N')
        elif last_moved == 'W' and 'E' in valid_directions:
            valid_directions.remove('E')
        elif 'W' in valid_directions:
            valid_directions.remove('W')

    # if possible, continue in the same direction
    if last_moved in valid_directions:
        print last_moved
    # prefer turning left/right randomly instead of turning 180
    #   backwards has been removed from valid_directions if not
    #   the only option
    elif len(valid_directions) > 0:
        last_moved=random.choice(valid_directions)
        print last_moved
    # can't move, so stay put. desire to continue in original 
    #   direction remains.
    else:
        print 'X'

Fizyk, Haskell

Fizyk Pac-Man wierzy, że prawo uniwersalnej grawitacji Newtona może mu pomóc wygrać grę. Następnie po prostu stosuje go do wszystkich innych obiektów, które zna podczas gry. Ponieważ fizyk jest stary i ma złą pamięć, może pamiętać rzeczy tylko w 5 rundach. Hooooly, zła pamięć faktycznie pomaga mu zdobyć lepsze wyniki.

Ta odpowiedź ma dwa pliki:

• Main.hszawiera interesującą część.
• Pacman.hs, tylko trochę nudnego kodu obsługi protokołu. Możesz go użyć do napisania własnego rozwiązania haskell. Nie zawiera żadnego kodu AI.

Och, czekaj, my też mamy Makefile.

Oto nadchodzą:

Main.hs

import Pacman
import Data.Complex
import Data.List
import Data.Function
import qualified Data.Map as Map
import Data.Maybe
import System.IO

data DebugInfo = DebugInfo {
  debugGrid :: Grid
, debugForce :: Force
, debugAction :: Action
} deriving (Show)

data Physicist = Physicist [(Int, Object)] (Maybe DebugInfo)

type Force = Complex Double


calcForce :: Int -> Position -> PlayerType -> Object -> Force
calcForce n p1 t1 object = if d2 == 0 then 0 else base / (fromIntegral d2 ** 1.5 :+ 0)
  where
    (x1, y1) = p1
    (x2, y2) = p2
    wrap d = minimumBy (compare `on` abs) [d, n - d]
    dx = wrap $ x2 - x1
    dy = wrap $ y2 - y1
    Object t2 p2 = object
    d2 = dx * dx + dy * dy
    base = (fromIntegral dx :+ fromIntegral dy) * case t1 of
      PacmanPlayer -> case t2 of
        Pellet -> 10.0
        PowerPellet -> 200.0
        Ghost -> -500.0
        Pacman -> -20.0
        Fruit -> 100.0
        Empty -> -2.0
      GhostPlayer -> case t2 of
        Pellet -> 10.0
        PowerPellet -> 200.0
        Ghost -> -50.0
        Pacman -> 500.0
        Fruit -> 100.0
        Empty -> -2.0

instance PlayerAI Physicist where
  findAction player info = (action, player') where
    Player {
      playerType = type_
    , playerField = field
    , playerMemory = Physicist objectsWithAge _
    } = player

    n = fieldSize field
    NormalRound pos _ objects = info
    objectsWithAge' = combineObjects objectsWithAge objects
    objects' = map snd objectsWithAge'
    directionChoices = filter (not . gridHasWall grid) directions4
    totalForce = sum $ map (calcForce n pos type_) objects'
    grid = fromMaybe (error $ "invalid position " ++ show pos) $ (fieldGetGrid field) pos
    action = if magnitude totalForce < 1e-10
      then if null directionChoices
        then Stay
        else Move $ head directionChoices
      else Move $ maximumBy (compare `on` (projectForce totalForce)) directionChoices
    debugInfo = Just $ DebugInfo grid totalForce action
    player' = player {
      playerMemory = Physicist objectsWithAge' debugInfo
    }

  -- roundDebug player _ = do
  --   let Physicist objects debugInfo = playerMemory player
  --       type_ = playerType player
  --   hPrint stderr (objects, debugInfo)

combineObjects :: [(Int, Object)] -> [Object] -> [(Int, Object)]
combineObjects xs ys = Map.elems $ foldr foldFunc initMap ys where
  foldFunc object@(Object type_ pos) = Map.insert pos (0, object)
  addAge (age, object) = (age + 1, object)
  toItem (age, object@(Object _ pos)) = (pos, (age, object))
  initMap = Map.fromList . map toItem . filter filterFunc . map addAge $ xs
  filterFunc (age, object@(Object type_ _))
    | type_ == Empty = True
    | age < maxAge = True
    | otherwise = False

maxAge = 5

projectForce :: Force -> Direction -> Double
projectForce (fx :+ fy) (Direction dx dy) = fx * fromIntegral dx + fy * fromIntegral dy

main :: IO ()
main = runAI $ Physicist [] Nothing

Pacman.hs

module Pacman (
    Field(..)
  , Grid(..)
  , Direction(..)
  , directions4, directions8
  , Position
  , newPosition
  , Player(..)
  , PlayerType(..)
  , ObjectType(..)
  , Object(..)
  , RoundInfo(..)
  , Action(..)
  , runAI
  , PlayerAI(..)
  ) where

import Data.Bits
import Data.Char
import Data.List
import Data.Maybe
import qualified Data.Map as Map
import qualified System.IO as SysIO

data Field = Field {
  fieldGetGrid :: Position -> Maybe Grid
, fieldSize :: Int
}

data Grid = Grid {
  gridHasWall :: Direction -> Bool
, gridPos :: Position
}

instance Show Grid where
  show g = "Grid " ++ show (gridPos g) ++ ' ':reverse [if gridHasWall g d then '1' else '0' | d <- directions4]

data Direction = Direction Int Int
  deriving (Show, Eq)

directions4, directions8 :: [Direction]
directions4 = map (uncurry Direction) [(-1, 0), (0, 1), (1, 0), (0, -1)]
directions8 = map (uncurry Direction) $ filter (/=(0, 0)) [(dx, dy) | dx <- [-1..1], dy <- [-1..1]]

type Position = (Int, Int)
newPosition :: (Int, Int)  -> Position
newPosition = id

data Player a = Player {
  playerType :: PlayerType
, playerField :: Field
, playerRounds :: Int
, playerMemory :: a
}
data PlayerType = PacmanPlayer | GhostPlayer
  deriving (Show, Eq)

class PlayerAI a where
  onGameStart :: a -> Field -> IO ()
  onGameStart _ _ = return ()

  onGameEnd :: a -> IO ()
  onGameEnd _ = return ()

  findAction :: Player a -> RoundInfo -> (Action, Player a)

  roundDebug :: Player a -> RoundInfo -> IO ()
  roundDebug _ _ = return ()


data ObjectType = Pacman | Ghost | Fruit | Pellet | PowerPellet | Empty
  deriving (Eq, Show)
data Object = Object ObjectType Position
  deriving (Show)

data RoundInfo = EndRound | NormalRound Position PlayerType [Object]

data Action = Stay | Move Direction
  deriving (Show)


parseField :: String -> Field
parseField s = if validateField field
  then field 
  else error $ "Invalid field: " ++ show ("n", n, "s", s, "fieldMap", fieldMap)
  where
    field = Field {
      fieldGetGrid = flip Map.lookup fieldMap
    , fieldSize = n
    }
    (n : _) = [x | x <- [0..], x * x == length s]
    fieldMap = Map.fromList [
        ((i, j), parseGrid c (newPosition (i, j))) 
        | (i, row) <- zip [0..n-1] rows,
          (j, c) <- zip [0..n-1] row
      ]
    rows = reverse . snd $ foldr rowFoldHelper (s, []) [1..n]
    rowFoldHelper _ (s, rows) =
      let (row, s') = splitAt n s
      in (s', row:rows)

validateField :: Field -> Bool
validateField field@(Field { fieldGetGrid=getGrid, fieldSize=n }) = 
  all (validateGrid field) $ map (fromJust.getGrid) [(i, j) | i <- [0..n-1], j <- [0..n-1]]

validateGrid :: Field -> Grid -> Bool
validateGrid
  field@(Field { fieldGetGrid=getGrid, fieldSize=n })
  grid@(Grid { gridPos=pos })
  = all (==True) [gridHasWall grid d == gridHasWall (getNeighbour d) (reverse d) | d <- directions4]
  where
    reverse (Direction dx dy) = Direction (-dx) (-dy)
    (x, y) = pos
    getNeighbour (Direction dx dy) = fromJust . getGrid . newPosition $ (mod (x + dx) n, mod (y + dy) n)

parseGrid :: Char -> Position -> Grid
parseGrid c pos = Grid gridHasWall pos
  where
    walls = zip directions4 bits
    bits = [((x `shiftR` i) .&. 1) == 1 | i <- [0..3]]
    Just x = elemIndex (toLower c) "0123456789abcdef"
    gridHasWall d = fromMaybe (error $ "No such direction " ++ show d) $
      lookup d walls

parseRoundInfo :: String -> RoundInfo
parseRoundInfo s = if s == "Q" then EndRound else NormalRound pos playerType objects'
  where
    allObjects = map parseObject $ words s
    Object type1 pos : objects = allObjects
    objects' = if type1 `elem` [Empty, Ghost] then objects else allObjects
    playerType = case type1 of
      Ghost -> GhostPlayer
      _ -> PacmanPlayer

parseObject :: String -> Object
parseObject s = Object type_ (newPosition (x, y)) where
  (y, x) = read $ "(" ++ init s ++ ")"
  type_ = case last s of
    'P' -> Pacman
    'G' -> Ghost
    'o' -> Pellet
    'O' -> PowerPellet
    'F' -> Fruit
    'X' -> Empty
    c -> error $ "Unknown object type: " ++ [c]

sendAction :: Action -> IO ()
sendAction a = putStrLn name >> SysIO.hFlush SysIO.stdout where
  name = (:[]) $ case a of
    Stay -> 'X'
    Move d -> fromMaybe (error $ "No such direction " ++ show d) $
      lookup d $ zip directions4 "NESW"

runPlayer :: PlayerAI a => Player a -> IO ()
runPlayer player = do
  roundInfo <- return . parseRoundInfo =<< getLine
  case roundInfo of
    EndRound -> return ()
    info@(NormalRound _ type_' _) -> do
      let
        updateType :: Player a -> Player a
        updateType player = player { playerType = type_' }
        player' = updateType player
        (action, player'') = findAction player' info
      roundDebug player'' info
      sendAction action
      let 
        updateRounds :: Player a -> Player a
        updateRounds player = player { playerRounds = playerRounds player + 1}
        player''' = updateRounds player''
      runPlayer player'''

runAI :: PlayerAI a => a -> IO ()
runAI mem = do
  field <- return . parseField =<< getLine
  let player = Player {
    playerType = PacmanPlayer
  , playerField = field
  , playerRounds = 0
  , playerMemory = mem
  }
  runPlayer player

Makefile

physicist: Main.hs Pacman.hs
    ghc -O3 -Wall Main.hs -o physicist

polecenie.txt

./physicist

dumbpac

Ten ruch porusza się losowo, bez względu na układ labiryntu, duchy i inne czynniki.

Perl:

#!/usr/bin/perl
local $| = 1; # auto flush!
$maze_desc = <>;
while(<>) { 
    if($_ eq "Q"){
        exit;
    }
    $move = (("N","E","S","W","X")[rand 5]);
    print ($move . "\n");
}

Pyton:

#!/usr/bin/env python

import os
import sys
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

maze_desc = sys.stdin.readline().rstrip()
while True:
    info = sys.stdin.readline().rstrip()
    if (not int) or (info == "Q"):
        break
    print random.choice(['N', 'E', 'S', 'W', 'X'])

randomwalk

ten pac wchodzi losowo, ale nie do ścian

#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays of numbers indicating wall positions
def chunks(l, n):
    for i in xrange(0, len(l), n):
        yield l[i:i+n]
map = []
for row in chunks(maze_desc, maze_size):
    map.append([int(c,16) for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    # break a line of input up into a list of tuples (X,Y,contents)
    info = info.split()
    info = [input_re.match(item).groups() for item in info]

    # this pac only cares about its current location
    info = info[0]

    # which directions can we move from our current location?
    valid_directions = []
    # we might consider sitting still
    # valid_directions.append('X')
    walls = map[int(info[1])][int(info[0])]
    if not walls&1:
        valid_directions.append('N')
    if not walls&2:
        valid_directions.append('E')
    if not walls&4:
        valid_directions.append('S')
    if not walls&8:
        valid_directions.append('W')

    # move at random, not into a wall
    print random.choice(valid_directions)

Pathy, Python 3

Ten bot często korzysta ze ścieżki. Biorąc pod uwagę pozycję początkową i końcową, używa prostej BFS, aby znaleźć najkrótszą ścieżkę. Wyszukiwanie ścieżki jest używane w:

• Znajdź pelety mocy, owoce lub granulki.
• Jeśli jest niezwyciężony, ścigaj duchy
• Jeśli to duch, ścigaj Pac-Men
• Uciekaj przed duchami
• Oblicz odległość między daną parą pozycji.

polecenie.txt

python3 pathy.py

pathy.py

import sys
import random
from collections import deque

DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
GHOST = 'G'
PACMAN = 'P'
FRUIT = 'F'
PELLET = 'o'
POWER_PELLET = 'O'
EMPTY = 'X'

PACMAN_PLAYER = 'pacman-player'
GHOST_PLAYER = 'ghost-player'


class Field:
    def __init__(self, s):
        n = int(.5 + len(s) ** .5)
        self.size = n
        self.mp = {(i, j): self.parse_grid(s[i * n + j]) for i in range(n) for j in range(n)}

    @staticmethod
    def parse_grid(c):
        x = int(c, 16)
        return tuple((x >> i) & 1 for i in range(4))

    def can_go_dir_id(self, pos, dir_id):
        return self.mp[pos][dir_id] == 0

    def connected_neighbours(self, pos):
        return [(d, self.go_dir_id(pos, d)) for d in range(4) if self.can_go_dir_id(pos, d)]

    def find_path(self, is_end, start):
        que = deque([start])
        prev = {start: None}
        n = self.size

        def trace_path(p):
            path = []
            while prev[p]:
                path.append(p)
                p = prev[p]
            path.reverse()
            return path

        while que:
            p = x, y = que.popleft()
            if is_end(p):
                return trace_path(p)
            for d, p1 in self.connected_neighbours(p):
                if p1 in prev:
                    continue
                prev[p1] = p
                que.append(p1)
        return None

    def go_dir_id(self, p, dir_id):
        dx, dy = DIRECTIONS[dir_id]
        x, y = p
        n = self.size
        return (x + dx) % n, (y + dy) % n

    def distance(self, p1, p2):
        return len(self.find_path((lambda p: p == p2), p1)) 

    def get_dir(self, p1, p2):
        x1, y1 = p1
        x2, y2 = p2
        return (self.dir_wrap(x2 - x1), self.dir_wrap(y2 - y1))

    def dir_wrap(self, x):
        if abs(x) > 1:
            return 1 if x < 0 else -1
        return x


class Player:
    def __init__(self, field):
        self.field = field

    def interact(self, objects):
        " return: action: None or a direction_id"
        return action

    def send(self, msg):
        print(msg)
        sys.stdout.flush()


class Pathy(Player):
    FLEE_COUNT = 8

    def __init__(self, field):
        super().__init__(field)
        self.type = PACMAN_PLAYER
        self.pos = None
        self.mem_field = {p: GHOST for p in self.field.mp}
        self.power = 0
        self.flee = 0
        self.ghost_pos = None
        self.ghost_distance = None

    @property
    def invincible(self):
        return self.type == PACMAN_PLAYER and self.power > 0

    def detect_self(self, objects):
        ((x, y), type) = objects[0]
        self.type = GHOST_PLAYER if type == GHOST else PACMAN_PLAYER
        self.pos = (x, y)

    def update_mem_field(self, objects):
        for (p, type) in objects:
            self.mem_field[p] = type

    def find_closest_ghost_pos(self, objects):
        try:
            return min(
                (p for (p, t) in objects if t == GHOST),
                key=lambda p: self.field.distance(self.pos, p)
            )
        except:
            return None

    def chase(self, types):
        is_end = lambda p: self.mem_field[p] in types
        path = self.field.find_path(is_end, self.pos)
        if not path:
            return None
        return DIRECTIONS.index(self.field.get_dir(self.pos, path[0]))

    def interact(self, objects):
        self.detect_self(objects)
        self.update_mem_field(objects)

        action = None
        if self.invincible:
            self.debug('invincible!!!')
            action = self.chase((GHOST,))
            if action is None:
                action = self.chase((POWER_PELLET,))
            if action is None:
                action = self.chase((FRUIT, PELLET,))
        elif self.type == GHOST_PLAYER:
            action = self.chase((PACMAN,))
        else:
            # PACMAN_PLAYER
            ghost_pos = self.find_closest_ghost_pos(objects)
            if ghost_pos:
                ghost_distance = self.field.distance(ghost_pos, self.pos)
                if not self.flee or ghost_distance < self.ghost_distance:
                    self.flee = self.FLEE_COUNT
                    self.ghost_distance = ghost_distance
                    self.ghost_pos = ghost_pos

            if self.flee > 0:
                self.flee -= 1
                action = max(
                    self.field.connected_neighbours(self.pos),
                    key=lambda dp: self.field.distance(dp[1], self.ghost_pos)
                )[0]
                # self.debug('flee: ghost_pos {} pos {} dir {} dist {}'.format(
                #     self.ghost_pos, self.pos, DIRECTIONS[action], self.field.distance(self.pos, self.ghost_pos)))
            else:
                self.ghost_pos = self.ghost_distance = None
                action = self.chase((POWER_PELLET, FRUIT))
                if action is None:
                    action = self.chase((PELLET,))
                if action is None:
                    action = random.choice(range(5))
                    if action > 3:
                        action = None

        # Detect power pellet
        if action is None:
            next_pos = self.pos
        else:
            next_pos = self.field.go_dir_id(self.pos, action)
        if self.mem_field[next_pos] == POWER_PELLET:
            self.power = 9
        elif self.invincible and self.mem_field[next_pos] == GHOST:
            self.debug('Got a ghost!')
        else:
            self.power = max(0, self.power - 1)
        return action

    def debug(self, *args, **kwargs):
        return
        print(*args, file=sys.stderr, **kwargs)


def start_game(player_class):
    field = Field(input())
    player = player_class(field)
    while True:
        line = input()
        if line == 'Q':
            break
        objects = [(tuple(map(int, x[:-1].split(',')))[::-1], x[-1]) for x in line.split(' ')]
        action = player.interact(objects)
        player.send('NESW'[action] if action is not None else 'X')


if __name__ == '__main__':
    start_game(Pathy)