Tworzenie deterministycznego program do odegrania n ^d Kółko i krzyżyk z pozostałych zawodników.

Twój program powinien działać, gdy n(szerokość) id (numer wymiaru) znajdują się w następujących zakresach:

n∈[3,∞)∩ℕ  ie a natural number greater than 2
d∈[2,∞)∩ℕ  ie a natural number greater than 1

n = 3; d = 2(3 ² tj. 3 na 3):

[][][]
[][][]
[][][]

n = 3; d = 3(3 ³ tj. 3 na 3 na 3):

[][][]
[][][]
[][][]

[][][]
[][][]
[][][]

[][][]
[][][]
[][][]

n = 6; d = 2(6 ² tj. 6 na 6):

[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]

I tak dalej.

Wejście:

Dane wejściowe będą na STDIN. Pierwszy wiersz danych wejściowych będzie składał się z dwóch liczb noraz dw formien,d .

Następnie pojawi się linia składająca się ze współrzędnych określających wykonane ruchy. Współrzędne są wymienione w następującej postaci: 1,1;2,2;3,3. Lewy górny róg jest punktem początkowym (0,0 dla 2D). W ogólnym przypadku ta lista będzie wyglądać tak, jakby 1,2,...,1,4;4,0,...,6,0;...pierwsza liczba reprezentowała lewą prawą stronę, drugą górę-dół-ność, trzecią do trzeciego wymiaru itp. Zauważ, że pierwsza współrzędna to Xpierwsza kolej, druga jest Opierwsza kolej, ....

Jeśli będzie to pierwszy ruch, na wejściu pojawi się liczba, po której nastąpi 1 pusty wiersz.

Aby zachować spójność, dane wejściowe zawsze kończą się nową linią. Przykładowe dane wejściowe (\ n to nowa linia):

10,10\n0,0,0,0,0,0,0,0,0,0;0,2,3,4,5,6,7,8,9,0;0,1,2,3,4,5,6,7,8,9\n

Do pierwszego ruchu:

10,10\n\n

gdzie \njest znak nowej linii.

Wynik:

Wyjdź ruch, który chcesz wykonać, w tym samym formacie, co dane wejściowe (lista oddzielona przecinkami). Nieprawidłowy ruch (tj. Taki, który został już wykonany) spowoduje przegraną w grze.

Uwaga: Możesz użyć generatora liczb losowych, o ile wysyłasz go taką wartością, aby każdy przebieg był identyczny w tych samych warunkach. Innymi słowy, program musi być deterministyczny.

Uwaga: dozwolone są tylko prawidłowe ruchy.

Zwycięskie gry (jeśli grałeś wystarczająco dużo wielowymiarowych kółko i krzyżyk, to tak samo.)

Aby wygrać, jeden gracz musi mieć wszystkie sąsiadujące pola wzdłuż linii. Oznacza to, że gracz musi mieć nruchy na linii, aby zostać zwycięzcą.

Sąsiadujący:

• każda płytka jest punktem; na przykład (0,0,0,0,0) to punkt wd=5
• sąsiadujące płytki są płytkami, więc oba są punktami na tej samej jednostce d-cube. Innymi słowy, odległość Czebyszewa między płytkami wynosi 1.
• innymi słowy, jeśli punkt pprzylega do punktu q, wówczas każda współrzędna w podpowiedniej współrzędnej in qróżni się od niej nie więcej niż o jeden. Dodatkowo przynajmniej para współrzędnych różni się dokładnie o jeden.

Linie:

• Linie są definiowane przez wektory i kafelki. Linia to każda płytka dotknięta równaniem:p0 + t<some vector with the same number of coordinates as p0>

Symulacja i warunki wygranej:

• Podaj w swojej odpowiedzi, czy jest gotowy do oceny. Oznacza to, że wyraźnie wskaż, czy twoja odpowiedź została wykonana.

• Jeśli twoja odpowiedź jest oznaczona jako zrobiona, nie będzie oceniana aż do co najmniej 24 godzin po ostatniej edycji kodu.

• Programy muszą działać w trybie offline. Jeśli okaże się, że program oszukuje, automatycznie otrzyma wynik -1i nie będzie dalej oceniany. (Jak ktokolwiek skończyłby z oszustwem w swoich programach?)

• Jeśli twój program generuje nieprawidłowe dane wyjściowe, jest to od razu liczone jako strata dla gry

• Jeśli program nie generuje wyników po 1 minucie, jest to od razu liczone jako strata dla gry. W razie potrzeby zoptymalizuj szybkość. Nie chcę czekać godzinę, aby przetestować inny program.

• Każdy program będzie uruchamiany z innymi programami dwa razy dla każdego nz zakresu [3,6]i każdego dz zakresu [2,5], raz Xi raz jako O. To jest jedna runda.

• Dla każdej gry, którą wygrywa program, osiąga +3swój wynik. Jeśli program remisuje (1 wygrana i 1 przegrana w jednej rundzie lub remisy w obu grach), to dostaje +1. Jeśli program się zgubił, to dostaje +0(tj. Bez zmian).

• Program z najwyższym wynikiem wygrywa. W przypadku remisu wygrywa program z najmniejszą liczbą przegranych gier (spośród remisujących zawodników).

Uwaga: W zależności od liczby odpowiedzi może być potrzebna pomoc w przeprowadzeniu testów.

Powodzenia! I niech symulacje przebiegną zawsze na twoją korzyść!

Python 3

import random as rand
import re

def generateMoves(width, dim):
    l = [0] * dim
    while existsNotX(l, width - 1):
        yield l[:]
        for i in range(dim):
            if l[i] < width - 1:
                l[i] += 1
                break
            else:
                l[i] = 0
    yield l

def existsNotX(l, x):
    for i in l:
        if i != x:
            return True
    return False

input_s = input()
dims, moves = None, None
#this is to allow input as a single paste, instead of ENTER inputting.
try:
    dims, moves = input_s.splitlines()
except ValueError:
    dims = input_s
    moves = input()

rand.seed(moves + dims)

dims = eval(dims) #change into tuple

moves = moves.split(';')
if len(moves[0]):
    moves = [eval(m) for m in moves] #change into tuples

output =[x for x in generateMoves(dims[0], dims[1]) if x not in moves]
print(re.sub('[^\\d,]', '', str(output[rand.randint(0, len(output))])))

To jest po prostu losowy ai. Losowo wybiera ruch spośród ruchów, które są nadal dostępne.

Python 2.7

To jest praca w toku, którą dostarczam, aby dać szkielet / inspirację innym użytkownikom. Działa, wymieniając każdą możliwą zwycięską linię, a następnie stosując heurystykę, aby zdobyć tę linię zgodnie z jej wartością. Obecnie heurystyka jest pusta (super tajne działania). Dodałem także obsługę błędów wygranych i kolizji.

Uwagi na temat problemu

Ile jest wygranych linii? Rozważ przypadek 1-wymiarowy; są 2 wierzchołki, 1 krawędź i 1 linia. W 2 wymiarach mamy 4 wierzchołki połączone 2 liniami i 4 krawędzie połączone 2 * n liniami. W 3 wymiarach mamy 8 wierzchołków połączonych 4 liniami, 12 krawędzi połączonych 6 * n liniami i 6 ścian połączonych 3*n^2liniami.

Zasadniczo nazwijmy wierzchołek 0-aspektem, krawędź 1-aspektem itp. Następnie N(i)oznaczmy liczbę i-aspektów, dliczbę wymiarów i ndługość boku. Zatem liczba wygrywających linii wynosi0.5*sum(N(i)*n^i,i=0..d-1) .

Według Wikipedii, N(i)=2^(d-i)*d!/(i!*(n-1)!)więc końcowa formuła to:

sum(2^(d-i-1) n^i d! / (i! * (n-i)!),i=0..d-1)

który wolfram | alpha nie bardzo lubi. To robi się bardzo duże dość szybko, więc nie oczekuję, że mój program będzie miał wykonalne środowisko uruchomieniowe dla d> 8.

Niektóre wyniki (przepraszam za formatowanie:

d\n 0   1    2      3      4       5        6        7         8         9
0   1   1    1      1      1       1        1        1         1         1
1   2   4    6      8      10      12       14       16        18        20
2   4   11   26     47     74      107      146      191       242       299
3   8   40   120    272    520     888      1400     2080      2952      4040
4   16  117  492    1437   3372    6837     12492    21117     33612     50997
5   32  364  2016   7448   21280   51012    107744   206896    368928    620060
6   64  1093 8128   37969  131776  372709   908608   1979713   3951424   7352101
7   128 3280 32640  192032 807040  2687088  7548800  18640960  41611392  85656080
8   256 9834 130809 966714 4907769 19200234 62070009 173533434 432891129 985263594

I / O

W tej chwili dane wejściowe należy wprowadzić jako: tictactoe.py <ret> n,d <ret> move;move <ret>- zanotuj wiele wierszy, a nie końcowy ;.

Dane wyjściowe wyglądają (x_1,x_2,x_3...)na przykład:

tictactoe.py <ret> 6,5 <ret> <ret> => 0, 0, 0, 0, 0

tictactoe.py <ret> 6,5 <ret> 0,0,0,0,0;0,0,0,0,5 <ret> => 0, 0, 0, 5, 0

# Notes on terminology:
#
# - A hypercube is the region [0,n]^d
# - An i-facet is an i-dimensional facet of a hypercube,
#   which is to say, a 0-facet is a vertex, a 1-facet an
#   edge, a 2-facet a face, and so on.
# - Any tuple {0,n}^i is a vertex of an i-hypercube
#   which is why I've used vertex to describe such
#   tuples
# - A winning line is a set of n coordinates which joins
#   two opposite i-facets
# - i-facets are opposite if they differ in every co-
#   ordinate which defines them
#
# Test Data:
#  


import numpy
import itertools

def removeDuplicates(seq):
    noDupes = []
    [noDupes.append(i) for i in seq if not noDupes.count(i)]
    return noDupes 


def listPairedVertices (i,n):
    """
    listPairedVertices returns a list L of elements of {0,n}^i which has the
    property that for every l in L, there does not exist l' such that
    l+l' = {n}^i.
    """

    vertices = numpy.array([[b*(n-1)  for b in a] for a in [
        list(map(int,list(numpy.binary_repr(x,i)))) for x in range(2**i)
    ]])
    result = []
    while len(vertices)>1:
        for j in range(len(vertices)):
            if numpy.all(vertices[j] + vertices[0] == [n-1]*i):
                result.append(vertices[0])
                vertices=numpy.delete(vertices,[0,j],axis=0)
                break
    return result


def listSequences (d,l):
    """
    listSequences returns the subset of {0,1}^d having precisely n 1s.
    """
    return numpy.array([
        r for r in itertools.product([0,1],repeat=d) if sum(r)==l
    ])


def listPaddedConstants (s,n):
    """
    listPaddedConstants takes a sequence in {0,1}^d and returns a number in
    {0..n}^sum(s) padded by s
    """
    result = numpy.zeros([n**sum(s),len(s)],dtype=numpy.int)
    for i,x in enumerate([list(z) for z in 
        itertools.product(range(n),repeat=sum(s))]):
        for j in range(len(s)):
            if s[j]: result[i][j] = x.pop()
    return result


def listWinningVectorsForDimension(d,i,n):
    """
    List the winning lines joining opposite i-facets of the hypercube.

    An i-facet is defined by taking a vertex v and a sequence s, then forming 
    a co-ordinate C by padding v with zeroes in the positions indicated by s.
    If we consider s = s_0.e_0 + s_1+e_1... where the e_j are the canonical
    basis for R^d, then the formula of the i-facet is 
        C+x_0.s_0.e_0+x_1.s_1.e_1... 
    for all vectors x = (x_0,x_1...) in R^n

    We know that winning lines only start at integral positions, and that the
    value of a will only be needed when s_j is nonempty, so the start point S
    of a winning line is in fact determined by:
     + vertex v in {0,n}^(d-i), padded by s
     + a in R^i, padded by the complement of s, s'

    Having performed the following operations, the co-ordinates of the winning
    lines are abs(S-k*s') for k in [0..n-1]
    """
    vertices = listPairedVertices(d-i,n)
    sequences = listSequences(d,i)
    result = []
    for s in sequences:
        for v in vertices:
            C = [0]*d
            j = 0
            for index in range(d):
                if s[index]: C[index] = 0
                else: 
                    C[index] = v[j]
                    j+=1
            result += [
                [numpy.absolute(S-k*(numpy.absolute(s-1))) for k in range(n)] 
                    for S in [C+a for a in listPaddedConstants(s,n)]
            ]
    return result


def AllWinningLines (d,n):
    """
    has the structure [[x_1,x_2,x_3],[y_1,y_2,y_3]] where each l_k is a
    length-d co-ordinate
    """
    result = []
    for i in range(d):
        result += listWinningVectorsForDimension(d,i,n)
    return result


def movesAlreadyMade ():
    """
    Returns a list of co-ordinates of moves already made read from STDIN
    """
    parameters = raw_input()
    moves = raw_input()
    parameters = list(map(int,parameters.split(',')))
    moves = [map(int,a.split(',')) for a in moves.split(';')] \
        if moves != '' else []
    return {'n':parameters[0], 'd':parameters[1], 'moves':moves}

def scoreLine (moves, line, scores, n):
    """
    Gives each line a score based on whatever logic I choose
    """
    myMoves          = moves[0::2]
    theirMoves       = moves[1::2]
    if len(moves)%2: myMoves, theirMoves = theirMoves, myMoves

    lineHasMyMove    = 0
    lineHasTheirMove = 0
    score            = 0

    for coord in line:
        if coord.tolist() in myMoves: 
            lineHasMyMove += 1
            if coord.tolist() in theirMoves: raise Exception('Move clash')
        elif coord.tolist() in theirMoves: lineHasTheirMove += 1

    if lineHasMyMove == len(line):
        raise Exception('I have won')
    elif lineHasTheirMove == len(line):
        raise Exception('They have won')
    elif lineHasMyMove and lineHasTheirMove: 
        pass
    elif lineHasTheirMove == len(line)-1: 
        score = n**lineHasTheirMove
    else: 
        score = n**lineHasMyMove

    for coord in line:
        if coord.tolist() not in moves: 
            scores[tuple(coord)]+=score

def main():
    """
    Throw it all together
    """
    data      = movesAlreadyMade()
    dimension = data['d']
    length    = data['n']
    lines     = AllWinningLines(dimension, length)
    scores    = numpy.zeros([length]*dimension, dtype=numpy.int)

    try: [scoreLine(data['moves'], line, scores, length) for line in lines]
    except Exception as E:
            print 'ERROR: ' + E.args[0]
            return
    print ','.join(map(
        str,numpy.unravel_index(numpy.argmax(scores),scores.shape)
        ))


if __name__ == "__main__": main() 

Edycja: dla I / O, dodano logikę. Wierzę, że jest to teraz gotowe do oznaczenia

Uwaga: ten komentarz był początkowo symbolem zastępczym, który usunąłem i usunąłem.

Python 2

import re
import itertools

input_s = raw_input()
dims, moves = None, None
#this is to allow input as a single paste, instead of ENTER inputting.
try:
    dims, moves = input_s.splitlines()
except ValueError:
    dims = input_s
    moves = raw_input()

dims = eval(dims) #change into tuple

moves = moves.split(';')
if len(moves[0]):
    moves = [eval(m) for m in moves] #change into tuples

allSpaces = [x for x in itertools.product(range(dims[0]), repeat=dims[1])]
move = None
for space in allSpaces:
    if space not in moves:
        move = space
        break
print(re.sub('[^\\d,]', '', str(move)))

Większość kodu jest dokładnie taka sama jak losowa sztuczna inteligencja Quincunx . Zamiast losowo wybierać ruch, wybiera pierwszy dostępny ruch leksykograficznie (tj. (0,0, ... 0), następnie (0,0, ... 1), a następnie (0,0, ... 2) itp.).

Jest to dość banalna strategia, ale prawie zawsze bije się losowo.