Let's play Meta tic-tac-toe!

Question

Lets play a game of Meta tic-tac-toe!

This is a king-of-the-hill tournament of Meta tic-tac-toe. The rules of Meta tic-tac-toe are as follows:

1. All of the regular rules of tic-tac-toe apply.

2. There are nine boards arranged to make one master board. Like so:

   0|1|2 || 0|1|2 || 0|1|2 
   ----- || ----- || ----- 
   3|4|5 || 3|4|5 || 3|4|5 
   ----- || ----- || ----- 
   6|7|8 || 6|7|8 || 6|7|8 
   ========================
   0|1|2 || 0|1|2 || 0|1|2 
   ----- || ----- || ----- 
   3|4|5 || 3|4|5 || 3|4|5 
   ----- || ----- || ----- 
   6|7|8 || 6|7|8 || 6|7|8 
   ========================
   0|1|2 || 0|1|2 || 0|1|2 
   ----- || ----- || ----- 
   3|4|5 || 3|4|5 || 3|4|5 
   ----- || ----- || ----- 
   6|7|8 || 6|7|8 || 6|7|8 
   

   board 0 refers to the top left board, board 1 refers to the top middle board... like this

   0|1|2
   -----
   3|4|5
   -----
   6|7|8
   

   If I say board 3, tile 4, that means the center tile of the board on the middle left.

3. You are only allowed to move in one of the smaller boards.

4. If you win one of the smaller boards, that entire board counts as your tile.

5. If one of the boards becomes filled before either bot has won it, it counts as nobodies tile.

6. Whoever wins the master board wins!

However, there is an important twist. Let's say I go in board 7, tile 2. That means on your turn, you can only go in board 2. Then let's say you go in board 2, tile 5. Now on my turn, I can only go in board 5. Let's say that board 1 is full. (There are no more spots left, or one of us has already won board 1) Now if I go in board 5, tile 1, you can go in any of the boards you want.

These rules can be regarded as:

1. You must play in the board corresponding to the position played by the previous player.
   • If X plays in board 2, tile 5; O must play in board 5
2. If the target board is full (a tie) or already has a victor, the next move is unconstrained.
3. A board with a winner may not be played into, even on an unconstrained move.

If this is a little bit confusing, you can try it online here. (make sure to switch from "first tile wins" to "3 tiles in a row")

Now here are the rules of the challenge.

1. You must write a bot that plays this game.

2. Bot 1 is Xs, and it gets to go first. It will be called with these command line arguments (without the stuff in parentheses):

   X         (whose turn)
   --------- (board 0)
   --------- (board 1)
   --------- (board 2)
   --------- (board 3)
   --------- (board 4)
   --------- (board 5)
   --------- (board 6)
   --------- (board 7)
   --------- (board 8)
   --------- (master board)
   xx        (last move)
   

   The first character represents who the bot is. In this case, bot 1 plays as X. The next 9 lines refers to the 9 boards. The 11th line refers to the master board. The "xx" is the last move. Now, bot1 must print two numbers between 0 and 8. Number 1 is the board your bot is moving in, and number 2 is the tile in said board. The controller will keep track of this move. Let's say bot 1 prints 38. Now the board will look like this:

    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   ==========================
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |X ||  | |  ||  | |  
   ==========================
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   

   and bot2 will be called with these arguments:

   O
   ---------
   --------- 
   --------- 
   --------X 
   --------- 
   --------- 
   --------- 
   --------- 
   --------- 
   ---------
   38
   

3. Now bot 2 must move in board 8 (because bot1 placed an x in tile 3). Let's say bot2 prints 84. Now the board looks like this.

    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   ==========================
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |X ||  | |  ||  | |  
   ==========================
    | |  ||  | |  ||  | |  
   ----- || ----- || ----- 
    | |  ||  | |  ||  |O|  
   ----- || ----- || ----- 
    | |  ||  | |  ||  | |  
   

   now bot1 is going to be called with these arguments:

   X
   ---------
   --------- 
   --------- 
   --------X 
   --------- 
   --------- 
   --------- 
   --------- 
   ----0---- 
   ---------
   84
   

4. Now bot1 must move in board 4. However, bot1 is a naughty little bot, and decides to move in board 3. It prints '30'. The board does not change at all. The master bot keeps track of this. Now bot2 will be called with these arguments:

   O
   ---------
   --------- 
   --------- 
   --------X 
   --------- 
   --------- 
   --------- 
   --------- 
   ----0---- 
   ---------
   xx
   

5. Now bot 2 can go anywhere it wants (except for 38 and 84, of course). This continues until somebody wins 3 of the master boards in a row. Then, there is a second matchup where bot2 is X and gets to go first.

6. This repeats until every single bot has played every other bot.

Scoring

The scoring works like this:

The winner of a each match gets 100 + number of open spots points. That way, it is more valuable if your bot wins quickly. Every time your bot makes an invalid move, it loses 1 point. If after 250 rounds, neither bot has won, each bot loses 10 points, and we go on to the next round.

---

Everything will be put into a directory that contains

1. The controller bot. This is a C++ program that I have written. You can look at the controller bot source code here. Please let me know if you see something that isn't right with the controller.

2. A text file named instructions.txt This file will look something like this:

   [Total number of bots that are competing]
   
   [bot1Name] [bot1 command to run]
   [bot2Name] [bot2 command to run]
   ...
   

3. A folder for each bot. This folder will hold your program (Whether it's a script or a binary) and ONE text file named data.txt that your bot can read and write whatever it wants to.

Technical specifications and rule clarifications

• Any bot that attempts to read/write something from anywhere not inside of it's folder will be kicked from the game.

• Your program must be able to run on a macbook running Yosemite. Currently supported languages are python (2.7.9 and 3.4.2), C/C++, objective-C, perl, ruby, bash, PHP, Java, C#, javascript and Haskell. There are a lot more, but these are just the ones I can think of right now. I will add more as time goes on. If you want to compete in a specific language, message me or comment, and I'll add it to the list if possible.

• If a board is won, but there is still space, you still cannot move into one of the open spots.

• Note that the working directory of your submission will be the directory that contains the controller and all the other bots, NOT the directory that contains your bot.

• Please post along with your controller bot code the correct command to compile (if applicable) and to run your bot. Most of this will be done from the OS X terminal, which is fairly similar to a linux terminal.

• Bots must complete in under a second. Unfortunately, I am not quite competent enough to add a timer to the controller bot. However, I will manually time the bots.

---

Results!

Well, I was right. I forgot to make the controller bot check to see if the masterBoard is full. If the masterBoard is full, then EVERY move is invalid, but it continues to call the bots, which is probably why there were so many invalid moves. I have it fixed now. Here are the official results with the most current version of all of the bots.

Bot 1, goodRandBot, has 1 wins and made 0 illegal moves, for a total of 133 points.
Bot 2, naiveBot, has 3 wins and made 48 illegal moves, for a total of 361 points.
Bot 3, depthBot, has 5 wins and made 0 illegal moves, for a total of 664 points.
Bot 4, middleBot, has 1 wins and made 20 illegal moves, for a total of 114 points.

With 4 bots, This program took 477.471 seconds to finish.

Depth Bot is the reigning champion! At least, for right now.

Answer 1

Python 2.7, Depth

An alpha-beta pruning implementation without anything too fancy. It does try to order moves in a less naive way to maximize the alpha-beta eliminations. I will probably try to speed it up, but honestly I don't know how competitive Python can be if it comes down to a question of speed.

class DepthPlayer:
    def __init__(self,depth):
        self.depth = depth

    def score(self,master,subs,last_move):
        total = 0
        for x in range(3):
            for y in range(3):
                c = master[3*y+x]
                if c == 0:
                    total += sum(subs[3*y+x])
                else:
                    total += c*10
                    for (dx,dy) in [(1,-1),(1,0),(0,1),(1,1)]:
                        if x+dx<=2 and 0<=y+dy<=2 and master[3*(y+dy)+(x+dx)] == c:
                            total += c*10
        if last_move is None or master[last_move[1]] != 0 or 0 not in subs[last_move[1]]:
            total += 5
        return total

    def winner(self,board):
        for y in range(3):
            row = board[3*y:3*y+3]
            if 0!=row[0]==row[1]==row[2]:
                return row[0]
        for x in range(3):
            col = board[x:9:3]
            if 0!=col[0]==col[1]==col[2]:
                return col[0]
        if 0!=board[0]==board[4]==board[8]:
            return board[0]
        if 0!=board[2]==board[4]==board[6]:
            return board[2]

        return 0

    def parse(self,input):
        lines = input.split('\n')
        team = lines[0]
        subs_str = lines[1:10]
        master_str = lines[10]
        last_move_str = lines[11]

        master = [1 if c==team else 0 if c=='-' else -1 for c in master_str]
        subs = [[1 if c==team else 0 if c=='-' else -1 for c in sub_str] for sub_str in subs_str]
        if last_move_str == 'xx':
            last_move = None

        else:
            last_move = [int(c) for c in last_move_str]
        return master,subs,last_move

    def alphabeta(self, master,subs,last_move, depth, alpha, beta, player):
        if depth == 0:
            return self.score(master,subs,last_move),None
        w = self.winner(master)
        if w != 0:
            return w*1000,None

        if player:
            v = -10000
            best = None
            for n_master,n_subs,n_last_move in self.all_moves(master,subs,last_move,1):
                nv,_ = self.alphabeta(n_master,n_subs,n_last_move, depth-1, alpha, beta, False)
                if nv>v:
                    v = nv
                    best = n_last_move
                alpha = max(alpha, v)
                if beta <= alpha:
                    break
            return v,best
        else:
            v = 10000
            best = None
            for n_master,n_subs,n_last_move in self.all_moves(master,subs,last_move,-1):
                nv,nb = self.alphabeta(n_master,n_subs,n_last_move, depth-1, alpha, beta, True)
                if nv<v:
                    v = nv
                    best = n_last_move
                beta = min(beta, v)
                if beta <= alpha:
                    break
            return v,best

    def make_move(self,master,subs,move,player):
        n_subs = [sub[:] for sub in subs]
        n_master = master[:]
        n_subs[move[0]][move[1]] = player
        if n_master[move[0]] == 0:
            n_master[move[0]] = self.winner(n_subs[move[0]])
        return n_master,n_subs,move

    def sub_moves(self,board):
        first = []
        second = []
        third = []
        for i in range(9):
            if board[i] != 0:
                continue
            y,x = divmod(i,3)
            c=-2
            if   x==0 and 0!=board[i+1]==board[i+2]>c: c=board[i+1]
            elif x==1 and 0!=board[i-1]==board[i+1]>c: c=board[i-1]
            elif x==2 and 0!=board[i-2]==board[i-1]>c: c=board[i-2]
            if   y==0 and 0!=board[i+3]==board[i+6]>c: c=board[i+3]
            elif y==1 and 0!=board[i-3]==board[i+3]>c: c=board[i-3]
            elif y==2 and 0!=board[i-6]==board[i-3]>c: c=board[i-6]
            if i in [0,4,8] and 0!=board[(i+4)%12]==board[(i+4)%12]>c: c=board[i-6]
            if i in [2,4,6] and 0!=board[6 if i==2 else i-2]==board[2 if i==6 else i+2]>c: c=board[i-6]

            if c==-2:   third.append(i)
            elif c==-1: second.append(i)
            else:       third.append(i)
        return first+second+third

    def all_moves(self,master,subs,last_move,player):
        if last_move is not None and master[last_move[1]]==0 and 0 in subs[last_move[1]]:
            for i in self.sub_moves(subs[last_move[1]]):
                yield self.make_move(master,subs,[last_move[1],i],player)

        else:
            for j in range(9):
                if master[j]==0 and 0 in subs[j]:
                    for i in self.sub_moves(subs[j]):
                        yield self.make_move(master,subs,[j,i],player)

    def move(self,master,subs,last_move):
        return self.alphabeta(master,subs,last_move, self.depth, -10000, 10000, True)[1]

    def run(self,input):
        result = self.move(*self.parse(input))
        if result:
            return str(result[0])+str(result[1])

def print_board(subs,player):
    string = ""
    for row in range(9):
        for sub in subs[row/3*3:row/3*3+3]:
            for c in sub[row%3*3:row%3*3+3]:
                string += "-XO"[c*(1 if player=='X' else -1)]
            string += ' '
        if row%3 == 2:
            string += '\n'
        string += '\n'
    print string

def to_string(master,subs,last_move,player):
    string = player+'\n'
    for sub in subs:
        for c in sub:
            string += "-XO"[c*(1 if player=='O' else -1)]
        string += '\n'
    for c in master:
        string += "-XO"[c*(1 if player=='O' else -1)]
    string += '\n'+str(last_move[0])+str(last_move[1])
    return string


import sys
command = '\n'.join(sys.argv[1:])
print DepthPlayer(8).run(command)

To run it, you can simply do python Depth.py <input>, though I would suggest using pypy as it speeds it up noticeably.

Also I don't know how fast your system is but you can modify the first argument to DepthPlayer at the very end to be higher if it can still run in the specified time (on my system it completed almost all things very quickly with a depth of 7 or 8, but there were a few cases that were near or above a second so I set it to 6 to be safe).

Answer 2

Java, Naive

If possible, it wins. Otherwise, it prevents an opponent from winning.

import java.util.Arrays;

public class Naive {

    public static void main(String[] args) {

        char[][] board = new char[9][9];
        for (int i = 0; i < 9; i++) {
            board[i] = args[i + 1].toCharArray();
        }
        char[] metaBox = args[10].toCharArray();

        char a = args[0].charAt(0),
                b = (char) ('X' + 'O' - a);

        int legalBox = args[11].charAt(1) - '0';
        boolean legalAnywhere = legalBox == 'x' - '0';
        if (!legalAnywhere) {
            if (wins(board[legalBox], 'X') || wins(board[legalBox], 'O')) {
                legalAnywhere = true;
            }
        }
        a:
        if (!legalAnywhere) {
            for (int i = 0; i < 9; i++) {
                if (board[legalBox][i] == '-') {
                    break a;
                }
            }
            legalAnywhere = true;
        }

        if (legalAnywhere) {
            chooseMove(board, metaBox, a, b);
        } else {
            chooseMove(board, metaBox, a, b, legalBox);
        }
    }

    static boolean canWinWith(char[] box, char c) {
        for (int i = 0; i < 9; i++) {
            if (wins(box, i, c)) {
                return true;
            }
        }
        return false;
    }

    static boolean wins(char[] box, int move, char c) {
        char[] copy = Arrays.copyOf(box, 9);
        copy[move] = c;
        return wins(copy, c);
    }

    static boolean wins(char[] box, char c) {
        return (box[0] == c && box[1] == c && box[2] == c)
               || (box[3] == c && box[4] == c && box[5] == c)
               || (box[6] == c && box[7] == c && box[8] == c)
               || (box[0] == c && box[3] == c && box[6] == c)
               || (box[1] == c && box[4] == c && box[7] == c)
               || (box[2] == c && box[5] == c && box[8] == c)
               || (box[0] == c && box[4] == c && box[8] == c)
               || (box[2] == c && box[4] == c && box[6] == c);
    }

    static void endWith(int box, int i) {
        System.out.println("" + box + i);
        System.exit(0);
    }

    private static void chooseMove(char[][] board, char[] metaBox, char a, char b, int legalBox) {
        for (int i = 0; i < 9; i++) {
            if (wins(board[legalBox], i, a) && board[legalBox][i] == '-') {
                endWith(legalBox, i);
            }
        }
        for (int i = 0; i < 9; i++) {
            if (wins(board[legalBox], i, b) && board[legalBox][i] == '-') {
                endWith(legalBox, i);
            }
        }
        for (int i = 0; i < 9; i++) {
            if (board[legalBox][i] == '-') {
                if (!canWinWith(board[i], b)) {
                    endWith(legalBox, i);
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            if (board[legalBox][i] == '-') {
                endWith(legalBox, i);
            }
        }
        throw new RuntimeException("No move chosen!");
    }

    private static void chooseMove(char[][] board, char[] metaBox, char a, char b) {
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (wins(board[box], i, a) && board[box][i] == '-') {
                    endWith(box, i);
                }
            }
        }
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (wins(board[box], i, b) && board[box][i] == '-') {
                    endWith(box, i);
                }
            }
        }
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (board[box][i] == '-') {
                    if (!canWinWith(board[i], b)) {
                        endWith(box, i);
                    }
                }
            }
        }
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (board[box][i] == '-') {
                    endWith(box, i);
                }
            }
        }
        throw new RuntimeException("No move chosen!");
    }
}

Answer 3

Python 2, MiddleBot

MiddleBot likes the middle. Before the central game (4) is won, it will try to grab the centre square of as many games as possible, forcing the opponent back to the middle game again and again.
Once this is done, it tries to win any games it can, or just fills the first available space if not (need to work on its late game, I think)

from random import randint
import sys
command_in = '\n'.join(sys.argv[1:])
class MiddleBot:

    def scan_in(self,the_game):

        lines = the_game.split('\n')
        self.us = lines[0]
        if self.us == 'X':
            self.them = 'O'
        else:
            self.them = 'X'
        self.games = lines[1:10]
        self.metagame = lines[10]
        self.last_move = lines[11]

        try:
            self.sub_board = int(self.last_move[1])
        except ValueError:
            self.sub_board = self.last_move[1]

    def empty(self,game,target):
        if self.games[int(game)][int(target)] == '-':
            self.emptycell = 1
        else: self.emptycell = 0

    def empty_fill(self,game):
        #checks for next empty space, fills it
        for k in xrange(0,8):
            self.empty(game,k)
            if self.emptycell == 1:
                self.first_empty_space = k
                break
            if self.emptycell == 0:
                game = randint(0,8)
                self.first_empty_space = 4


    def aim_for_target(self,game,target):
        if self.games[int(game)][int(target)] == '-':
            self.move = `game` + `target`
        else:
            self.empty_fill(game)
            self.move = `game` + `self.first_empty_space`


    #define all win conditions        
    win = [0]*8            
    win[0] = [0,1,2]
    win[1] = [3,4,5]
    win[2] = [6,7,8]
    win[3] = [0,3,6]
    win[4] = [1,4,7]
    win[5] = [2,5,8]
    win[6] = [0,4,8]
    win[7] = [2,4,6]

    #check if current board state is one move away from 'us' winning
    def aim_for_win(self,game):
            for k in xrange(0,len(self.win)):
                if self.games[self.sub_board][self.win[k][0]] == self.games[self.sub_board][self.win[k][1]] == self.us:
                    self.empty(self.sub_board,self.win[k][2])
                    if self.emptycell == 1:
                        self.move = `self.sub_board`+`self.win[k][2]`
                    else:
                        self.empty_fill(self.sub_board)
                        self.move = `self.sub_board`,`self.first_empty_space`
                elif self.games[self.sub_board][self.win[k][0]] == self.games[self.sub_board][self.win[k][2]] == self.us:
                    self.empty(self.sub_board,self.win[k][1])
                    if self.emptycell == 1:
                        self.move = `self.sub_board`+`self.win[k][1]`
                    else:
                        self.empty_fill(self.sub_board)
                        self.move = `self.sub_board`+`self.first_empty_space`
                elif self.games[self.sub_board][self.win[k][1]] == self.games[self.sub_board][self.win[k][2]] == self.us:
                    self.empty(self.sub_board,self.win[k][0])
                    if self.emptycell == 1:
                        self.move = `self.sub_board`+`self.win[k][0]`
                    else:
                        self.empty_fill(self.sub_board)
                        self.move = `self.sub_board`+`self.first_empty_space`
                else:
                    self.empty_fill(self.sub_board)
                    self.move = `self.sub_board`+`self.first_empty_space`


    def play(self):
        #If the middle board is not won, aim for the middle square of each board
        if self.metagame[4] == '-':
            if self.sub_board == 4 or self.sub_board == 'x':
                self.aim_for_target(4,4)
            else:
                self.aim_for_target(self.sub_board,4)
        else:
            #once the middle board is won, pretty much plays randomly, aiming to win if it can, otherwise just filling the first empty space in each subgame
            played = 0
            if self.sub_board == 'x':
                self.sub_board = randint(0,8)
            while played == 0:
                if self.metagame[int(self.sub_board)] == '-':
                    self.aim_for_win(self.sub_board)
                    played = 1
                else:
                    self.sub_board = randint(0,8)
        return self.move

    def run(self,game_board):
        self.scan_in(game_board)
        self.play()
        return self.move

print MiddleBot().run(command_in)      

To run it, python MiddleBot.py <input> It seems to happily run under a second for me, so hopefully it will for you as well

Answer 4

Might as well throw my own bot into the mix.

python 2, goodRandomBot

import sys
from random import choice

args = sys.argv
if len(args) < 13:
    print ("I can't work with this!\n")
    sys.exit()

whoAmI = args[1];
masterBoard = list(args[11])
board = []
for i in range(2, 11):
    board.append(list(args[i]))

oppMove = args[12]

def findAllValidMoves(board, masterBoard):
    validMoves = []
    for row in range(9):
        if masterBoard[row] != '-':
            continue
        for col in range(len(board[row])):
            if board[row][col] == '-':
                validMoves.append(str(row) + str(col))
    return validMoves

validMoves = []
if oppMove == "xx" or masterBoard[int(oppMove[1])] != "-":
    validMoves = findAllValidMoves(board, masterBoard)    

else:
    row = int(oppMove[1])
    for col in range(len(board[row])):
        if board[row][col] == '-' and masterBoard[row] == "-":
            validMoves.append(str(row) + str(col))

if (validMoves == []):
    validMoves = findAllValidMoves(board, masterBoard)

print choice(validMoves)

This bot doesn't care where it moves, as long as it is a valid move. Picks at random from all valid moves, and makes an average of 0 invalid moves.