I only managed one task in the 2016 VolgaCTF, but it was a fun one. Coding a tic tac toe bot.
Challenge:
Tic-Tac-Toe An important step towards the strong AI is the ability of an artificial agent to solve a well-defined problem. A project by the name 'tic-tac-toe' was one of such test problems. It's still up... nc tic-tac-toe.2016.volgactf.ru 45679
Solution:
Connecting to the provided address using netcat presented a prompt for a username and then a quick intro to the game.
Welcome to Noughts & Crosses World Championship! Please, name yourself. Codehead The match is played over 500 rounds, the winner of each round gets 1.0 points, the looser gets 0.0 points, and in case of a draw each player gets 0.5 points. To make your move choose the empty cell and send it's index followed by '\n', e.g. '4\n'.The indices map: 0 | 1 | 2 ---+---+--- 3 | 4 | 5 ---+---+--- 6 | 7 | 8 Round number 1. Server vs. T3-Bot 9000. Current score: 0.0 - 0.0 | | ---+---+--- | X | ---+---+--- | |
The game didn’t have an aggressive timeout like most of these challenges do, so it was possible to play manually against the computer for a few turns and get a feel for the level of opposition.
After a few games it was apparent that the server logic favoured the center square approach. Playing a corner strategy won most of the games I played against it.
Obviously we’re not going to play 500 games against the server, we need some Python!
Grabbing the game board using my favourite TelnetLib library proved interesting. The text blocks received varied in size between the intro text, in-game updates and new games with score updates. My usual approach is to use timeouts rather than look for specific text to aquire text blocks, this was tricky as the server was getting hammered by other people trying to solve the puzzle too. I’m sure the intro text said 2000 games early in the competition. I guess this was dropped down to 500 in order to lighten the load and two extra servers were added.
Eventually I worked out that splitting the input into lines and reversing the order gave me a consistent way to grab the board data into a 9 element array:
def readBoard():
tIn = tn.read_until("WordsWeNeverSee",0.8)
tLines = tIn.split('\n')
sys.stdout.write(tIn)
tLInes = tLines.reverse()
row = tLines[6].replace(' ', '').split('|')
board[0] = row[0]
board[1] = row[1]
board[2] = row[2]
row = tLines[4].replace(' ', '').split('|')
board[3] = row[0]
board[4] = row[1]
board[5] = row[2]
row = tLines[2].replace(' ', '').split('|')
board[6] = row[0]
board[7] = row[1]
board[8] = row[2]
Now it was just a case of evalutaing the board state and choosing the best move.
The logic went through a few iterations, at first it generally selected a random valid square after snagging some corners. The first time it was able to complete 500 games, it lost with a score of 328 - 172, not that bad for random selection.
The final code checks for the following situations in the following priority:
- Strong start
- Check for winning moves (two ‘O’ entries and a blank on any winline)
- Block opposition winning chance (two ‘X’ entries and blank on any winline)
- Grab corners
- Choose a random valid square
A couple of worker functions take care of finding char counts or the first available square in a tuple argument.
winLines = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]]
def countCharInCells(char, tup):
count = 0
for n in tup:
if board[n] == char:
count += 1
return count
def findEmpty(tup):
for n in tup:
if board[n] == '':
return n
return -1
def selectMove():
xCount = board.count('X')
# Strong first turn move
if xCount == 0:
tn.write('8\n')
return
# Best response to center start
if board.count('X') == 1:
if board[4] == 'X':
tn.write('8\n')
return
# See if we can win
for wl in winLines:
if countCharInCells('O', wl) == 2:
choice = findEmpty(wl)
if choice != -1:
tn.write(str(choice) + '\n')
return
# Try to block opposition winning moves
for wl in winLines:
if countCharInCells('X', wl) == 2:
choice = findEmpty(wl)
if choice != -1:
tn.write(str(choice) + '\n')
return
# Try to snag a corner
choice = findEmpty([0,2,6,8])
if choice != -1:
tn.write(str(choice) + '\n')
return
# Pick a random valid square when stumped
while True:
choice = randint(0,8)
if board[choice] == '':
tn.write(str(choice) + '\n')
return
Running this code against the server had the following results:
Welcome to Noughts & Crosses World Championship! Please, name yourself. The match is played over 500 rounds, the winner of each round gets 1.0 points, the looser gets 0.0 points, and in case of a draw each player gets 0.5 points. To make your move choose the empty cell and send it's index followed by '\n', e.g. '4\n'.The indices map: 0 | 1 | 2 ---+---+--- 3 | 4 | 5 ---+---+--- 6 | 7 | 8 Round number 1. Server vs. T3-Bot 9000. Current score: 0.0 - 0.0 | | ---+---+--- | X | ---+---+--- | | X | | ---+---+--- | X | ---+---+--- | | O X | | O ---+---+--- | X | ---+---+--- X | | O Round number 2. Server vs. T3-Bot 9000. Current score: 0.0 - 1.0 | | ---+---+--- | | ---+---+--- | |
Off to a good start, we won the first game.
Some time later …
Round number 500.
Server vs. T3-Bot 9000. Current score: 75.0 - 424.0
| |
---+---+---
| |
---+---+---
| |
| |
---+---+---
| |
---+---+---
| O | X
X | O |
---+---+---
| |
---+---+---
| O | X
Server vs. T3-Bot 9000. Final score: 75.0 - 425.0
Congratulations! Your flag is: VolgaCTF{tic_t@c_t0e_is_the_e@rly_step_t0wards_AI}
A pretty good result. Playing 500 games took a long time, but I didn’t see my bot lose a single match while I was watching, all the server points seemed to come from drawn games.
I’d assumed that we always played as ‘O’ and the server was ‘X’, but I realised while watching the games scroll past that this changed depending on who tool the first move. Fortunately, my code was generic enough that it didn’t really matter.
Here’s the full code for reference:
#!/usr/bin/env python
from telnetlib import Telnet
import sys
from pprint import pprint
from random import randint
HOST = '95.213.237.93'
PORT = 45679
tn = Telnet(HOST, PORT)
board=['','','','','','','','','']
winLines = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]]
def main():
startup()
while True:
readBoard()
selectMove()
tn.close()
def startup():
print "Start!"
print tn.read_until("WordsWeNeverSee",2.0) # Read welcome message
tn.write("T3-Bot 9000\n") # Send a name
print tn.read_until("7 | 8", 2.0) # Read past the intro text
def readBoard():
tIn = tn.read_until("WordsWeNeverSee",0.5)
tLines = tIn.split('\n')
sys.stdout.write(tIn)
tLInes = tLines.reverse()
row = tLines[6].replace(' ', '').split('|')
board[0] = row[0]
board[1] = row[1]
board[2] = row[2]
row = tLines[4].replace(' ', '').split('|')
board[3] = row[0]
board[4] = row[1]
board[5] = row[2]
row = tLines[2].replace(' ', '').split('|')
board[6] = row[0]
board[7] = row[1]
board[8] = row[2]
def countCharInCells(char, tup):
count = 0
for n in tup:
if board[n] == char:
count += 1
return count
def findEmpty(tup):
for n in tup:
if board[n] == '':
return n
return -1
def selectMove():
xCount = board.count('X')
# Strong first turn move
if xCount == 0:
tn.write('8\n')
return
# Best response to center start
if board.count('X') == 1:
if board[4] == 'X':
tn.write('8\n')
return
# See if we can win
for wl in winLines:
if countCharInCells('O', wl) == 2:
choice = findEmpty(wl)
if choice != -1:
tn.write(str(choice) + '\n')
return
# Try to block opposition winning moves
for wl in winLines:
if countCharInCells('X', wl) == 2:
choice = findEmpty(wl)
if choice != -1:
tn.write(str(choice) + '\n')
return
# Try to snag a corner
choice = findEmpty([0,2,6,8])
if choice != -1:
tn.write(str(choice) + '\n')
return
# Pick a random valid square when stumped
while True:
choice = randint(0,8)
if board[choice] == '':
tn.write(str(choice) + '\n')
return
if __name__ == "__main__":
main()