Membuat program deterministik untuk bermain n ^d tic-tac-toe dengan kontestan lain.

Program Anda harus bekerja ketika n(lebar) dan d(nomor dimensi) berada dalam rentang ini:

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

n = 3; d = 2(3 ² yaitu 3 oleh 3):

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

n = 3; d = 3(3 ³ yaitu 3 oleh 3 oleh 3):

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

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

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

n = 6; d = 2(6 ² yaitu 6 oleh 6):

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

Dan seterusnya.

Memasukkan:

Masukan akan ke STDIN. Baris input pertama adalah dua angka, ndan ddalam bentuk n,d.

Setelah ini akan menjadi garis yang terdiri dari koordinat yang menentukan langkah-langkah yang telah dilakukan. Koordinat akan terdaftar dalam bentuk: 1,1;2,2;3,3. Pojok kiri atas adalah asal (0,0 untuk 2D). Dalam kasus umum, daftar ini akan seperti di 1,2,...,1,4;4,0,...,6,0;...mana angka pertama mewakili kiri-kanan, kedua naik ke atas, ketiga melalui dimensi ke-3, dll. Perhatikan bahwa koordinat pertama adalah Xgiliran pertama, yang kedua adalah Ogiliran pertama, ....

Jika ini merupakan langkah pertama, input akan berupa angka diikuti oleh 1 baris kosong.

Untuk konsistensi, input akan selalu diakhiri dengan baris baru. Input Sampel (\ n adalah baris baru):

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

Untuk langkah pertama:

10,10\n\n

di mana \nkarakter baris baru.

Keluaran:

Keluarkan langkah yang ingin Anda buat dalam format yang sama dengan input (daftar yang dipisahkan koma). Langkah yang tidak valid (yaitu yang sudah diambil) akan menghasilkan kerugian untuk permainan.

Catatan: Anda dapat menggunakan generator angka acak, asalkan Anda menaburnya dengan nilai sedemikian rupa sehingga setiap proses akan sama dengan kondisi yang sama. Dengan kata lain, program harus bersifat deterministik.

Catatan: hanya gerakan yang sah yang diizinkan.

Winning Games (Jika Anda telah memainkan cukup banyak tac toe tic multi-dimensi, ini adalah sama.)

Agar menang, satu pemain harus memiliki semua kotak yang berdekatan di sepanjang garis. Artinya, pemain itu harus nbergerak pada garis untuk menjadi pemenang.

Berdekatan:

• setiap ubin adalah sebuah titik; misalnya (0,0,0,0,0) adalah titik did=5
• ubin yang berdekatan adalah ubin sedemikian rupa sehingga keduanya merupakan titik pada unit d-cube yang sama. Dengan kata lain, jarak Chebyshev antara ubin adalah 1.
• dengan kata lain, jika suatu titik pberbatasan dengan suatu titik q, maka setiap koordinat dalam pkoordinat yang sesuai qberbeda darinya dengan tidak lebih dari satu. Selain itu, setidaknya pada pasangan koordinat berbeda dengan tepat satu.

Garis:

• Garis ditentukan oleh vektor dan ubin. Garis adalah setiap ubin yang terkena persamaan:p0 + t<some vector with the same number of coordinates as p0>

Kondisi Simulasi dan Menang:

• Nyatakan jawaban Anda jika siap untuk dinilai. Artinya, jelas menunjukkan apakah jawaban Anda sudah selesai atau belum.

• Jika jawaban Anda ditandai sudah selesai, ia tidak akan dinilai setidaknya 24 jam setelah pengeditan terakhir pada kode.

• Program harus bekerja offline. Jika suatu program terbukti curang, maka secara otomatis akan menerima skor -1, dan tidak akan dinilai lebih lanjut. (Bagaimana orang akan berakhir dengan program mereka curang?)

• Jika program Anda menghasilkan output yang tidak valid, itu langsung dihitung sebagai kerugian untuk game

• Jika program Anda gagal menghasilkan output setelah 1 menit, itu langsung dihitung sebagai kerugian untuk permainan. Jika perlu, optimalkan kecepatannya. Saya tidak mau harus menunggu satu jam untuk menguji program dari yang lain.

• Setiap program akan dijalankan terhadap program lain dua kali untuk masing-masing ndalam jangkauan [3,6]dan masing-masing ddalam jangkauan [2,5], sekali sebagai Xdan sekali sebagai O. Ini satu putaran.

• Untuk setiap permainan, sebuah program menang, ia +3mencapai skornya. Jika program diikat (1 menang dan 1 kalah dalam satu putaran atau seri untuk kedua game), maka itu didapat +1. Jika program hilang, maka ia mendapat +0(yaitu tidak ada perubahan).

• Program dengan skor tertinggi menang. Jika ada seri, maka program dengan jumlah game yang kalah paling sedikit (dari kontestan yang diikat) menang.

Catatan: Bergantung pada jumlah jawaban, saya mungkin perlu bantuan menjalankan tes.

Semoga berhasil! Dan semoga simulasi berjalan sesuai keinginan Anda!

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

Ini hanyalah ai acak. Ini secara acak memilih langkah keluar dari langkah yang masih tersedia.

Python 2.7

Ini adalah karya dalam proses yang saya berikan untuk memberikan kerangka / inspirasi kepada penjawab lain. Ini bekerja dengan mendaftar setiap kemungkinan garis kemenangan, kemudian menerapkan beberapa heuristik untuk mencetak garis itu sesuai dengan betapa berharganya itu. Saat ini, heuristik kosong (pekerjaan super rahasia). Saya juga menambahkan penanganan kesalahan menang dan bentrok.

Catatan tentang masalahnya

Ada berapa garis kemenangan? Pertimbangkan kasus 1 dimensi; ada 2 simpul, 1 tepi, dan 1 garis. Dalam 2 dimensi, kami memiliki 4 simpul yang bergabung dengan 2 garis, dan 4 ujung yang bergabung dengan 2 * n garis. Dalam 3 dimensi, kami memiliki 8 simpul bergabung dengan 4 garis, 12 tepi bergabung dengan 6 * n garis, dan 6 wajah bergabung dengan 3*n^2garis.

Secara umum, mari kita sebut simpul 0-segi, tepi 1-segi, dll. Lalu mari N(i) menyatakan jumlah i-segi, djumlah dimensi, dan npanjang sisi. Maka jumlah baris yang menang adalah 0.5*sum(N(i)*n^i,i=0..d-1).

Per wikipedia, N(i)=2^(d-i)*d!/(i!*(n-1)!) jadi rumus terakhirnya adalah:

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

yang wolfram | alpha tidak terlalu suka. Ini menjadi sangat besar dengan sangat cepat, jadi saya tidak berharap program saya memiliki runtime yang dapat dikelola untuk d> 8.

Beberapa hasil (maaf tentang pemformatan:

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

Saat ini, input perlu dimasukkan sebagai: tictactoe.py <ret> n,d <ret> move;move <ret> - perhatikan beberapa baris dan tidak ada akhir ;.

Outputnya seperti (x_1,x_2,x_3...) , misalnya:

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

Sunting: untuk I / O, tambahkan logika. Saya percaya ini sekarang siap untuk ditandai

Perhatikan bahwa komentar ini awalnya adalah placeholder yang saya hapus dan batalkan penghapusan.

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

Sebagian besar kode persis sama dengan AI acak Quincunx . Alih-alih memilih langkah secara acak, ia memilih langkah yang tersedia pertama secara leksikografis (yaitu (0,0, ... 0), lalu (0,0, ... 1), lalu (0,0, ... 2) , dll.).

Ini adalah strategi sampah yang cukup, tetapi hampir selalu mengalahkan secara acak.