Programming an Award-Winning Connect 4 Bot at ElixirConf 2017

Last week several fellow SmartLogic developers and I had the opportunity to travel to beautiful Bellevue, Washington for a three-day hiatus from our regular engineering activities in order to do a dive deep into one of our favorite programming languages, Elixir, at the premier North American conference that celebrates this powerful and modern programming language: ElixirConf. The conference itself was informative, entertaining, well-attended, and well-organized; I’d give it a solid 10/10 and would definitely recommend other developers interested in the language try to attend in the future.

As a language, Elixir is fast and reliable and designed for developer productivity and scalability. Because of these benefits, Elixir and its flagship web framework, Phoenix, have become our backend stack of choice here at SmartLogic, and while we don’t do gaming here, the highlight of my trip to ElixirConf was an after-session bot-programming competition, hosted by Alan Voss (via RentPath) and based on the classic board game, Connect 4.

The Game

Many of us grew up playing Connect 4, where you drop black and white tokens into a vertical board with seven columns and six rows. It was evident that Alan had put a lot of work into preparing Elixir code to facilitate the contest, and these efforts resulted in an engaging, educational, and (most importantly) fun event for everyone who attended.

To win at Connect 4 you connect four of your color tokens in a row before your opponent, however to win at this coding competition we were tasked with spending 90 minutes to program a bot that plays Connect 4 better than anyone else’s bot. Alan produced a program that would run a Round Robin style tournament with all the contenders in play. Submission was done by pull request, and Alan ran the games against one another in real time on a projector in front of the room so we could all see how everybody’s bot performed (the repo is available here on GitHub).

The Twist (or: How to win at anything)

Funny thing, everything I’ve reported so far is not actually from first-hand experience. While I’d fully intended on attending the Connect 4 competition, dinner with my team ran over that night, and by the time I made it to the event, found a partner, and got acquainted with the format, I was down to 45 mins to compete--roughly half the time of all the other participants.

We’ve all had situations like this. Schedules don’t line up. Deadlines loom. Suddenly we’re short on time and we’re faced with a seemingly impossible objective. These moments can break people. Often, under pressure, our inner monologues become a distraction. They cause us to judge, evaluate, and lose focus. I’ve found--through sport, work, and study--that the key to performance under pressure is to silence the train of thought.

Spoiler alert: we won. You probably already knew this (have you even been paying attention?), but the question was never what happened but how it happened. In the end, there were three principles at work here:

  1. Learning first;
  2. Over-communication; and
  3. Default to simplicity

When I turned off my inner monologue I defaulted to the above strategies that have guided me for the last twenty years--things I now do instinctively.

Learning First

My preference for learning meant that I was completely unconcerned with winning. I was only concerned with progress. Rapid progress. This preference manifested itself in the Connect 4 contest in my choice of partner. Choices were limited by my lateness, however, I happened to strike up a conversation with an experienced Elixir developer, Eric Toulson. We were both competitive and late to the game. He had a bot strategy in mind. Looking back on it, maybe I lucked out. Okay, probably, but I like to think that “real recognize real.”

Over-Communicate

This is something I try to do at work and in my personal life. Let me illustrate the importance of communication through a short digression. I was recently in China for a few weeks with a diverse group of friends. These folks were more or less introverted (ok, more introverted than I am). We’d often go looking for food, and I’d find myself experiencing an uncomfortable kind of Deja Vu. One of us would be drawn to place. We might ask: “What do you think of this place?” Responses would be mixed-ish. The most usual response was a sort of ambivalent, mostly non-verbal approval or disapproval. For me, a talker, this was extremely confusing. I could sense that the group didn’t like the restaurant, but I never knew why. Never, ever, would everyone in the group offer up a verbal response, yet every single time, every single one of these people had plenty of thoughts. They were withholding information. They were withholding lots of information in a situation where there was absolutely nothing to gain from withholding lots of information. This happens all the time in business. Lots of hidden agendas. Very little talking. Very little benefit to silence.

Sure, there are times to be silent. And there are times to talk. At SmartLogic, we pair program often. We get a lot of mileage out of talking to one another. By pairing and talking through our ideas. We get more transparency into the thought processes that eventually crystallize into code. Pairing leads to faster feedback loops between humans. These feedback loops accelerate learning, cement technical understanding, and build rapport.

Pairing effectively is a super power. Over-communicating is a strategy to make yourself more clear. Being more clear means being more understood.

To be clear, I don’t mean over-talking. I mean over-talking and over-listening. As in there cannot be too much of both in balance. Here are two simple rules for over-communication:

  1. When multiple people are collaborating, at any given time one of them should be talking through their thought processes (while the other person is actively listening); and
  2. The group should aim to split talking time equally (see Google’s research on this)

During our little contest, Eric and I over-communicated. We spoke and listened and transacted a lot of information. Realistically, he taught and I listened, and I was lucky to be in that position, because I learned a lot.

Default to Simplicity

This is a tough one. Most people seem to think simplicity means straight lines and no elaboration. I think simplicity means that important things take precedence. Really, simplicity is about prioritization. Apple products are considered the pinnacle of simplicity of design because they have their priorities in order. User experience over everything. Likewise, in order to build a great bot, our priorities must be in order. Or at least, in better order than the competition. Once again, Eric came to the rescue with some solid priorities. Here is how we prioritized developing our bot:

  1. If there is a winning move on the board, take it;
  2. If there is a blocking move on the board, take it; and
  3. Google a perfect strategy and implement that

Implementing a Contender

Step One: Copy The Sample Code

The easiest way to learn is to copy. Going through the sample contender helped us understand the module’s external APIs. This is how we learned to interact with the game logic.

defmodule ConnectFour.Contenders.PureRandomness do  
  use GenServer

  def start(default) do
    GenServer.start(__MODULE__, default)
  end

  def handle_call(:name, _from, state) do
    letters = for n <- ?A..?Z, do: n
    random_name =
      for _ <- 1..12 do
        Enum.random(letters)
      end

    {:reply, List.to_string(random_name), state}
  end

  def handle_call({:move, board}, _from, state) do
    random_column =
      board
      |> Enum.at(0)
      |> Enum.with_index
      |> Enum.filter(&(elem(&1, 0) == 0))
      |> Enum.map(&(elem(&1, 1)))
      |> Enum.random

    {:reply, random_column, state}
  end
end  

This PureRandomness Contender module handles two calls. One to give a name (a random string of numbers) and another to select an available move.

Look at the function definitions and notice how a Module can have two functions with the same name. This is possible because of Elixir’s powerful pattern matching capabilities. If the module is called with a leading :name atom then it will return a name. If it is called with a leading {:move, board} then it will return a 3-element tuple like so: {:reply, random_column, state}.

This yields an important realization. A move in Connect 4 is a simple decision. We simply return the column number we want to play. Easy.

Instead of pure_randomness.ex, we named our script basic.ex. Instead of PureRandomness, we called the module Rocky (original, I know). Then we proceeded to hack the contender (and the game).

defmodule ConnectFour.Contenders.Rocky do  
  use GenServer
  alias ConnectFour.BoardHelper

  def start(default) do
    GenServer.start(__MODULE__, default)
  end

  def handle_call(:name, _from, state) do
    {:reply, "Rocky", state}
  end

  ...

Step Two: Test Your Code (Hack the Test)

In the README provided by Alan, we can see there is a bin/match script. It takes two contender modules as arguments. The two contenders will face off in a Connect 4 match to the death (ok, maybe contenders don’t die--they’re computer programs!).

Now, one of the coolest aspects of this match function is the graphical display that emerges on your terminal to show game progress. You can see your contender making moves against its opponent. At the end of the animation, you learn who won! Look here:

mix run -e "result = ConnectFour.Controller.do_game([ConnectFour.Contenders.$1, ConnectFour.Contenders.$2]); result |> ConnectFour.Controller.display_game(false); IO.inspect result"  

This shell script runs the game pitting the two contenders against one another. The line actually displaying the game is my problem. Removing it leaves the following:

mix run -e "ConnectFour.Controller.do_game([ConnectFour.Contenders.$1, ConnectFour.Contenders.$2])"  

This tiny hack gave us a huge advantage

You see, running the match to test our bot against the PureRandomness contender took seconds and seconds. It was agonizing. Removing the display feature cut our feedback loop by an order of magnitude or two. Suddenly we could test our bot over and over while our competition was waiting for matches to complete. Maybe some of the other competitors figured this out? I have no way of knowing.

Step Three: Implement Your Strategy

Remember our priorities?

  1. Take a winning move; and
  2. Block the opponent from winning

First things first. We have to check the board for winning moves.

  …

  def win_check(board, contender) do
    for sim_move <- possible_moves() do 
      with {:ok, board} <- BoardHelper.drop(board,contender,sim_move),
           {:winner, winner} <- BoardHelper.evaluate_board(board) do
         sim_move
      else 
        _ ->nil
      end
    end
  end
  def possible_moves do
    0..6 |> Enum.to_list
  end

You can see this function is multi-purpose. We can pass either contender into the second argument to see if they have a winning move available to them. This will be useful to see if the opponent has any winning moves open to them.

You can also see that we’re using some of Alan’s BoardHelper functions to perform the heavy lifting of checking for a winner (BoardHelper.evaluate/3) and simulating moves (BoardHelper.drop/3).

Now, let’s execute a winning move if it becomes available.

 def handle_call({:move, board}, _from, state) do

    winning_move = win_check(board, 1)
    |> Enum.reject(fn(column) -> is_nil(column) end)
    |> List.first

    {:reply, (winning_move || blocking_move || random_column), state}
  end

Now, when Rocky receives a call with the {:move, board} tuple we can respond with a winning move or… Nothing? Ok, well that won’t get us very far since the game is Connect F-O-U-R. Let’s implement a blocking move the same way we did the winning move check.

 def handle_call({:move, board}, _from, state) do
    winning_move = win_check(board, 1)
    |> Enum.reject(fn(column) -> is_nil(column) end)
    |> List.first

    blocking_move = win_check(board, 2)
    |> Enum.reject(fn(column) -> is_nil(column) end)
    |> List.first

    {:reply, (winning_move || blocking_move ), state}
  end

Ah, now we’re onto something, but unfortunately, we were running out of time and fast. We determined we had to have some default heuristic for making non-winner, non-blocking moves.

Cue -- Randomness:

 def handle_call({:move, board}, _from, state) do
    random_column =
      board
      |> Enum.at(0)
      |> Enum.with_index
      |> Enum.filter(&(elem(&1, 0) == 0))
      |> Enum.map(&(elem(&1, 1)))
      |> Enum.random

    winning_move = win_check(board, 1)
    |> Enum.reject(fn(column) -> is_nil(column) end)
    |> List.first

    blocking_move = win_check(board, 2)
    |> Enum.reject(fn(column) -> is_nil(column) end)
    |> List.first

    {:reply, (winning_move || blocking_move || random_column), state}
  end

Ah. Isn’t that an elegant function? I love it. Simple. Makes use of the language’s most powerful features. Plus it wins.

Reflections

I love friendly competition. Actually, just about the only thing I like more than competition is learning, so a competition that helps me learn might just be the best thing ever, and that’s why I really enjoyed participating in the Connect 4 competition.

I suppose in the future you could wow people by implementing a bot with perfect logic. Then you’d win every time. Or, at least half the time.

While the competition was gaming-based--something I never do at work--my team’s ultimate success despite our time limitations drew on the foundational skills I use every day when I am at work here at SmartLogic: put learning first, over-communicate, and default to simplicity.

View the code in Alan’s repo and in my “Basic” Rocky module: https://github.com/alanvoss/connect_four

comments powered by Disqus