The Tic-tac-toe Games

Question

Create a deterministic program to play n^d tic-tac-toe with the other contestants.

Your program should work when n (width) and d (dimension number) are in these ranges:

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

n = 3; d = 2 (3² ie 3 by 3):

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

n = 3; d = 3 (3³ ie 3 by 3 by 3):

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

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

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

n = 6; d = 2 (6² ie 6 by 6):

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

And so on.

Input:

Input will be to STDIN. The first line of input will be two numbers, n and d in the form n,d.

After this will be a line consisting of coordinates specifying the moves that have been done. Coordinates will be listed in the form: 1,1;2,2;3,3. The upper left corner is the origin ( 0,0 for 2D). In the general case, this list will be like 1,2,...,1,4;4,0,...,6,0;... where the first number represents left-right-ness, the second up-down-ness, the third through the 3rd dimension, etc. Note that the first coordinate is Xs first turn, the second is Os first turn, ....

Should this be the first move, the input will a number followed by 1 blank line.

For consistency, the input will always end with a newline. Sample Input (\n is 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

For first move:

10,10\n\n

where \n is the newline character.

Output:

Output the move you wish to make in the same format as the input (a comma-separated list). An invalid move (ie one that has already been taken) will result in a loss for the game.

Note: You can use a random number generator, as long as you seed it with a value such that each run would be identical given the same conditions. In other words, the program must be deterministic.

Note: only valid moves are allowed.

Winning Games (If you've played enough multi-dimensional tic tac toe, this is the same.)

In order for there to be a win, one player must have all the adjacent squares along a line. That is, that player must have n moves on a line to be a winner.

Adjacent:

• each tile is a point; for example (0,0,0,0,0) is a point in d=5
• adjacent tiles are tiles such they are both points on the same unit d-cube. In other words, the Chebyshev distance between the tiles is 1.
• in other words, if a point p is adjacent to a point q, then every coordinate in ps corresponding coordinate in q differs from it by no more than one. Additionally, at least on coordinate pair differs by exactly one.

Lines:

• Lines are defined by vectors and a tile. A line is each tile hit by the equation: p0 + t<some vector with the same number of coordinates as p0>

Simulation and Winning Conditions:

• State in your answer if it is ready for grading. That is, clearly indicate whether or not your answer is done.

• If your answer is marked as done, it will not be graded until at least 24 hours after the last edit to the code.

• Programs must work offline. If a program is found to be cheating, it will automatically receive a score of -1, and will not be scored further. (How would anyone end up with their programs cheating?)

• If your program produces invalid output, it is immediately counted as a loss for the game

• If you program fails to produce output after 1 minute it is immediately counted as a loss for the game. If necessary, optimize for speed. I don't want to have to wait an hour to test a program off of another.

• Each program will be run against the other programs twice for each n in the range [3,6] and each d in the range [2,5], once as X and once as O. This is one round.

• For each game a program wins, it gets +3 to its score. If the program tied (1 win and 1 loss in a single round or ties for both games), then it gets +1. If the program lost, then it gets +0 (ie no change).

• The program with the highest score wins. Should there be a tie, then the program with the least number of lost games (out of the tied contestants) wins.

Note: Depending on the number of answers, I may need help running the tests.

Good luck! And may the simulations run ever in your favor!

Answer 1

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

This is simply a random ai. It randomly selects a move out of the moves that are still available.

Answer 2

Python 2.7

This is a work-in-progress submission which I'm providing to give a skeleton/inspiration to other answerers. It works by listing every possible winning line, then applying some heuristic to score that line according to how valuable it is. Currently, the heuristic is blank (super-secret workings). I have also added win and clash error handling.

Notes on the problem

How many winning lines are there? Consider the 1-dimensional case; there are 2 vertices, 1 edge, and 1 line. In 2 dimensions, we have 4 vertices joined by 2 lines, and 4 edges joined by 2*n lines. In 3 dimensions, we have 8 vertices joined by 4 lines, 12 edges joined by 6*n lines, and 6 faces joined by 3*n^2 lines.

In general, let us call a vertex a 0-facet, an edge a 1-facet, etc. Then let N(i) denote the number of i-facets, d the number of dimensions, and n the side length. Then the number of winning lines is 0.5*sum(N(i)*n^i,i=0..d-1).

Per wikipedia, N(i)=2^(d-i)*d!/(i!*(n-1)!), so the final formula is:

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

which wolfram|alpha doesn't like very much. This gets very large pretty quickly, so I don't expect my program to have manageable runtime for d>8.

Some results (sorry about the formatting:

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

At the moment, the input needs to be input as: tictactoe.py <ret> n,d <ret> move;move <ret> - note the multiple lines and no final ;.

The output looks like (x_1,x_2,x_3...), for instance:

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: for I/O, added logic. I believe this is now ready to mark

Note that this comment was initially a placeholder which I deleted and undeleted.

Answer 3

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

Most of the code is exactly the same as Quincunx's random AI. Instead of randomly selecting a move, it picks the first available move lexicographically (i.e. (0,0,...0), then (0,0,...1), then (0,0,...2), etc.).

This is a pretty rubbish strategy, but it almost always beats playing at random.