05 Oct 2014, 17:25

Tic-Tac-Toe in ... MySQL

If you ever attended a boring lecture, you probably know this game by heart. Frequently scribbled on textbook margins and school desks, it’s insanely popular and fun to play. Talking to a friend about MySQL made me wonder if such a respectable, high performance database can be misused and tricked into being a gaming platfom. While it isn’t likely going to run Quake, maybe a simple game of Tic-Tac-Toe would be just right.

Why would anyone do this? Well, making floppy drives play The Imperial March isn’t very useful either, but it’s darn entertaining. MySQL is a powerful tool with strong scripting capabilities and Turing complete as well, so implementing this game in a single player mode is possible.

Implementation

First, we need a board. To keep things simple, we’ll keep it as a 9 letter string - matrix element with position (1,1) will be the first element, then element (1,2) and so on .

SET @ploca = '_________';

After defining something to store and describe the board in, we declare AI is using ‘o’ and the player will be playing with ‘x’. Underscores are used to represent unclaimed fields. Since MySQL isn’t Perl or Python, we’ll have to improvise a little and create a function to check what’s placed on the board at a specific (row,column) position.

CREATE FUNCTION get(instring VARCHAR(255), y INT, x INT) RETURNS CHAR(1) RETURN SUBSTRING(instring, 3*(y-1)+x, 1);

Now we need to think of a way to display the board to the player. There is no simple print function and we are trying to display a string as a table, so this is what I could think of.

DELIMITER $$
CREATE PROCEDURE display_board(IN l VARCHAR(16))
BEGIN
      DROP TEMPORARY TABLE IF EXISTS `tablica`;
      CREATE TEMPORARY TABLE `tablica` (ta varchar(1), bli varchar(1), ca varchar(1));
      INSERT INTO tablica VALUES (get(l, 1,1), get(l, 1,2), get(l, 1,3));
      INSERT INTO tablica VALUES (get(l, 2,1), get(l, 2,2), get(l, 2,3));
      INSERT INTO tablica VALUES (get(l, 3,1), get(l, 3,2), get(l, 3,3));          
      SELECT * from tablica;
END
$$

We declare a temporary table, extract characters from our board-string and select it. This will print it (somewhat) nicely to the player.

+------+------+------+
| ta   | bli  | ca   |
+------+------+------+
| o    | _    | _    |
| _    | x    | _    |
| _    | _    | _    |
+------+------+------+
3 rows in set (0.02 sec)

AI - making a respectable oponent

This is a good time to talk about the AI. Taking the classic approach isn’t something you do when coding for fun, so I decided to do something different. When doing something weird in a database engine, why not use it in your advantage? Basic combinatorics tells us each field can be either ‘o’, ‘x’ or empty, and there are 9 fields so that’s 39 = 19,683 possible board positions. Also, many positions are invalid - you can’t have all x’s because players take turns, you can’t play after you’ve lost etc. so the real number of valid board is much smaller (it’s 5477).

Game theory teaches us Tic-Tac-Toe can never actually be won if you pick optimal moves, so we’ll run it once to generate a tree of best computer moves given a certain position, store it permanently in the database, and use it to defeat the puny human.

Tic tac toe

Each optimal move for a certain position will be stored as a table row along with its predecessor’s id, so we can look it up and know where to move.

+-------+-----------+------------+------+------+--------+
| id    | matrix    | moves_next | kraj | win  | parent |
+-------+-----------+------------+------+------+--------+
| 32041 | oxooxxo_x | x          |    1 | o    |  32040 |
+-------+-----------+------------+------+------+--------+

An example of a move stored in a database - this is a finished game which a computer (‘o’ player) won. Let’s implement a function for making a move.

DELIMITER $$
CREATE PROCEDURE place_x(IN y INT, IN x INT)
BEGIN
      IF get(@ploca, y, x) = '_' THEN   
    SELECT concat(substring(@ploca, 1, 3*(y-1)+x-1), 'x', substring(@ploca, 3*(y-1)+x+1)) INTO @ploca;
    CALL display_board(@ploca);

        SELECT id,kraj,win FROM tictactoe WHERE matrix=@ploca AND moves_next='o' LIMIT 1 INTO @parent_id, @kraj, @win;
        SELECT matrix,kraj,win FROM tictactoe WHERE parent=@parent_id LIMIT 1 INTO @ploca, @kraj, @win;
    
    CALL display_board(@ploca);
    
    IF @kraj = 1 THEN   
      IF @win = 'o' THEN SELECT 'Izgubili ste!' AS ' '; ELSE  SELECT 'Nerijeseno. Pokusajte ponovno!' AS ' '; END IF;
      SET @ploca = '_________';
      CALL display_board(@ploca);
    END IF;
      END IF;
END
$$
DELIMITER ;

Constructing the optimal move tree

If you ever saw Wargames, you probably remember the scene where the kid saves the world by making the computer play Tic-Tac-Toe with itself. The same thing is done here (minus saving the world part). Computer plays both sides, but when impersonating a human it checks all moves, not just the best one, because a human might make a mistake. To determine the best move, a recursive minimax algorithm is used, checking long-term consequence of a move (‘move’ function) and choosing the one with a best outcome.

This python algorithm is ran only once; it recursively traverses the moves tree and inserts nodes as database rows. Our database could also be imported from external file, effectively eliminating any external dependencies, even if they are only a one-time thing. A single database row also contains state flags to determine if the game is over or not.


#!/usr/bin/python
import itertools, hashlib, MySQLdb

ploca = list('_' * 9) 
db=MySQLdb.connect('localhost', 'game', 'game', 'game')
c=db.cursor()

def move(ploca, player):
    if len(set(ploca)) == 1: return 0, 4
    nextplayer = 'x' if player is 'o' else 'o' 
    if pobjednik(ploca):
        return (-1, -1) if player is 'x' else (1, -1)

    reslist = []
    lista = []

    if provjeri_kraj(ploca): return 0, -1
    for i in range(9):
        if ploca[i] == '_': lista.append(i)

    for i in lista:
        ploca[i]=player
        ret,mov=move(ploca, nextplayer)
        reslist.append(ret)
        ploca[i]='_'

    if player is 'x': return max(reslist),lista[reslist.index(max(reslist))]
    else: return min(reslist),lista[reslist.index(min(reslist))]

def moguci_potezi(ploca): return [i for i in zip(range(9), ploca) if i[1] is '_']
def provjeri_kraj(ploca): return True if not len(moguci_potezi(ploca)) else False
def igraceva_polja(igrac, ploca): return [i for i in zip(range(9), ploca) if i[1] == igrac]
def nerijeseno(ploca):  return True if provjeri_kraj(ploca) and not pobjednik(ploca) else False

def pobjednik(ploca):       
    dobitne_mogucnosti = ([0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [2,4,6], [0,4,8])
    for strana in ('x', 'o'):
        if [len([ploca[i] for i in j if ploca[i] is strana]) for j in dobitne_mogucnosti].count(3): return strana
    return False

def povuci_potez(ploca, strana, parent):
    win = 'NULL'
    tbl = [''.join(ploca), strana]
    
    kraj = 1 if nerijeseno(ploca) or pobjednik(ploca) else 0
    if kraj: win = pobjednik(ploca) if pobjednik(ploca) else 'Tie'

    tbl.extend([win, str(kraj)])
    c.execute("INSERT INTO tictactoe (matrix, moves_next, win, kraj) VALUES ('{}');".format("', '".join(tbl)))
    lastrowid = c.lastrowid
    db.commit()

    if parent is not 'NULL': c.execute("UPDATE tictactoe SET parent='{0}' WHERE id='{1}'".format(parent, lastrowid))
    if pobjednik(ploca) or nerijeseno(ploca): return

    slobodna_polja = moguci_potezi(ploca)
    if strana == 'x': 
        for i in slobodna_polja:
            ploca_recursive=ploca[:]
            ploca_recursive[i[0]] = 'x'
            povuci_potez(ploca_recursive, 'o', lastrowid)
    else:
        ploca[move(ploca, 'o')[1]] = 'o'
        povuci_potez(ploca, 'x', lastrowid)

povuci_potez(ploca, 'x', 'NULL')

Making it fancy

That’s all nice, it works, but one more thing… can we make it 3D, just for fun? Mysql can execute shell commands, but apparently you can’t pipe anything through shell scripts. Let’s use a trick - very often it produces long, long tables, and to facilitate looking at the data you can set a pager - something it will pipe your output through, like less or your favorite editor. Why not using that and piping it through … figlet! One apt-get install figlet later, finding a cool looking 3d font and a little sed to strip everything not important and we’re left with this.

mysql> pager sed -e 's/| ta   | bli  | ca   |//g' -e 's/  \+/ /g' -e 's/[+\-]//g' -e '/^$/d' | figlet -f 'larry3d.flf'
mysql> call place_x(2,3);
 __                  __                  __                   __       
/\ \                /\ \                /\ \                 /\ \      
\ \ \        ___    \ \ \       __  _   \ \ \                \ \ \     
 \ \ \      / __`\   \ \ \     /\ \/'\   \ \ \                \ \ \    
  \ \ \    /\ \L\ \   \ \ \    \/>  </    \ \ \                \ \ \   
   \ \ \   \ \____/    \ \ \    /\_/\_\    \ \ \                \ \ \  
    \ \ \   \/___/      \ \ \   \//\/_/     \ \ \      _______   \ \ \ 
     \ \_\               \ \_\               \ \_\    /\______\   \ \_\
      \/_/                \/_/                \/_/    \/______/    \/_/
 __                   __                  __                  __       
/\ \                 /\ \                /\ \                /\ \      
\ \ \                \ \ \        ___    \ \ \       __  _   \ \ \     
 \ \ \                \ \ \      / __`\   \ \ \     /\ \/'\   \ \ \    
  \ \ \                \ \ \    /\ \L\ \   \ \ \    \/>  </    \ \ \   
   \ \ \                \ \ \   \ \____/    \ \ \    /\_/\_\    \ \ \  
    \ \ \      _______   \ \ \   \/___/      \ \ \   \//\/_/     \ \ \ 
     \ \_\    /\______\   \ \_\               \ \_\               \ \_\
      \/_/    \/______/    \/_/                \/_/                \/_/
 __                  __                  __                  __       
/\ \                /\ \                /\ \                /\ \      
\ \ \       __  _   \ \ \        ___    \ \ \       __  _   \ \ \     
 \ \ \     /\ \/'\   \ \ \      / __`\   \ \ \     /\ \/'\   \ \ \    
  \ \ \    \/>  </    \ \ \    /\ \L\ \   \ \ \    \/>  </    \ \ \   
   \ \ \    /\_/\_\    \ \ \   \ \____/    \ \ \    /\_/\_\    \ \ \  
    \ \ \   \//\/_/     \ \ \   \/___/      \ \ \   \//\/_/     \ \ \ 
     \ \_\               \ \_\               \ \_\               \ \_\
      \/_/                \/_/                \/_/                \/_/

Check out the video (HTML5 - webm):

Awesome!