Créer un programme déterministe pour jouer n ^d tic-tac-toe avec les autres participants.

Votre programme devrait fonctionner lorsque n(largeur) et d(numéro de dimension) se trouvent dans ces plages:

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

n = 3; d = 2(3 ² soit 3 par 3):

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

n = 3; d = 3(3 ³ soit 3 par 3 par 3):

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

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

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

n = 6; d = 2(6 ² soit 6 par 6):

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

Etc.

Contribution:

L'entrée sera vers STDIN. La première ligne de saisie sera composée de deux nombres net dsous la forme n,d.

Après cela sera une ligne composée de coordonnées spécifiant les mouvements qui ont été effectués. Les coordonnées seront listés sous la forme: 1,1;2,2;3,3. Le coin supérieur gauche est l'origine (0,0 pour 2D). Dans le cas général, cette liste sera comme 1,2,...,1,4;4,0,...,6,0;...où le premier nombre représente la gauche-droite-ness, la deuxième haut-bas-ness, la troisième à la 3ème dimension, etc. Notez que la première coordonnée est Xs premier tour, la seconde c'est Ole premier tour, ....

Si c'est le premier mouvement, l'entrée sera un nombre suivi d'une ligne vierge.

Par souci de cohérence, l'entrée se terminera toujours par une nouvelle ligne. Exemple d'entrée (\ n est une nouvelle ligne):

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

Pour le premier coup:

10,10\n\n

où \nest le caractère de nouvelle ligne.

Production:

Sortez le déplacement que vous souhaitez effectuer dans le même format que l'entrée (une liste séparée par des virgules). Un coup invalide (c'est-à-dire un coup déjà effectué) entraînera une perte pour le jeu.

Remarque: Vous pouvez utiliser un générateur de nombres aléatoires, tant que vous l'amorcez avec une valeur telle que chaque exécution serait identique dans les mêmes conditions. En d'autres termes, le programme doit être déterministe.

Remarque: seuls les déplacements valides sont autorisés.

Jeux gagnants (Si vous avez joué suffisamment de tic tac toe multidimensionnel, c'est la même chose.)

Pour qu'il y ait une victoire, un joueur doit avoir toutes les cases adjacentes le long d'une ligne. Autrement dit, ce joueur doit avoir des nmouvements sur une ligne pour être gagnant.

Adjacent:

• chaque tuile est un point; par exemple (0,0,0,0,0) est un pointd=5
• les tuiles adjacentes sont des tuiles telles qu'elles sont les deux points sur la même unité d-cube. En d'autres termes, la distance de Chebyshev entre les tuiles est de 1.
• en d'autres termes, si un point pest adjacent à un point q, alors chaque coordonnée en ps coordonnée correspondante en ne qdiffère pas de plus d'un. De plus, au moins sur la paire de coordonnées diffère exactement d'un.

Lignes:

• Les lignes sont définies par des vecteurs et une tuile. Une ligne est chaque tuile frappée par l'équation:p0 + t<some vector with the same number of coordinates as p0>

Conditions de simulation et de gain:

• Indiquez dans votre réponse si elle est prête pour le classement. Autrement dit, indiquez clairement si votre réponse est terminée ou non.

• Si votre réponse est marquée comme terminée, elle ne sera notée qu'au moins 24 heures après la dernière modification du code.

• Les programmes doivent fonctionner hors ligne. Si un programme est en train de tricher, il recevra automatiquement un score de -1, et ne sera pas noté plus loin. (Comment quelqu'un finirait-il par tricher avec ses programmes?)

• Si votre programme produit une sortie invalide, elle est immédiatement comptabilisée comme une perte pour le jeu

• Si votre programme ne produit pas de sortie après 1 minute, il est immédiatement comptabilisé comme une perte pour le jeu. Si nécessaire, optimisez pour la vitesse. Je ne veux pas avoir à attendre une heure pour tester un programme sur un autre.

• Chaque programme sera exécuté contre les autres programmes deux fois pour chacun ndans la plage [3,6]et chacun ddans la plage [2,5], une fois au fur Xet à mesure O. Ceci est un tour.

• Pour chaque match gagné par un programme, il atteint +3son score. Si le programme est à égalité (1 victoire et 1 défaite en un seul tour ou égalité pour les deux matchs), il obtient +1. Si le programme a perdu, il obtient +0(c'est-à-dire aucun changement).

• Le programme avec le score le plus élevé gagne. En cas d'égalité, le programme avec le moins de matchs perdus (parmi les concurrents à égalité) gagne.

Remarque: Selon le nombre de réponses, j'ai peut-être besoin d'aide pour exécuter les tests.

Bonne chance! Et que les simulations fonctionnent toujours en votre faveur!

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

Il s'agit simplement d'un ai aléatoire. Il sélectionne au hasard un mouvement parmi les mouvements encore disponibles.

Python 2.7

Il s'agit d'une soumission de travail en cours que je fournis pour donner un squelette / inspiration à d'autres répondeurs. Il fonctionne en répertoriant toutes les lignes gagnantes possibles, puis en appliquant une heuristique pour marquer cette ligne en fonction de sa valeur. Actuellement, l'heuristique est vide (fonctionnement super secret). J'ai également ajouté la gestion des erreurs de victoire et de conflit.

Notes sur le problème

Combien y a-t-il de lignes gagnantes? Prenons le cas unidimensionnel; il y a 2 sommets, 1 arête et 1 ligne. En 2 dimensions, nous avons 4 sommets joints par 2 lignes, et 4 arêtes jointes par 2 * n lignes. En 3 dimensions, nous avons 8 sommets joints par 4 lignes, 12 bords joints par 6 * n lignes et 6 faces jointes par des 3*n^2lignes.

En général, appelons un sommet une facette 0, une arête une facette 1, etc. N(i)Notons ensuite le nombre de facettes i, dle nombre de dimensions et nla longueur du côté. Ensuite, le nombre de lignes gagnantes est 0.5*sum(N(i)*n^i,i=0..d-1).

Par wikipedia, N(i)=2^(d-i)*d!/(i!*(n-1)!)la formule finale est donc:

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

quel wolfram | alpha n'aime pas beaucoup. Cela devient très grand assez rapidement, donc je ne m'attends pas à ce que mon programme ait un temps d'exécution gérable pour d> 8.

Quelques résultats (désolé pour le formatage:

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

E / S

Pour le moment, l'entrée doit être entrée comme: tictactoe.py <ret> n,d <ret> move;move <ret>- notez les lignes multiples et aucune finale ;.

La sortie ressemble (x_1,x_2,x_3...), par exemple:

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

Edit: pour les E / S, logique ajoutée. Je crois que c'est maintenant prêt à marquer

Notez que ce commentaire était initialement un espace réservé que j'ai supprimé et restauré.

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

La plupart du code est exactement le même que l'IA aléatoire de Quincunx . Au lieu de sélectionner aléatoirement un coup, il sélectionne le premier coup disponible lexicographiquement (ie (0,0, ... 0), puis (0,0, ... 1), puis (0,0, ... 2) , etc.).

Il s'agit d'une stratégie assez poubelle, mais elle bat presque toujours au hasard.