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

This is a 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.

• As an aside, have you ever looked at Fire and Ice (a pbem version at gamerz.net) - there are some tic-tac-toe elements to it... though this also reminded me of scribe.
– user12166
May 12, 2015 at 3:34
• 9 likes and 40 views. I'm impressed! May 12, 2015 at 6:13
• You might want to put a limit on the response time of bots, or bots may take 3 minutes per move while searching all possible future moves. May 12, 2015 at 8:31
• I've added some rule clarifications to the bit about next move. I have a concern about the data format and one of the rules. Rule 5 from the first section: "If one of the boards becomes filled, it counts as nobodies tile." Is this filled without a winner? i.e. if someone wins the tile previously, and it becomes filled is it nobodies tile? Furthermore, if the bots are stateless (they appear to be) with the state passed in, how does the winner of a board that is XXX000--- get transmitted? or is that a 'nobody gets it despite O having won it first'?
– user12166
May 12, 2015 at 13:47
• @MichaelT the winner of the board is passed in on the 11th line. I'll edit this part to make it a little bit more clear, however your edit is incorrect. "If a board is won, but there is still space, you still cannot move into one of the open spots." May 12, 2015 at 15:08

# 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

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

• python's sys.argv doesn't return a newline separated string. It gives a list of strings in this format: ['Depth.py', 'X', '---------', '---------', ...] I fixed it by editing the last two lines to this command = '\n'.join(sys.argv[1:]) print DepthPlayer(6).run(command) I hope you don't mind. May 13, 2015 at 1:41
• @DJMcMayhem Oh thanks I didn't test that last line.
– KSab
May 13, 2015 at 2:39

# 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!");
}
}

• You'll have to forgive me for being a java noob, but how do I run this from the parent directory? I have Naive.class in a directory named naiveBot inside the main directory. May 12, 2015 at 17:52
• @DJMcMayhem I don't have access to a Mac, but on Windows, you can just run the java Naive <args> command, assuming the environment variables include the pointer to C:\Program Files\Java\jdk1.8.0\bin. I hope this helps. May 12, 2015 at 19:48
• Alright, I'll figure it out. May 12, 2015 at 19:50
• @DJMcMayhem If you didn't figure it out already, it's java -classpath naiveBot Naive ;) May 13, 2015 at 7:44
• @Ypnypn If legalAnywhere is true, your submission fails because you try to use boards that are already won by a player. May 13, 2015 at 8:44

# 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

• Everything runs fine, but FYI, it crashes when the last move is 'xx' which happens at the beginning and every time a bot makes an invalid move. May 14, 2015 at 4:44
• Oops! Should be fixed now. Forgot to test the 'xx' case in that iteration, sorry! May 14, 2015 at 8:25
• Also made an edit - it would crash if a board had been filled without a winner and it was asked to play there May 14, 2015 at 9:06

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.