Создать детерминированную программу для воспроизведения п ^d крестиков-ноликов с другими соперниками.

Ваша программа должна работать, когда n(ширина) и d(номер измерения) находятся в следующих диапазонах:

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

n = 3; d = 2(3 ^2, т.е. 3 на 3):

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

n = 3; d = 3(3 ^3, т.е. 3 на 3 на 3):

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

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

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

n = 6; d = 2(6 ^2, т.е. 6 на 6):

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

И так далее.

Входные данные:

Вход будет в STDIN. Первая строка ввода будет двумя числами nи dв форме n,d.

После этого будет строка, состоящая из координат, определяющих ходы, которые были сделаны. Координаты будут перечислены в следующем виде: 1,1;2,2;3,3. Верхний левый угол - это начало координат (0,0 для 2D). В общем случае этот список будет аналогичен тому, 1,2,...,1,4;4,0,...,6,0;...где первое число представляет левый-правый, второй-вверх-вниз, с третьего по третье измерение и т. Д. Обратите внимание, что первая координата - это Xпервый поворот, второй Это Oпервый поворот, ....

Если это будет первым ходом, вводом будет число, за которым следует 1 пустая строка.

Для согласованности ввод всегда заканчивается новой строкой. Пример ввода (\ n - новая строка):

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

Для первого хода:

10,10\n\n

где \nсимвол новой строки.

Выход:

Выведите ход, который вы хотите сделать, в том же формате, что и ввод (список через запятую). Неверный ход (т. Е. Тот, который уже был сделан) приведет к проигрышу в игре.

Примечание: Вы можете использовать генератор случайных чисел, если вы заполняете его значением, таким образом, чтобы каждый прогон был идентичен при одинаковых условиях. Другими словами, программа должна быть детерминированной.

Примечание: разрешены только действительные ходы.

Игры-победители (если вы играли в достаточно многогранные крестики-нолики, это то же самое.)

Чтобы победа была, у одного игрока должны быть все смежные квадраты вдоль линии. То есть этот игрок должен иметь nходы на линии, чтобы быть победителем.

Рядом:

• каждая плитка - это точка; например (0,0,0,0,0) является точкой вd=5
• соседние плитки - это плитки, так что они обе являются точками на одном и том же d-кубе. Другими словами, расстояние Чебышева между плитками равно 1.
• другими словами, если точка pсмежна с точкой q, то каждая координата в ps соответствующей координате qотличается от нее не более чем на единицу. Кроме того, хотя бы пара координат отличается ровно на одну.

линии:

• Линии определяются векторами и плиткой. Линия - это каждая ячейка, пораженная уравнением:p0 + t<some vector with the same number of coordinates as p0>

Условия симуляции и выигрыша:

• Укажите в своем ответе, готов ли он к оценке. То есть четко укажите, выполнен ли ваш ответ.

• Если ваш ответ помечен как выполненный, он не будет оценен, по крайней мере, через 24 часа после последнего редактирования кода.

• Программы должны работать в автономном режиме. Если программа обнаруживает мошенничество, она автоматически получит оценку -1и больше не будет оцениваться. (Как бы кто-нибудь в конечном итоге обманул их программы?)

• Если ваша программа выдает неверный вывод, она сразу же считается проигрышем для игры

• Если ваша программа не выдает результат через 1 минуту, это сразу же считается проигрышем для игры. При необходимости оптимизируйте скорость. Я не хочу ждать час, чтобы протестировать программу другого.

• Каждая программа будет запущена против других программ дважды для каждой nв диапазоне [3,6]и каждой dв диапазоне [2,5], один раз как Xи один раз как O. Это один раунд.

• За каждую игру, которую выигрывает программа, она получает +3свой счет. Если программа связана (1 победа и 1 поражение в одном раунде или ничья в обеих играх), то она получает +1. Если программа потеряна, то она получает +0(т.е. без изменений).

• Программа с наибольшим количеством очков выигрывает. Если будет ничья, то выигрывает программа с наименьшим количеством проигранных игр (из числа соперников).

Примечание. В зависимости от количества ответов мне может понадобиться помощь в проведении тестов.

Удачи! И пусть симуляторы всегда идут вам на пользу!

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

Это просто случайный ай. Он случайным образом выбирает ход из ходов, которые все еще доступны.

Python 2.7

Это представление в процессе разработки, которое я предоставляю, чтобы дать скелет / вдохновение другим ответчикам. Он работает, перечисляя каждую возможную выигрышную линию, а затем применяя эвристику для оценки этой строки в соответствии с ее ценностью. В настоящее время эвристика пуста (сверхсекретные работы). Я также добавил обработку ошибок win и clash.

Примечания по проблеме

Сколько выигрышных линий? Рассмотрим одномерный случай; Есть 2 вершины, 1 ребро и 1 линия. В двух измерениях у нас есть 4 вершины, соединенные 2 линиями, и 4 ребра, соединенные 2 * n линиями. В 3 измерениях у нас есть 8 вершин, соединенных 4 линиями, 12 ребер, соединенных 6 * n линиями, и 6 граней, соединенных 3*n^2линиями.

В общем, давайте назовем вершину 0-гранью, ребро 1-гранью и т. Д. Затем N(i)обозначим число i-фасетов, dчисло измерений и nдлину стороны. Тогда количество выигрышных линий равно 0.5*sum(N(i)*n^i,i=0..d-1).

Согласно википедии N(i)=2^(d-i)*d!/(i!*(n-1)!), итоговая формула:

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

какой вольфрам | альфа не очень любит. Это становится очень большим довольно быстро, поэтому я не ожидаю, что моя программа будет иметь управляемое время выполнения для d> 8.

Некоторые результаты (извините за форматирование:

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

На данный момент ввод должен быть введен как: tictactoe.py <ret> n,d <ret> move;move <ret>- обратите внимание на несколько строк и без финала ;.

Вывод выглядит так (x_1,x_2,x_3...), например:

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

Редактировать: для ввода / вывода, добавлена ​​логика. Я полагаю, что это теперь готово отметить

Обратите внимание, что этот комментарий изначально был заполнителем, который я удалил и удалил.

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

Большая часть кода точно такая же, как случайный ИИ Quincunx . Вместо случайного выбора хода он выбирает первый доступный ход лексикографически (то есть (0,0, ... 0), затем (0,0, ... 1), затем (0,0, ... 2) , и т.д.).

Это довольно мусорная стратегия, но она почти всегда превосходит игру наугад.