Erstellen Sie ein deterministisches Programm zu spielen n ^d Tic-Tac-Toe mit den anderen Kandidaten.

Ihr Programm sollte funktionieren, wenn n(width) und d(dimension number) in diesen Bereichen liegen:

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

n = 3; d = 2(3 ^2, dh 3 mal 3):

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

n = 3; d = 3(3 ³ dh 3 mal 3 mal 3):

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

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

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

n = 6; d = 2(6 ^2, dh 6 mal 6):

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

Und so weiter.

Eingang:

Die Eingabe erfolgt in STDIN. Die erste Zeile der Eingabe wird zwei Zahlen, sein nund din der Form n,d.

Danach wird eine Linie aus Koordinaten erstellt, die die durchgeführten Bewegungen angeben. Die Koordinaten werden in Form aufgeführt werden: 1,1;2,2;3,3. Die obere linke Ecke ist der Ursprung (0,0 für 2D). Im allgemeinen Fall entspricht diese Liste der Stelle, 1,2,...,1,4;4,0,...,6,0;...an der die erste Zahl die Links-Rechts-Position, die zweite Auf-Ab-Position, die dritte bis dritte Dimension usw. darstellt. Beachten Sie, dass die erste Koordinate die Xerste und die zweite Kurve ist ist Os erste Runde, ....

Sollte dies der erste Zug sein, wird bei der Eingabe eine Zahl gefolgt von einer Leerzeile eingegeben.

Aus Gründen der Konsistenz endet die Eingabe immer mit einem Zeilenumbruch. Beispieleingabe (\ n ist Newline):

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

Für den ersten Zug:

10,10\n\n

Wo \nist das Newline-Zeichen?

Ausgabe:

Geben Sie den Zug, den Sie ausführen möchten, in demselben Format wie die Eingabe aus (eine durch Kommas getrennte Liste). Ein ungültiger Zug (dh ein Zug, der bereits ausgeführt wurde) führt zu einem Verlust für das Spiel.

Hinweis: Sie können einen Zufallszahlengenerator verwenden, solange Sie einen Wert festlegen, bei dem jeder Lauf unter den gleichen Bedingungen identisch ist. Mit anderen Worten, das Programm muss deterministisch sein.

Hinweis: Es sind nur gültige Züge erlaubt.

Gewinnspiele (Wenn Sie genug mehrdimensionale Tic Tac Toe gespielt haben, ist dies dasselbe.)

Um zu gewinnen, muss ein Spieler alle angrenzenden Felder entlang einer Linie haben. Das heißt, dieser Spieler muss nZüge auf einer Linie haben, um ein Gewinner zu sein.

Benachbart:

• jedes Plättchen ist ein Punkt; Zum Beispiel ist (0,0,0,0,0) ein Punkt ind=5
• benachbarte Kacheln sind solche Kacheln, die beide Punkte auf derselben Einheit d-Würfel sind. Mit anderen Worten beträgt der Chebyshev-Abstand zwischen den Kacheln 1.
• Mit anderen Worten, wenn ein Punkt pan einen Punkt angrenzt q, unterscheidet sich jede Koordinate in der pentsprechenden Koordinate qdarin nicht mehr als um eins. Außerdem unterscheidet sich mindestens ein Koordinatenpaar um genau eins.

Linien:

• Linien werden durch Vektoren und eine Kachel definiert. Eine Linie ist jedes Plättchen, das von der folgenden Gleichung getroffen wird:p0 + t<some vector with the same number of coordinates as p0>

Simulations- und Gewinnbedingungen:

• Geben Sie in Ihrer Antwort an, ob sie zur Benotung bereit ist. Geben Sie also deutlich an, ob Ihre Antwort fertig ist oder nicht.

• Wenn Ihre Antwort als erledigt markiert ist, wird sie erst 24 Stunden nach der letzten Änderung des Codes bewertet.

• Programme müssen offline arbeiten. Wenn festgestellt wird, dass ein Programm betrügt, erhält es automatisch eine Punktzahl von -1und wird nicht weiter gewertet. (Wie würde jemand damit enden, dass seine Programme betrügen?)

• Wenn Ihr Programm eine ungültige Ausgabe erzeugt, wird dies sofort als Verlust für das Spiel gewertet

• Wenn Sie nach 1 Minute keine Ausgabe erstellen, wird dies sofort als Verlust für das Spiel gewertet. Bei Bedarf auf Geschwindigkeit optimieren. Ich möchte nicht eine Stunde warten müssen, um ein Programm von einem anderen zu testen.

• Jedes Programm wird zweimal für jedes nin dem Bereich [3,6]und jedes din dem Bereich [2,5]einmal als Xund einmal als gegen die anderen Programme ausgeführt O. Dies ist eine Runde.

• Für jedes Spiel, das ein Programm gewinnt, erreicht es +3seine Punktzahl. Wenn das Programm unentschieden ist (1 Sieg und 1 Niederlage in einer einzigen Runde oder Unentschieden für beide Spiele), wird es ausgeglichen +1. Wenn das Programm verloren geht, dann wird es +0(dh keine Änderung).

• Das Programm mit der höchsten Punktzahl gewinnt. Sollte es ein Unentschieden geben, gewinnt das Programm mit der geringsten Anzahl verlorener Partien (von den unentschieden ausgetragenen Teilnehmern).

Hinweis: Abhängig von der Anzahl der Antworten benötige ich möglicherweise Hilfe beim Ausführen der Tests.

Viel Glück! Und mögen die Simulationen jemals zu Ihren Gunsten ablaufen!

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))])))

Dies ist einfach ein zufälliges ai. Es wählt zufällig einen Zug aus den noch verfügbaren Zügen aus.

Python 2.7

Dies ist eine in Bearbeitung befindliche Einreichung, die ich zur Verfügung stelle, um anderen Antwortenden ein Skelett / eine Inspiration zu geben. Es funktioniert, indem jede mögliche Gewinnlinie aufgelistet und dann eine Heuristik angewendet wird, um diese Linie danach zu bewerten, wie wertvoll sie ist. Derzeit ist die Heuristik leer (Super-Secret-Arbeiten). Ich habe auch die Behandlung von Win- und Clash-Fehlern hinzugefügt.

Hinweise zum Problem

Wie viele Gewinnlinien gibt es? Betrachten Sie den eindimensionalen Fall. Es gibt 2 Eckpunkte, 1 Kante und 1 Linie. In 2 Dimensionen haben wir 4 Scheitelpunkte, die durch 2 Linien verbunden sind, und 4 Kanten, die durch 2 * n Linien verbunden sind. In 3 Dimensionen haben wir 8 Scheitelpunkte, die durch 4 Linien verbunden sind, 12 Kanten, die durch 6 * n Linien verbunden sind, und 6 Flächen, die durch 3*n^2Linien verbunden sind.

Nennen wir einen Scheitelpunkt im Allgemeinen eine 0-Facette, eine Kante eine 1-Facette usw. Dann N(i)bezeichnen wir die Anzahl der i-Facetten, ddie Anzahl der Dimensionen und ndie Seitenlänge. Dann ist die Anzahl der Gewinnlinien 0.5*sum(N(i)*n^i,i=0..d-1).

Per Wikipedia N(i)=2^(d-i)*d!/(i!*(n-1)!)lautet die endgültige Formel also:

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

welches wolfram | alpha nicht besonders mag. Das wird ziemlich schnell sehr groß, so dass ich nicht erwarte, dass mein Programm eine überschaubare Laufzeit für d> 8 hat.

Einige Ergebnisse (Entschuldigung für die Formatierung:

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

Im Moment muss die Eingabe wie folgt erfolgen: tictactoe.py <ret> n,d <ret> move;move <ret>- Beachten Sie die mehreren Zeilen und kein Finale ;.

Die Ausgabe sieht (x_1,x_2,x_3...)zum Beispiel so aus:

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() 

Bearbeiten: Für E / A Logik hinzugefügt. Ich glaube, das ist jetzt bereit zu markieren

Beachten Sie, dass dieser Kommentar ursprünglich ein Platzhalter war, den ich gelöscht und wieder hergestellt habe.

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

Der größte Teil des Codes ist genau derselbe wie die zufällige KI von Quincunx . Anstatt einen Zug zufällig auszuwählen, wählt er den ersten verfügbaren Zug lexikographisch aus (dh (0,0, ... 0), dann (0,0, ... 1), dann (0,0, ... 2). , etc.).

Dies ist eine ziemlich blöde Strategie, aber sie schlägt fast immer das Spielen nach dem Zufallsprinzip.