Quarto

Quarto is a game played between two players. Players take turn placing pieces on a 4×4 grid. Pieces have four “dimensions”: light/dark, tall/short, whole/hollow, and round/square. When a player places a piece that creates a row, column, or diagonal of pieces that all share a common dimension, that player wins. Read more at the Wikipedia article on Quarto.

My friend, Gabe, wanted to learn some Ruby on Rails programming and developed a game server for Quarto sessions. His website hosts a Quarto human interface. Through this interface you can play against other people or computers.

Part of our competitive spirit was to create computer players that could play each other. The subject of my AI player is the focus of the rest of this article.

The computer player I implemented relies on lighttpd, mysql, django, celery, RabbitMQ and Boost.Python. The system is implemented in mainly C++ and python with some bash scripts for management. The basic workflow is:

1. Gabe's server sends an http request to my server asking a specific player to join a session.
2. My server registers the request and queues it with Celery (backed by RabbitMQ).
3. Celery dispatches the request and a response is sent to Gabe's server.
4. Gabe's server sends an http request to my server asking a specific player to make a move.
5. Again, my server registers the request, queues it with Celery, and replies when Celery dispatches the task.
   • Move requests rely on a C++ module that is called via Boost.Python.

The two key ways that I experimented with this workflow were (1) using Celery + RabbitMQ and (2) using Boost.Python. Both these systems worked quite well.

With (1), our servers were able to communicate asynchronously. Since the task of making a move can take a long time, we didn't want our servers to wait on the other end of an http request. I thought Celery's delayed task processing worked quite well. I also think it's a clever way (in say, a website) to delay more compute-intensive (either for a machine or human) tasks to later. The responsiveness of my system seems high though it does a lot of work on each move.

With (2), I had the opportunity to write a high-performance solution in C++ that still was callable from my django application. As many people have already suggested, this is a great solution when you have a compute-intensive task for which you want the highest performance.

As I stated before, my system is a linux, lighttpd, mysql, django stack. This combination is easy to develop with and cheap (thanks Rackspace!). I couldn't recommend it more. Unlike other web projects, I also got Celery and RabbitMQ installed on the machine. For the AI player, I needed g++ for compilation and Boost.Python to interface my C++ module with the django app. Though it may be obvious, here's what each system is doing:

• Linux - The operating system for the whole stack. This would probably work on Windows (and I'm certainly more familiar with the MSVC++ compiler) but is too expensive on Rackspace.
• Lighttpd - Handles http requests and dispatches (via Fast-CGI) to django.
• Django - Web project/application framework. This handles the data in the http requests and provides an administrator interface for AI players.
• MySQL - Stores information about players (ids, passwords, etc.)
• Celery - Distributed task-based messaging. Interfaces between Django and RabbitMQ to queue and dispatch work items from a queue.
• RabbitMQ - A specialized database for queues. Stores information about join/move requests.
• Boost.Python - Interfaces between python and C++ modules.
• g++/gcc - Compiler for C++ modules.

Thanks to Django, there's a friendly Quarto Admin interface that allows me to create players, edit passwords, etc. This also controls what variant of AI is used for each registered player. Different AI player variants include: random players, 1-lookahead, time-constrained lookahead, and max lookahead. I created separate Django apps for the random and lookahead players.

The AI player is C++ but is written in a C-style so that I could have a clearer understanding of what the machine code would look like (this is essentially C with namespaces). The kernel of the AI is the FindBestMoveRec function which implements a recursive min-max algorithm for solving Quarto puzzles. No heuristic value of moves is computed. Instead, only win, tie, lose, unknown, and out_of_time (time is deterministically based on the number of entries to the function) states are tracked. Calling FindBestMoveRec is FindBestMove which does an iteratively increasing depth-limit search for the best solution.

The game state is contained in 88 bits: 64 bits are for the board (with 4 bits per square, each bit represents a dimension of the piece at that square), 16 bits indicate which board positions are occupied, and 8 bits store the next piece to be played. With such a minimal representation of the game state, I can easily pass it around in arguments and make copies of it on the stack.

class Player(models.Model):
    session_server_id = models.IntegerField()
    name = models.CharField(max_length=20)
    password = models.CharField(max_length=20)

def computer_move(request):
    if request.method == 'POST':
        xml = request.raw_post_data
        MoveTask.delay(xml)
        return HttpResponse(status=200)
    else:
        return HttpResponseNotAllowed(['POST',])

class MoveTask(Task):
    def run(self, xml):
        if game.is_won(xml):
            return

        board = map(lambda x: int(x), game.from_xml_to_string(xml).split(" "))
        selected = board.pop()
        session_id, player_id, password = get_ids(xml)
        count = board.count(16)

        if count == 16 and selected == 16:
            random_player.tasks.MoveTask.delay(xml)
        elif count >= 14:
            random_player.tasks.MoveTask.delay(xml)
        elif count == 1:
            random_player.tasks.MoveTask.delay(xml)
        elif count == 0:
            raise Exception("can't move")
        else:
            move = quarto_ai.FindBestMove(game.from_xml_to_string(xml))
            square, piece = move.split(" ")
            square = int(square)
            piece = int(piece)

            if piece == 16:
                all_squares = list(board)
                all_squares.append(selected)
                pieces = filter(lambda x: x != 16, all_squares)
                piece = random.choice([item for item in range(16) if item not in pieces])

            row = square / 4
            col = square % 4
            piece = game.map_to_external[piece]

            result = session.make_move(session_id, player_id, password, row, col, piece)

            if not result:
                raise Exception("session.make_move failed")

std::string
FindBestMove(std::string game_string);

BOOST_PYTHON_MODULE(quarto_ai)
{
    using namespace boost::python;
    def("FindBestMove", FindBestMove);
}

    uint8_t
    FindBestMoveRec(uint64_t squares, uint16_t occupied, uint16_t given_piece,
		    uint16_t &best_square, uint16_t &best_piece,
		    uint8_t depth, uint8_t max_depth)
    {
      assert(depth <= max_depth);

      if (AI::iter > MAX_ITER)
	{
	  return OUTCOME_OUT_OF_TIME;
	}

      uint8_t outcome = OUTCOME_INVALID;
      best_square = SQUARE_MAX;
      best_piece = PIECE_MAX;

      uint16_t unoccupied = static_cast<uint16_t>(~occupied);
      uint16_t availables = Board::AvailablePieces(squares, occupied, given_piece);

      for (uint16_t square = SQUARE_MIN; square < SQUARE_MAX; square++)
	{
	  if (unoccupied & (static_cast<uint16_t>(1) << square))
	    {
	      uint64_t squares_sim = squares;
	      uint16_t occupied_sim = occupied;

	      AI::iter++;

	      Board::MoveToOpenSquare(squares_sim, occupied_sim, square, given_piece);

	      if (Board::Goal(squares_sim, occupied_sim, square))
		{
		  // This move is a win.

		  best_square = square;
		  best_piece = PIECE_MAX;
		  return OUTCOME_WIN;
		}
	      else
		{
		  if (availables == 0)
		    {
		      // There are no available pieces.

		      assert(occupied_sim == 0xFFFF);

		      if (outcome < OUTCOME_TIE)
			{
			  outcome = OUTCOME_TIE;
			  best_square = square;
			  best_piece = PIECE_MAX;
			}
		    }
		  else if (depth == max_depth)
		    {
		      // The counter-move outcome is unknown.

		      if (outcome < OUTCOME_UNKNOWN)
			{
			  outcome = OUTCOME_UNKNOWN;
			  best_square = square;
			  best_piece = PIECE_MAX;
			}
		    }
		  else
		    {
		      for (uint16_t piece = PIECE_MIN; piece < PIECE_MAX; piece++)
			{
			  if (availables & (static_cast<uint16_t>(1) << piece))
			    {
			      uint8_t counter_outcome;
			      uint16_t counter_square = SQUARE_MAX;
			      uint16_t counter_piece = PIECE_MAX;

			      AI::iter++;

			      counter_outcome = FindBestMoveRec(squares_sim, occupied_sim, piece,
								counter_square, counter_piece,
								static_cast<uint16_t>(depth + 1), max_depth);

			      // Translate the counter_outcome into what it means for us.

			      switch (counter_outcome)
				{
				case OUTCOME_WIN:
				  counter_outcome = OUTCOME_LOSE;
				  break;
				case OUTCOME_TIE:
				case OUTCOME_UNKNOWN:
				  break;
				case OUTCOME_LOSE:
				  best_square = square;
				  best_piece = piece;
				  return OUTCOME_WIN;
				case OUTCOME_OUT_OF_TIME:
				  return OUTCOME_OUT_OF_TIME;
				default:
				  assert(counter_outcome > 0 && counter_outcome < OUTCOME_MAX);
				  counter_outcome = OUTCOME_INVALID;
				  break;
				}

			      if (outcome < counter_outcome)
				{
				  outcome = counter_outcome;
				  best_square = square;
				  best_piece = piece;
				}
			    }
			}
		    }
		}
	    }
	}
      assert(outcome != OUTCOME_INVALID);
      return outcome;
    }