Evaluating Logic Circuits with Ternary Logic Graphs

This article describes how a basic RS NOR flip-flop circuit can be simulated using a directed graph constructed with source nodes (which output a value to nodes), terminal nodes (which take input from nodes), and gate nodes (which take input from nodes, do something with it, and provide the output to nodes). This graph propagates changed values to simulate the flow of electricity in the real-life logic circuit. It is based on a ternary logic system, which consists of a third unknown value in addition to the normal true and false values. In this article, balanced ternary is used to represent these values: +1 for true, 0 for unknown, and -1 for false. The language used in this article is Swift, as I wanted to try it out here by building (the bones of) a circuit simulator iOS app.

The Logic Graph

Logic nodes are based upon two main protocols, which set out what nodes that provide output to the graph and a nodes that take input from the graph should do. Ternary values are represented by the type TValue, a typealias of Int.

The following structure represents an input to a logic node. This defines the node that the input is connected to, and the index of the input (this is useful when the referenced logic node has more than one input connection):

struct LogicNodeInput {
    var node: LogicNode
    var index: Int
}

The protocol for a node that provides an output to the graph (such as a button) is defined below:

protocol OutputNode {
    var outputValue: TValue { get set }
    var childInputs: [LogicNodeInput] { get set }
}

Each node providing an output to the graph has an array of child inputs, which are inputs that the source node is connected to in the logic circuit. When the node providing an output changes its outputValue, it passes the updated value and the corresponding input index to each node in its childInputs array using the update function, as shown by this implementation:

var outputValue: TValue {
    didSet {
        for input in childInputs {
            input.node.update(input.index, newValue: outputValue)
        }
    }
}

The other main protocol is for a node that takes an input from the graph, such as a lamp. This complements the OutputNode protocol to form a prototype for the I/O of a gate node.

protocol InputNode {
    var inputValues: [TValue] { get set }
    func update(inputIndex: Int, newValue: TValue)
}

As you can see, nodes that takes an input from the graph implement an update function, which is called by the OutputNode implementer whenever an input to the node changes. An example of a class which implements of this function is the TwoGateNode class, the base class for all logic gates with two inputs:

class TwoGateNode : LogicNode {
    var gateName : String
    var logicGateFunc: ((TValue, TValue) -> TValue)?
    
    init(gateName: String, children: [LogicNodeInput] = []) {
        self.gateName = gateName
        super.init()
        self.childInputs = children
        self.inputValues = [tunknown, tunknown]
    }
    
    func eval() -> TValue {
        return logicGateFunc!(inputValues[0], inputValues[1])
    }
    
    // Override definition of update() in LogicNode class
    override func update(inputIndex: Int, newValue: TValue) {
        inputValues[inputIndex] = newValue
        delegate?.newInputValue(inputIndex, newInputValue: newValue)
        
        let newOutput: TValue = eval()
        
        if (newOutput != outputValue) {
            outputValue = newOutput
            delegate?.newOutputValue(newOutput)
            
            for input in childInputs {
                input.node.update(input.index, newValue: newOutput)
            }
        }
    }
}

Simulating an RS Latch

The RS NOR flip-flop circuit contains two source nodes, two gate nodes, and two terminal nodes. Initially their values are initialized to 0 (unknown):

If we set R and S to false, so that the latch is neither being set nor reset, the output (Q) remains unknown, as the state held by the latch is unknown:

Setting R to true resets the flip-flop, setting the value of the latch to false:

In step 1, the value of the reset node is updated. The reset node then updates its child, the NOR node. The updated input causes the NOR node to evaluate to false, as 1 NOR 0 = -1. As its value has changed, the NOR node now updates its children: the Q node and the second NOR node. This second NOR node now evaluates to true, as -1 NOR -1 = +1. Therefore, it updates its children: the Q̄ node and the first NOR node. The first NOR node reevaluates itself with the new input, but its output remains the same, so it does not need to update its children and the update process is concluded.

Setting R to false causes this new value to be propagated to the top NOR node, but the value of the NOR node does not change as the latch retains its state:

Setting S to true sets the value of the latch to true. Because the design of the flip-flop is symmetrical, setting S to true causes the same events to occur except with the vertically opposite nodes. Instead of Q being set to true and Q̄ to false, Q̄ is set to true and Q to false:

Finally, as with setting R to false, setting S to false causes propagation of S=-1, but again the value of the NOR node does not change, and the latch retains its state:

Here is a demonstration of an RS latch created with this circuit simulator running in the iOS Simulator. Notice how both lamps remain off until the reset button is toggled, indicating that the value of Q was initially unknown:

Threes! AI — A Simple Distribution Method

The expectimax algorithm used by my AI for Threes! is fairly easy to parallelize, because the branches of the game tree can be surveyed in parallel. While developing the AI, I used the std::async function in C++ so that each node (up to a certain depth I defined) would run the expectimax algorithm on all of its child nodes in parallel. For production however, I wanted to run the AI on a small cluster of Raspberry Pis I had available, as they are fairly low power and, more importantly, they run silently.

In order to distribute the work amongst the Pis, I decided I would have one “master” computer that keeps track of the game state, decides what moves to make, and makes the moves. When deciding what the next move should be, this master computer then can use the help of the “worker” computers1. This worked better than just having each computer act as a worker, distributing work to its fellow workers. In this case, as you looked more moves in advance, each worker ended up spending a lot of time trying to find workers to distribute work to, which resulted in a lot of unnecessary holdup.

For communication between the computers, I chose to use simple TCP sockets. As my needs were quite simple, I decided to interface directly with the C APIs rather than finding a C++ socket library.

Here is a basic overview of what the master computer does when deciding what the next move should be:

  1. Find the depth (number of moves ahead) which the AI will look. This is done by the dynamic_depth function, which takes into account parameters like how far into the game the current move is and how many empty tiles there are on the board.

  2. Call the expectimax function, which traverses the game tree on the master computer until the parallelization depth is reached. The parallelization depth for each move is a constant number of levels above the leaf nodes.

  3. When the parallelization depth is reached, iterate through each of the parallelized node’s children, and ask an available worker to find the score of this child. Wait for the results from the workers.

  4. Use the results from the workers to find the score of the parallelized node. The score of the parallelized node is then used by the parent node to find the score of the parent, then the parent of the parent node to find the grandparent node’s score, and so on until the root node is reached.

  5. When the root node is reached, choose the move corresponding to the highest scoring branch as the next move.

It’s step 3 in which the distribution occurs. This occurs by a short sequence of messages between the master and workers. Each message is prefixed by 4 characters which signify the length of the body of the message2, so the receiving computer knows how many characters it should listen for.

Firstly, the master sends each worker node the “READY” message:

Workers that are currently not processing a job listen out for this message, and will respond with the “READY” message to indicate that they are ready to accept work from the master:

The master then serialises the board data along with a few other parameters and sends this data to the first-responding worker:

This message is structured as follows:

The worker now decodes the message, creates the board object, and surveys the remainder of the branch locally with the expectimax algorithm. It then sends the score of the parallelized node to the master (in this case 2637.436035) and closes the connection:

  1. Technically, the master computer is also a worker: due to the low resource usage of the master process, it makes sense to run a worker process on the same computer to utilise as much of the cluster’s computing power as possible.

  2. A higher base could have been used to represent this length in order to code for longer message bodies, but this is unnecessary here as the message body length should never exceed 9999 characters.

Seattle 2014 →

I recently uploaded some pictures to Flickr from my holiday in Seattle:

Downtown Seattle as seen from the ferry

Columbia Center Sky View Observatory

Mt Rainier National Park

Mt St Helens

View the full set.

Threes! AI — Game Representation

Please note that this article contains spoilers about the internal workings of Threes! such as the next tile generator.

Threes!

Threes! is a puzzle game about combining numbers.  To start with, 1 and 2 become 3.   After 1 and 2, you can only combine tiles of the same value, so 3 and 3 would become 6, and 6 and 6 would become 12.   You may be familiar with this concept of combining numbers, which is featured in the popular game 2048 (derived from Threes, and in which powers of 2 are combined).

I played the game for a while, and having reached a fairly meagre high score of 27,351, I wondered if I could create an AI which would play Threes better than me.  I chose to use C++ rather than Python to create this AI to take advantage of the threading features in C++11, and also to have more control over how the game state was stored and passed around.

This article will discuss how I represented the game, namely the storage of the game state, the possible moves, the tile generator, and the scoring system.

Tiles

There are 16 tiles in Threes, each of which can take on a value of either 0 (empty), 1, 2, or \( 3 \times 2^n \) (where n is a non-negative integer).  So I coded the tile value as below:

\[ c(x) = \left\{ \begin{array}{ll} x & \mbox{if } x \leq 3 \\ 3 + \log_2\left(\frac{x}{3}\right) & \mbox{if } x > 3 \end{array} \right. \]

A coded tile value can then be decoded in the following way:

\[ c^{-1}(x) = \left\{ \begin{array}{ll} x & \mbox{if } x \leq 3 \\ 3 \times 2^{x-3} & \mbox{if } x > 3 \end{array} \right. \]

In this way, tile values up to 12288 (\( 3 \times 2^{15-3} \)) can be stored in a nibble. The game state contains 16 tiles of 4 bits, so a total of 64 bits is needed to store the game state. I chose to store the game state as a 64 bit integer.

We can now define a function which determines whether two tiles can be paired, and finds the value of the combined tile if they can be paired:

const int CANNOT_PAIR = -1;

static int pair_result(int x, int y) {
    if (x > 2 && y > 2 && x == y) {
        return x + y;
    } else if (x == 0 || y == 0) {
        return max(x, y);
    } else if (x + y == 3) {
        return 3;
    }
    return CANNOT_PAIR;
}

The first conditional allows two tiles with a value of the same multiple of 3 to be paired. The second conditional allows a tile to move into an empty space. For example, if a 6 tile is being moved into an empty space, pair_result(6, 0) will be called, which will give a result of 6, so the value of the empty space becomes 6. The tile value for the initial position of the 6 tile is then set to 0. The last conditional allows 1 and 2 to be paired to make 3. If none of these cases apply, then the tiles cannot be paired.

Moves

There are four moves in Threes, which are up, down, left, and right. I could have implemented these moves with one function, however for readability purposes and because there are only four moves, I decided to implement a function for each move. Here, I’ll describe the up move.

When the board is slid up, the top row is immobile and cannot move. So we skip the first row and start from the second row. We then try to slide each tile onto the one above it. If they don’t pair, then we leave the tile as it is. If they do pair, then we set the top tile to the combined value and we set the bottom tile to 0 (to represent an empty tile location). Having finished the second row, we repeat this for the third row and finally the last row.

If we manage to pair at least one tile (including pairing a tile with an empty space) during this process, then the move is possible. At least one tile needs to move for the slide to be considered valid: if no tiles move, the game state doesn’t change.

Here is the function which is called to slide the board up:

bool Board::slide_up() {
    bool can_move = false;
    for (int i=1; i < 4; i++) {
        for (int j=0; j < 4; j++) {
            if (tile(i, j) == 0) {
                continue;
            }
            
            int pair_res = pair_result(tile(i, j), tile(i-1, j));
            
            if (pair_res != CANNOT_PAIR) {
                set_tile(i-1, j, pair_res);
                set_tile(i, j, 0);
                if (pair_res != 0) {
                    can_move = true;
                }
            }
        }
    }
    
    if (can_move) {
        last_slide = SLIDE_UP;
    }
    
    return can_move;
}

If the move is valid, then the player’s turn is finished, and the computer will then place the next tile onto the board (we’ll discuss how the AI does this in a later article).

Tile Generator

In Threes, the tile generator algorithm decides the next tile to be put in play (which is then displayed at the top of the screen). It is also used to select the starting tiles for a new game. The AI I created uses the description of the algorithm posted to Touch Arcade by kamikaze28. Tile generation is divided into two parts: the basic tiles, and the bonus tiles.

The basic tiles are 1, 2, and 3. These are generated by the following procedure, as described by kamikaze28:

The mechanic for drawing basic cards is best described with a face-down stack of cards as one would use in card games like Mau Mau or Gin rummy. In the case of Threes! this stack is comprised of the following cards:

  • 4x blue 1s
  • 4x red 2s
  • 4x white 3s

As with the physical analogy, card stacks in Threes! are also shuffled upon creation. …With every move the top card of the stack is drawn which reveals the next card. When the last card of a stack is drawn after a move, a new stack is instantly created and shuffled. The top card of the fresh stack is then displayed as the next card.

Tiles above 3 are considered bonus tiles. The highest bonus tile that can be generated is the highest tile value on the board divided by 8, so bonus tiles can only be generated when a 48 tile or higher is on the board.

When bonus tiles are available, there is a 1/21 chance that the tile generated will be a bonus tile. Each bonus tile available has an equal chance of being generated, so the chance of a 6 being generated is the same as the chance of a 12 being generated (if both 6 and 12 are available).

Basic tile generation

To implement the basic tile mechanism, I created an array called rem_tile_count. This stores the number of each of the 1, 2, and 3 tiles left in the stack. The following function returns the total number of remaining tiles, and regenerates the stack of tiles if it is empty:

int Board::total_tiles_rem() {
    int total_rem = std::accumulate(rem_tile_count, rem_tile_count+3, 0);
    
    if (total_rem == 0) {
        for (int i=0; i<3; i++) {
            rem_tile_count[i] = 4;
        }
        total_rem = 12;
    }
    return total_rem;
}

The basic tile is then generated by picking a random integer n, 0 ≤ n < total_tiles_remaining(). This can then be mapped to a tile value. The way that I do this can be visualised as assigning indexes to each tile, then generating the tile at index n. Let r(x) indicate the number of tiles of value x that remain in the stack. The 1 tile is assigned indexes 0 ≤ m < r(1). The 2 tile is then assigned indexes r(1) ≤ m < r(1) + r(2). Finally, the 3 tile is assigned indexes r(1) + r(2) ≤ m < r(1) + r(2) + r(3). Once the tile has been generated, we remove it from the stack and return its value. Here is an implementation of the basic tile generator (note that the r(x) function is denoted by rem_tile_count[x-1] due to the zero-indexing of arrays):

int Board::new_standard_tile() {
    int total_rem = total_tiles_rem();
    
    if (total_rem > 12) {
        throw "Total number of remaining tiles is too great.";
    }
    
    int rand_num = arc4random() % total_rem;
    
    if (rand_num < rem_tile_count[0]) {
        rem_tile_count[0]--;
        return 1;
    }
    
    if (rand_num < total_rem - rem_tile_count[2]) {
        rem_tile_count[1]--;
        return 2;
    }
    
    rem_tile_count[2]--;
    return 3;
}

Bonus tile generation

Because each bonus tile available has an equal chance of being generated, the bonus tile generator is much easier to implement. My implementation uses the fact that the bonus tiles 6, 12, 24, 48 etc have codes 4, 5, 6, 7 etc. First, we determine the maximum bonus tile value b (this is just the highest tile value on the board divided by 8). We then pick a random integer m, 4 ≤ m ≤ c(b). m is the coded value of the bonus tile, so the generated bonus tile value is \( c^{-1}(m) \).

I implemented this method slightly differently so that the random integer I need is of the format produced by arc4random().

First I found the number of bonus tiles available, s. This is equal to c(b) - 3 because the bonus tiles have codes 4, 5, 6 and so on. Now I can pick an random integer q, 0 ≤ q < s. This inequality is equivalent to 0 ≤ q < c(b) - 3, which is equivalent to 0 ≤ q ≤ c(b) - 4 because we are dealing with integers.

Therefore, to obtain the tile code of the generated tile, we can manipulate the inequality so it takes the form of the inequality 4 ≤ m ≤ c(b) that we found earlier. Adding 4 to each part of the inequality, we get 4 ≤ q + 4 ≤ c(b). It is now easy to see that m = q + 4, so the generated bonus tile value is \( c^{-1}(q+4) \).

This function defines the number of cards in the bonus pool, s:

int Board::bonus_pool_size() {
    int max_card = encode_tile_val(high_tile_val / 8);
    return std::max(0, max_card - 3);
}

And here is the function which generates the bonus tile, \( c^{-1}(m) \):

int Board::new_bonus_tile() {
    uint8_t tile_code = 4 + arc4random() % bonus_pool_size();
    return decode_tile_val(tile_code);
}

 

We can now generate a tile like so:

int Board::generate_new_tile_val() {
    if (high_tile_val >= 48 && arc4random() % 21 == 0) {
        return new_bonus_tile();
    }
    
    return new_standard_tile();
}

Scoring

Our representation of the game is coming along well, however we need to be able to differentiate between game states so that the AI can choose the move that will lead to the best game state. We do this by scoring the board. For now, we will implement the scoring that Threes uses itself, however we could define heuristics so that the AI will prefer certain characteristics such as empty spaces or a uniform gradient of tiles.

Threes scores each individual tile, so that the score of the board is the sum of all the individual tiles. Tiles less than 3 are worth nothing. For tiles 3 and over, a tile value of x will score \( 3^{\log_2(\frac{x}{3}) + 1} \) points.

Here is an implementation of a function to give the score of an individual tile:

int tile_score(int tile_val) {
    if (tile_val < 3) {
        return 0;
    }
    return pow(3, intlog2(tile_val/3) + 1);
}

Hence, the score of a game state can then be evaluated using the following function:

int Board::score() {
    int board_score = 0;
    for (int i = 0; i < 16; i++) {
        board_score += tile_score(tile(i/4, i%4));
    }
    return board_score;
}

 

We can now store the game state, execute moves, generate new tiles using the correct procedure, and evaluate the score of particular game states. An AI can now be implemented on top of this core logic.

Regex Crossword →

p1I recently finished the Hamlet series of the Regex Crossword puzzles. These are crossword puzzles where clues are not in the format of sentences, but instead are regular expressions that the appropriate row or column must satisfy.  The website contains several collections of puzzles, each with a common theme such as cities or palindromes for example.  I enjoyed completing these puzzles and I’d recommend them to any regex fans.

For a more extreme challenge, check out the hexagonal regex crossword created for the 2013 MIT Mystery Hunt.

Less Recently