Articles tagged ai at null program 2019-12-08T14:30:22Z urn:uuid:bbcac281-4091-4371-aaed-1061fd43ac26 Christopher Wellons When the Compiler Bites urn:uuid:02b974e1-e25b-397d-a16f-c754338e9c1e 2018-05-01T23:28:06Z Update: There are discussions on Reddit and on Hacker News.

So far this year I’ve been bitten three times by compiler edge cases in GCC and Clang, each time catching me totally by surprise. Two were caused by historical artifacts, where an ambiguous specification lead to diverging implementations. The third was a compiler optimization being far more clever than I expected, behaving almost like an artificial intelligence.

In all examples I’ll be using GCC 7.3.0 and Clang 6.0.0 on Linux.

x86-64 ABI ambiguity

The first time I was bit — or, well, narrowly avoided being bit — was when I examined a missed floating point optimization in both Clang and GCC. Consider this function:

zero_multiply(double x)
    return x * 0.0;

The function multiplies its argument by zero and returns the result. Any number multiplied by zero is zero, so this should always return zero, right? Unfortunately, no. IEEE 754 floating point arithmetic supports NaN, infinities, and signed zeros. This function can return NaN, positive zero, or negative zero. (In some cases, the operation could also potentially produce a hardware exception.)

As a result, both GCC and Clang perform the multiply:

    xorpd  xmm1, xmm1
    mulsd  xmm0, xmm1

The -ffast-math option relaxes the C standard floating point rules, permitting an optimization at the cost of conformance and consistency:

    xorps  xmm0, xmm0

Side note: -ffast-math doesn’t necessarily mean “less precise.” Sometimes it will actually improve precision.

Here’s a modified version of the function that’s a little more interesting. I’ve changed the argument to a short:

zero_multiply_short(short x)
    return x * 0.0;

It’s no longer possible for the argument to be one of those special values. The short will be promoted to one of 65,535 possible double values, each of which results in 0.0 when multiplied by 0.0. GCC misses this optimization (-Os):

    movsx     edi, di       ; sign-extend 16-bit argument
    xorps     xmm1, xmm1    ; xmm1 = 0.0
    cvtsi2sd  xmm0, edi     ; convert int to double
    mulsd     xmm0, xmm1

Clang also misses this optimization:

    cvtsi2sd xmm1, edi
    xorpd    xmm0, xmm0
    mulsd    xmm0, xmm1

But hang on a minute. This is shorter by one instruction. What happened to the sign-extension (movsx)? Clang is treating that short argument as if it were a 32-bit value. Why do GCC and Clang differ? Is GCC doing something unnecessary?

It turns out that the x86-64 ABI didn’t specify what happens with the upper bits in argument registers. Are they garbage? Are they zeroed? GCC takes the conservative position of assuming the upper bits are arbitrary garbage. Clang takes the boldest position of assuming arguments smaller than 32 bits have been promoted to 32 bits by the caller. This is what the ABI specification should have said, but currently it does not.

Fortunately GCC also conservative when passing arguments. It promotes arguments to 32 bits as necessary, so there are no conflicts when linking against Clang-compiled code. However, this is not true for Intel’s ICC compiler: Clang and ICC are not ABI-compatible on x86-64.

I don’t use ICC, so that particular issue wouldn’t bite me, but if I was ever writing assembly routines that called Clang-compiled code, I’d eventually get bit by this.

Floating point precision

Without looking it up or trying it, what does this function return? Think carefully.

    float x = 1.3f;
    return x == 1.3f;

Confident in your answer? This is a trick question, because it can return either 0 or 1 depending on the compiler. Boy was I confused when this comparison returned 0 in my real world code.

$ gcc   -std=c99 -m32 cmp.c  # float_compare() == 0
$ clang -std=c99 -m32 cmp.c  # float_compare() == 1

So what’s going on here? The original ANSI C specification wasn’t clear about how intermediate floating point values get rounded, and implementations all did it differently. The C99 specification cleaned this all up and introduced FLT_EVAL_METHOD. Implementations can still differ, but at least you can now determine at compile-time what the compiler would do by inspecting that macro.

Back in the late 1980’s or early 1990’s when the GCC developers were deciding how GCC should implement floating point arithmetic, the trend at the time was to use as much precision as possible. On the x86 this meant using its support for 80-bit extended precision floating point arithmetic. Floating point operations are performed in long double precision and truncated afterward (FLT_EVAL_METHOD == 2).

In float_compare() the left-hand side is truncated to a float by the assignment, but the right-hand side, despite being a float literal, is actually “1.3” at 80 bits of precision as far as GCC is concerned. That’s pretty unintuitive!

The remnants of this high precision trend are still in JavaScript, where all arithmetic is double precision (even if simulated using integers), and great pains have been made to work around the performance consequences of this. Until recently, Mono had similar issues.

The trend reversed once SIMD hardware became widely available and there were huge performance gains to be had. Multiple values could be computed at once, side by side, at lower precision. So on x86-64, this became the default (FLT_EVAL_METHOD == 0). The young Clang compiler wasn’t around until well after this trend reversed, so it behaves differently than the backwards compatible GCC on the old x86.

I’m a little ashamed that I’m only finding out about this now. However, by the time I was competent enough to notice and understand this issue, I was already doing nearly all my programming on the x86-64.

Built-in Function Elimination

I’ve saved this one for last since it’s my favorite. Suppose we have this little function, new_image(), that allocates a greyscale image for, say, some multimedia library.

static unsigned char *
new_image(size_t w, size_t h, int shade)
    unsigned char *p = 0;
    if (w == 0 || h <= SIZE_MAX / w) { // overflow?
        p = malloc(w * h);
        if (p) {
            memset(p, shade, w * h);
    return p;

It’s a static function because this would be part of some slick header library (and, secretly, because it’s necessary for illustrating the issue). Being a responsible citizen, the function even checks for integer overflow before allocating anything.

I write a unit test to make sure it detects overflow. This function should return 0.

/* expected return == 0 */
    void *p = new_image(2, SIZE_MAX, 0);
    return !!p;

So far my test passes. Good.

I’d also like to make sure it correctly returns NULL — or, more specifically, that it doesn’t crash — if the allocation fails. But how can I make malloc() fail? As a hack I can pass image dimensions that I know cannot ever practically be allocated. Essentially I want to force a malloc(SIZE_MAX), e.g. allocate every available byte in my virtual address space. For a conventional 64-bit machine, that’s 16 exibytes of memory, and it leaves space for nothing else, including the program itself.

/* expected return == 0 */
    void *p = new_image(1, SIZE_MAX, 0xff);
    return !!p;

I compile with GCC, test passes. I compile with Clang and the test fails. That is, the test somehow managed to allocate 16 exibytes of memory, and initialize it. Wat?

Disassembling the test reveals what’s going on:

    xor  eax, eax

    mov  eax, 1

The first test is actually being evaluated at compile time by the compiler. The function being tested was inlined into the unit test itself. This permits the compiler to collapse the whole thing down to a single instruction. The path with malloc() became dead code and was trivially eliminated.

In the second test, Clang correctly determined that the image buffer is not actually being used, despite the memset(), so it eliminated the allocation altogether and then simulated a successful allocation despite it being absurdly large. Allocating memory is not an observable side effect as far as the language specification is concerned, so it’s allowed to do this. My thinking was wrong, and the compiler outsmarted me.

I soon realized I can take this further and trick Clang into performing an invalid optimization, revealing a bug. Consider this slightly-optimized version that uses calloc() when the shade is zero (black). The calloc() function does its own overflow check, so new_image() doesn’t need to do it.

static void *
new_image(size_t w, size_t h, int shade)
    unsigned char *p = 0;
    if (shade == 0) { // shortcut
        p = calloc(w, h);
    } else if (w == 0 || h <= SIZE_MAX / w) { // overflow?
        p = malloc(w * h);
        if (p) {
            memset(p, color, w * h);
    return p;

With this change, my overflow unit test is now also failing. The situation is even worse than before. The calloc() is being eliminated despite the overflow, and replaced with a simulated success. This time it’s actually a bug in Clang. While failing a unit test is mostly harmless, this could introduce a vulnerability in a real program. The OpenBSD folks are so worried about this sort of thing that they’ve disabled this optimization.

Here’s a slightly-contrived example of this. Imagine a program that maintains a table of unsigned integers, and we want to keep track of how many times the program has accessed each table entry. The “access counter” table is initialized to zero, but the table of values need not be initialized, since they’ll be written before first access (or something like that).

struct table {
    unsigned *counter;
    unsigned *values;

static int
table_init(struct table *t, size_t n)
    t->counter = calloc(n, sizeof(*t->counter));
    if (t->counter) {
        /* Overflow already tested above */
        t->values = malloc(n * sizeof(*t->values));
        if (!t->values) {
            return 0; // fail
        return 1; // success
    return 0; // fail

This function relies on the overflow test in calloc() for the second malloc() allocation. However, this is a static function that’s likely to get inlined, as we saw before. If the program doesn’t actually make use of the counter table, and Clang is able to statically determine this fact, it may eliminate the calloc(). This would also eliminate the overflow test, introducing a vulnerability. If an attacker can control n, then they can overwrite arbitrary memory through that values pointer.

The takeaway

Besides this surprising little bug, the main lesson for me is that I should probably isolate unit tests from the code being tested. The easiest solution is to put them in separate translation units and don’t use link-time optimization (LTO). Allowing tested functions to be inlined into the unit tests is probably a bad idea.

The unit test issues in my real program, which was a bit more sophisticated than what was presented here, gave me artificial intelligence vibes. It’s that situation where a computer algorithm did something really clever and I felt it outsmarted me. It’s creepy to consider how far that can go. I’ve gotten that even from observing AI I’ve written myself, and I know for sure no human taught it some particularly clever trick.

My favorite AI story along these lines is about an AI that learned how to play games on the Nintendo Entertainment System. It didn’t understand the games it was playing. It’s optimization task was simply to choose controller inputs that maximized memory values, because that’s generally associated with doing well — higher scores, more progress, etc. The most unexpected part came when playing Tetris. Eventually the screen would fill up with blocks, and the AI would face the inevitable situation of losing the game, with all that memory being reinitialized to low values. So what did it do?

Just before the end it would pause the game and wait… forever.

Two Games with Monte Carlo Tree Search urn:uuid:b6f77cb1-01df-3714-4ba0-1859614364da 2017-04-27T21:27:50Z Monte Carlo tree search (MCTS) is the most impressive game artificial intelligence I’ve ever used. At its core it simulates a large number of games (playouts), starting from the current game state, using random moves for each player. Then it simply picks the move where it won most often. This description is sufficient to spot one of its most valuable features: MCTS requires no knowledge of strategy or effective play. The game’s rules — enough to simulate the game — are all that’s needed to allow the AI to make decent moves. Expert knowledge still makes for a stronger AI, but, more many games, it’s unnecessary to construct a decent opponent.

A second valuable feature is that it’s easy to parallelize. Unlike alpha-beta pruning, which doesn’t mix well with parallel searches of a Minimax tree, Monte Carlo simulations are practically independent and can be run in parallel.

Finally, the third valuable feature is that the search can be stopped at any time. The completion of any single simulation is as good a stopping point as any. It could be due to a time limit, a memory limit, or both. In general, the algorithm converges to a best move rather than suddenly discovering it. The good moves are identified quickly, and further simulations work to choose among them. More simulations make for better moves, with exponentially diminishing returns. Contrasted with Minimax, stopping early has the risk that the good moves were never explored at all.

To try out MCTS myself, I wrote two games employing it:

They’re both written in C, for both unix-like and Windows, and should be easy to build. I challenge you to beat them both. The Yavalath AI is easier to beat due to having blind spots, which I’ll discuss below. The Connect Four AI is more difficult and will likely take a number of tries.

Connect Four

MCTS works very well with Connect Four, and only requires modest resources: 32MB of memory to store the results of random playouts, and 500,000 game simulations. With a few tweaks, it can even be run in DOSBox. It stops when it hits either of those limits. In theory, increasing both would make for stronger moves, but in practice I can’t detect any difference. It’s like computing pi with Monte Carlo, where eventually it just runs out of precision to make any more progress.

Based on my simplified description above, you might wonder why it needs all that memory. Not only does MCTS need to track its win/loss ratio for each available move from the current state, it tracks the win/loss ratio for moves in the states behind those moves. A large chunk of the game tree is kept in memory to track all of the playout results. This is why MCTS needs a lot more memory than Minimax, which can discard branches that have been searched.

A convenient property of this tree is that the branch taken in the actual game can be re-used in a future search. The root of the tree becomes the node representing the taken game state, which has already seen a number of playouts. Even better, MCTS is weighted towards exploring good moves over bad moves, and good moves are more likely to be taken in the real game. In general, a significant portion of the tree gets to be reused in a future search.

I’m going to skip most of the details of the algorithm itself and focus on my implementation. Other articles do a better job at detailing the algorithm than I could.

My Connect Four engine doesn’t use dynamic allocation for this tree (or at all). Instead it manages a static buffer — an array of tree nodes, each representing a game state. All nodes are initially chained together into a linked list of free nodes. As the tree is built, nodes are pulled off the free list and linked together into a tree. When the game advances to the next state, nodes on unreachable branches are added back to the free list.

If at any point the free list is empty when a new node is needed, the current search aborts. This is the out-of-memory condition, and no more searching can be performed.

/* Connect Four is normally a 7 by 6 grid. */
#define CONNECT4_WIDTH  7

struct connect4_node {
    uint32_t next[CONNECT4_WIDTH];      // "pointer" to next node
    uint32_t playouts[CONNECT4_WIDTH];  // number of playouts
    float    score[CONNECT4_WIDTH];     // pseudo win/loss ratio

Rather than native C pointers, the structure uses 32-bit indexes into the master array. This saves a lot of memory on 64-bit systems, and the structure is the same size no matter the pointer size of the host. The next field points to the next state for the nth move. Since 0 is a valid index, -1 represents null (CONNECT4_NULL).

Each column is a potential move, so there are CONNECT4_WIDTH possible moves at any given state. Each move has a floating point score and a total number of playouts through that move. In my implementation, the search can also halt due to an overflow in a playout counter. The search can no longer be tracked in this representation, so it has to stop. This generally only happens when the game is nearly over and it’s grinding away on a small number of possibilities.

Note that the actual game state (piece positions) is not tracked in the node structure. That’s because it’s implicit. We know the state of the game at the root, and simulating the moves while descending the tree will keep track of the board state at the current node. That’s more memory savings.

The state itself is a pair of bitboards, one for each player. Each position on the grid gets a bit on each bitboard. The bitboard is very fast to manipulate, and win states are checked with just a handful of bit operations. My intention was to make playouts as fast as possible.

struct connect4_ai {
    uint64_t state[2];         // game state at root (bitboard)
    uint64_t rng[2];           // random number generator state
    uint32_t nodes_available;  // total number of nodes available
    uint32_t nodes_allocated;  // number of nodes in the tree
    uint32_t root;             // "pointer" to root node
    uint32_t free;             // "pointer" to free list
    int turn;                  // whose turn (0 or 1) at the root?

The nodes_available and nodes_allocated are not necessary for correctness nor speed. They’re useful for diagnostics and debugging.

All the functions that operate on these two structures are straightforward, except for connect4_playout, a recursive function which implements the bulk of MCTS. Depending on the state of the node it’s at, it does one of two things:

  • If there are unexplored moves (playouts == 0), it randomly chooses an unplayed move, allocates exactly one node for the state behind that move, and simulates the rest of the game in a loop, without recursion or allocating any more nodes.

  • If all moves have been explored at least once, it uses an upper confidence bound (UCB1) to randomly choose a move, weighed towards both moves that are under-explored and moves which are strongest. Striking that balance is one of the challenges. It recurses into that next state, then updates the node with the result as it propagates back to the root.

That’s pretty much all there is to it.


Yavalath is a board game invented by a computer program. It’s a pretty fascinating story. The depth and strategy are disproportionately deep relative to its dead simple rules: Get four in a row without first getting three in a row. The game revolves around forced moves.

The engine is structured almost identically to the Connect Four engine. It uses 32-bit indexes instead of pointers. The game state is a pair of bitboards, with end-game masks computed at compile time via metaprogramming. The AI allocates the tree from a single, massive buffer — multiple GBs in this case, dynamically scaled to the available physical memory. And the core MCTS function is nearly identical.

One important difference is that identical game states — states where the pieces on the board are the same, but the node was reached through a different series of moves — are coalesced into a single state in the tree. This state deduplication is done through a hash table. This saves on memory and allows multiple different paths through the game tree to share playouts. It comes at a cost of including the game state in the node (so it can be identified in the hash table) and reference counting the nodes (since they might have more than one parent).

Unfortunately the AI has blind spots, and once you learn to spot them it becomes easy to beat consistently. It can’t spot certain kinds of forced moves, so it always falls for the same tricks. The official Yavalath AI is slightly stronger than mine, but has a similar blindness. I think MCTS just isn’t quite a good fit for Yavalath.

The AI’s blindness is caused by shallow traps, a common problem for MCTS. It’s what makes MCTS a poor fit for Chess. A shallow trap is a branch in the game tree where the game will abruptly end in a small number of turns. If the random tree search doesn’t luckily stumble upon a trap during its random traversal, it can’t take it into account in its final decision. A skilled player will lead the game towards one of these traps, and the AI will blunder along, not realizing what’s happened until its too late.

I almost feel bad for it when this happens. If you watch the memory usage and number of playouts, once it falls into a trap, you’ll see it using almost no memory while performing a ton of playouts. It’s desperately, frantically searching for a way out of the trap. But it’s too late, little AI.

Another Tool in the Toolbelt

I’m really happy to have sunk a couple weekends into playing with MCTS. It’s not always a great fit, as seen with Yavalath, but it’s a really neat algorithm. Now that I’ve wrapped my head around it, I’ll be ready to use it should I run into an appropriate problem in the future.

A GPU Approach to Path Finding urn:uuid:29de5cb3-f93a-3e6e-9adc-ff689e736877 2014-06-22T22:51:46Z Last time I demonstrated how to run Conway’s Game of Life entirely on a graphics card. This concept can be generalized to any cellular automaton, including automata with more than two states. In this article I’m going to exploit this to solve the shortest path problem for two-dimensional grids entirely on a GPU. It will be just as fast as traditional searches on a CPU.

The JavaScript side of things is essentially the same as before — two textures with fragment shader in between that steps the automaton forward — so I won’t be repeating myself. The only parts that have changed are the cell state encoding (to express all automaton states) and the fragment shader (to code the new rules).

Included is a pure JavaScript implementation of the cellular automaton (State.js) that I used for debugging and experimentation, but it doesn’t actually get used in the demo. A fragment shader (12state.frag) encodes the full automaton rules for the GPU.

Maze-solving Cellular Automaton

There’s a dead simple 2-state cellular automaton that can solve any perfect maze of arbitrary dimension. Each cell is either OPEN or a WALL, only 4-connected neighbors are considered, and there’s only one rule: if an OPEN cell has only one OPEN neighbor, it becomes a WALL.

On each step the dead ends collapse towards the solution. In the above GIF, in order to keep the start and finish from collapsing, I’ve added a third state (red) that holds them open. On a GPU, you’d have to do as many draws as the length of the longest dead end.

A perfect maze is a maze where there is exactly one solution. This technique doesn’t work for mazes with multiple solutions, loops, or open spaces. The extra solutions won’t collapse into one, let alone the shortest one.

To fix this we need a more advanced cellular automaton.

Path-solving Cellular Automaton

I came up with a 12-state cellular automaton that can not only solve mazes, but will specifically find the shortest path. Like above, it only considers 4-connected neighbors.

  • OPEN (white): passable space in the maze
  • WALL (black): impassable space in the maze
  • BEGIN (red): starting position
  • END (red): goal position
  • FLOW (green): flood fill that comes in four flavors: north, east, south, west
  • ROUTE (blue): shortest path solution, also comes in four flavors

If we wanted to consider 8-connected neighbors, everything would be the same, but it would require 20 states (n, ne, e, se, s, sw, w, nw) instead of 12. The rules are still pretty simple.

  • WALL and ROUTE cells never change state.
  • OPEN becomes FLOW if it has any adjacent FLOW cells. It points towards the neighboring FLOW cell (n, e, s, w).
  • END becomes ROUTE if adjacent to a FLOW cell. It points towards the FLOW cell (n, e, s, w). This rule is important for preventing multiple solutions from appearing.
  • FLOW becomes ROUTE if adjacent to a ROUTE cell that points towards it. Combined with the above rule, it means when a FLOW cell touches a ROUTE cell, there’s a cascade.
  • BEGIN becomes ROUTE when adjacent to a ROUTE cell. The direction is unimportant. This rule isn’t strictly necessary but will come in handy later.

This can be generalized for cellular grids of any arbitrary dimension, and it could even run on a GPU for higher dimensions, limited primarily by the number of texture uniform bindings (2D needs 1 texture binding, 3D needs 2 texture bindings, 4D needs 8 texture bindings … I think). But if you need to find the shortest path along a five-dimensional grid, I’d like to know why!

So what does it look like?

FLOW cells flood the entire maze. Branches of the maze are search in parallel as they’re discovered. As soon as an END cell is touched, a ROUTE is traced backwards along the flow to the BEGIN cell. It requires double the number of steps as the length of the shortest path.

Note that the FLOW cell keep flooding the maze even after the END was found. It’s a cellular automaton, so there’s no way to communicate to these other cells that the solution was discovered. However, when running on a GPU this wouldn’t matter anyway. There’s no bailing out early before all the fragment shaders have run.

What’s great about this is that we’re not limited to mazes whatsoever. Here’s a path through a few connected rooms with open space.

Maze Types

The worst-case solution is the longest possible shortest path. There’s only one frontier and running the entire automaton to push it forward by one cell is inefficient, even for a GPU.

The way a maze is generated plays a large role in how quickly the cellular automaton can solve it. A common maze generation algorithm is a random depth-first search (DFS). The entire maze starts out entirely walled in and the algorithm wanders around at random plowing down walls, but never breaking into open space. When it comes to a dead end, it unwinds looking for new walls to knock down. This methods tends towards long, winding paths with a low branching factor.

The mazes you see in the demo are Kruskal’s algorithm mazes. Walls are knocked out at random anywhere in the maze, without breaking the perfect maze rule. It has a much higher branching factor and makes for a much more interesting demo.

Skipping the Route Step

On my computers, with a 1023x1023 Kruskal maze it’s about an order of magnitude slower (see update below) than A* (rot.js’s version) for the same maze. Not very impressive! I believe this gap will close with time, as GPUs become parallel faster than CPUs get faster. However, there’s something important to consider: it’s not only solving the shortest path between source and goal, it’s finding the shortest path between the source and any other point. At its core it’s a breadth-first grid search.

Update: One day after writing this article I realized that glReadPixels was causing a gigantic bottlebeck. By only checking for the end conditions once every 500 iterations, this method is now equally fast as A* on modern graphics cards, despite taking up to an extra 499 iterations. In just a few more years, this technique should be faster than A*.

Really, there’s little use in ROUTE step. It’s a poor fit for the GPU. It has no use in any real application. I’m using it here mainly for demonstration purposes. If dropped, the cellular automaton would become 6 states: OPEN, WALL, and four flavors of FLOW. Seed the source point with a FLOW cell (arbitrary direction) and run the automaton until all of the OPEN cells are gone.

Detecting End State

The ROUTE cells do have a useful purpose, though. How do we know when we’re done? We can poll the BEGIN cell to check for when it becomes a ROUTE cell. Then we know we’ve found the solution. This doesn’t necessarily mean all of the FLOW cells have finished propagating, though, especially in the case of a DFS-maze.

In a CPU-based solution, I’d keep a counter and increment it every time an OPEN cell changes state. The the counter doesn’t change after an iteration, I’m done. OpenGL 4.2 introduces an atomic counter that could serve this role, but this isn’t available in OpenGL ES / WebGL. The only thing left to do is use glReadPixels to pull down the entire thing and check for end state on the CPU.

The original 2-state automaton above also suffers from this problem.

Encoding Cell State

Cells are stored per pixel in a GPU texture. I spent quite some time trying to brainstorm a clever way to encode the twelve cell states into a vec4 color. Perhaps there’s some way to exploit blending to update cell states, or make use of some other kind of built-in pixel math. I couldn’t think of anything better than a straight-forward encoding of 0 to 11 into a single color channel (red in my case).

int state(vec2 offset) {
    vec2 coord = (gl_FragCoord.xy + offset) / scale;
    vec4 color = texture2D(maze, coord);
    return int(color.r * 11.0 + 0.5);

This leaves three untouched channels for other useful information. I experimented (uncommitted) with writing distance in the green channel. When an OPEN cell becomes a FLOW cell, it adds 1 to its adjacent FLOW cell distance. I imagine this could be really useful in a real application: put your map on the GPU, run the cellular automaton a sufficient number of times, pull the map back off (glReadPixels), and for every point you know both the path and total distance to the source point.


As mentioned above, I ran the GPU maze-solver against A* to test its performance. I didn’t yet try running it against Dijkstra’s algorithm on a CPU over the entire grid (one source, many destinations). If I had to guess, I’d bet the GPU would come out on top for grids with a high branching factor (open spaces, etc.) so that its parallelism is most effectively exploited, but Dijkstra’s algorithm would win in all other cases.

Overall this is more of a proof of concept than a practical application. It’s proof that we can trick OpenGL into solving mazes for us!

Markov Chain Text Generation urn:uuid:3f808165-be65-3f4b-f485-8df6aacccd04 2012-09-05T00:00:00Z You may have been confused by yesterday’s nonsense post. That’s because it was generated by a few Elisp Markov chain functions. It was fed my entire blog and used to generate a ~1500 word post. I tidied up a bit to make sure the markup was valid and parenthesis were balanced, but that’s about it.

The algorithm is really simple and I was quite surprised by the quality of the output. After feeding it Great Expectations and A Princess of Mars (easily obtainable from Project Gutenberg) I had a good laugh at some of the output. Some choice quotes,

He wiped himself again, as if he didn’t marry her by hand.

I admit having done so, and the summer afternoon toned down into the house.

My favorite of yesterday’s post was this one,

Suppose you want to read a great story, I recommend it.

The output also looks like some types of spam, so this may be how some spammers generate content in order to get around spam filters.

To build a Markov chain from input, the program looks at markov-text-state-size words (default 3) and makes note of what word follows. Then it slides the window forward one word and repeats. To generate text, the last markov-text-state-size words outputted is the state and the next word is selected from these notes at random, weighted by the frequency of its appearance in the input text. Smaller state sizes generates more random output and larger state sizes generates better structured output. Too large and the output is the input verbatim.

For example, given this sentence and a state size of two words,

Quickly, he ran and he ran until he couldn’t.

The produced chain looks like this in alist form,

((("Quickly," "he") "ran")
 (("he" "ran") "and" "until")
 (("ran" "and") "he")
 (("and" "he") "ran")
 (("ran" "until") "he")
 (("until" "he") "couldn't.")
 (("he" "couldn't.")))

Because there are two options for (“he” “ran”), the generator might loop around that state for awhile like so,

Quickly, he ran and he ran and he ran and he ran until he couldn’t.

Or it might skip the section altogether,

Quickly, he ran until he couldn’t.

Also notice that the punctuation is part of the word. This makes the output more natural, automatically forming sentences. More so, my program also holds onto all newlines. This breaks the output into nice paragraphs without any extra effort. Since I wrote it in Elisp, I use fill-paragraph to properly wrap the paragraphs as I generate them, so superfluous single newlines don’t hurt anything.

One problem I did run into with my input text was quotes. I was using novels so there is a lot of quoted text (character dialog). The generated text tends to balance quotes poorly. My solution for the moment is to strip these out along with spaces when forming words. That’s still not ideal.

I’m going to play with this a bit more, using it as a tool for other project ideas (ERC bot, etc.). I already did this by including a lorem ipsum generator alongside the markov-text package. The input text is Cicero’s De finibus bonorum et malorum, the original source of lorem ipsum. This was actually the original inspiration for this project, after I saw lorem-ipsum.el on EmacsWiki and decided I could do better.

Implemented Is Simple Data Compression urn:uuid:2dd8265c-e498-333f-7f07-4fd93d873975 2012-09-04T00:00:00Z Update: This post shouldn’t make sense to anyone (hopefully). Read the follow-up for an explanation.

When a branch of my posts remains simple.

This is necessary when one will assume Alan is more important than number 12. By using numbers to repeat them, but this won’t work with any sort of thing you want to load what’s needed. This includes reimplementing the reader as it seems you still need to specify any video-specific parameters, ppmtoy4m is the whole thing is just that, decorated with some tips on how the current space as visited, then recurse from the client to read a great story, I recommend you use to launch a daemon process and prints the variable information to stdout. As an added bonus, when a second variable for accumulation and a second argument is relevant.


This servlet uses the Term::ProgressBar, if it’s any good, but it’s funny. As anyone with cats knows, it’s not too stupid to call fsync() to force the write to the snapshot and uninterns any new symbols. These symbols will be added to the the second experiment.

At this line, you can perform a number from a couple of these and give them back any other language that can turn out even from a large header comment in the logs, so getting someone into my honeypot wouldn’t take long at all. The only proof I could then cherry-pick/pull the issues from that repository and see the polynomial interpolation at that time, presented in order. This makes so much of web development (I think that’s his name). I am an Emacs person myself, which I use branches all the time, now that they can be written.

We will run your build system in a web front-end to it, and made a couple of seconds.

You should also be a good head start, though. The SPARC is big-endian and the results to seed their program accordingly. You could do this is by mounting the compromised filesystem in a list. In the decentralized model, everyone has their own solutions in parallel when it comes across 10 it emits 0.

Here’s an example of some of the fire gem activated and exploded, causing no blindness to me. They take a look at the same level as the printed string. You can grab my source code in response to abuse by spammers who hide fraudulent URLs behind shortened ones. If these services ever went down all at once, these shortened URLs would rot, destroying many of the image, with the FFI.

Because I wrote a shell script that will also remove the execs and live with nested shells because the zeros cancel out everything else? Here is the protocol.

Generate a 10-byte random IV. This need not implement this.

Note that the shell script, and the arcfour key scheduler at least n days.

However, generating a series of commits to all other encounters nothing changes.

Your program should simulate this by having the user to reseed somewhere. There’s no direct way to install it to dominate for awhile. It is strange that Matlab itself doesn’t have any sort of syntax highlighting. Boring! I finally ran into this image. After each paste, make a saving throw to prevent an explosion.

Because Gnohkk would also suffer from the bottom are arranged around the cats in the logs, so getting someone into my honeypot wouldn’t take long at the link in the block. Another was going to used a stationary magnet.

Our team went with this array (and replaced the current layer 5). Now, duplicate the work was done just once by freeing the entire number, it can perform both compression and decompression on both sides don’t pay attention to the development loop is just an ordered list of 50 H’s and T’s. If you implement this in the same time. This is along the way, clone my repository right into the official website so I had to do this for any long-blocking function that I use ppmtoy4m to pipe the new frames to keep, such as n^p mod M, which this will handle efficiently. For example, to add a new compression algorithm in terms of brute-force attacks it requires using numbers long enough to fit three Emacs’ windows side-by-side at 78 columns each. The leftmost one contains my active work buffer where I do most useful things, a fresh array every time it sees a free musical. Unfortunately, my writing skills are even worse. I have gotten good mileage out of a file based on their website demonstrating how to increment the iterator. I have to type a negative comment about zip archives and moved on. I am using a constant amount of memory.

It turns out that everyone is free to share his source code samples, particularly more recent entries, was that producing the relief surface was an e-mail address, I get home from work I don’t recommend doing this with secret Java applets.

There are a few weeks since I last used KOffice, so I could easily plug it into Emacs and run the test above, I would rather not do damage, but rather a patient human being. Getting tired of manually synchronizing them. It was finally time to document the effort as a single mine is destroyed, the neighboring mines will replicate a replacement. The minefield itself could therefore hold no secrets whatsoever. This leaves out any possibility of a rumor among a group of people. At any given time, each person in the background. My shell habits looked like the ones you’re seeing after end-package.

It’s really simple way to detect edges all over the weekend I came up with some rough edges. So I got it right while IE, Opera, Safari, and Chrome all do it again.

Numbers can be found inside the fake closure provided by lexical-let. In a previous post about Lua, another about a third of my name generation code.

S-expressions are handy anywhere.

Two months ago I was so happy when I run the program with the proper Perl regular expression contains quotes and these will not be worth it.

I can’t help but think that a knight moving according to the current symbol table to the existing mountain of elisp code out there, requiring a massive increase in speed when using OpenCL. In fact, there is virtually no computation involved. So what I want to look like SBCL. Fortunately, that’s not all!!! There is a fake service or computer on a chess board such that it’s somewhat easier to tell when the handler can present any contents it wants. In this case, rather than just one, even though I don’t know what it looks good, except you want to italicize a few bits smaller than a minute. All the other day I will probably be ordered by their own directory. Modern applications have moved into a directory under ~/.config/. Your script needs to be broken into small computation units, because Emacs lacked network functionality until recently was the package manager, package, and the Emacs Lisp Package Archive.

One of the info field in the list, which sounds like a .emacs file in your program. If the slot is already taken, the symbol was in an external system.

After all this, I thought I’d give it a YouTube URL and a single password if the required artifacts, digitally signs them, and bundles them up.

The demo at the same length as the variable declarations are exactly the right magical string of, say, 31 fractions.

The story is really happening. Optimizing away variables that point to it.

Oh, and I was just a tiny subset of the memory at once became a lot of memory. For example, here’s my laptop’s /bin/ls, very roughly labeled.

The different segments of the game area was a mistake on my rolls and had some wires, connected to some sort of bad things this may happen subconsciously, which is given in ImageMagick’s montage tool, which made the final montage out of the image functions described below.

You can write a lexer or tokenizer without one. Because of this tool, Samuel Stoddard, gives some in-game context to the light of day. I just use your own program, the script in your load-path somewhere.

I’ve frequently thought that a Lisp-based shell would be produced by first individually gzipping each file in first.

For a long ways away from a simple double-click shortcut. If you just want to duplicate the remaining canines. Her reward for victory was a very similar process, but without any sort of thing is transparent. I’ve already used it with a degree in, say, a few months. I’ve used POSIX threads, Pthreads, before, so it suits my needs for the first two arguments from filter2, as well as some more to see my changes, but I don’t know much about it, user AJR spoiled it with ssh-add and it queries for your passphrase, storing it in two obarrays at once, these shortened URLs would rot, destroying many of its input. For example, this is what registration looks like,

Unfortunately, the HTML output is a Harsh Mistress. If you know that the opposite way that the adventures and characters are riddled with mistakes and very unbalanced. For an easier way to set up properly in your configuration.

I strongly recommend that you generally want to have a master pad, K, that you often generate very improbable series of commits.

To all other encounters nothing changes.

And that’s it! I put this line in your program. If you are subscribed to the rescue!

Traveling Salesman Problem by Genetic Algorithm urn:uuid:2a90302c-08f3-3b32-d41d-7d41d26cd9fc 2007-11-30T00:00:00Z
  • /download/genetic.tar.gz (6.19KB)
  • Here is another project for my artificial intelligence class. I wrote a generic genetic algorithm class in C++ and then applied that class to the traveling salesman problem. A genetic algorithm more tuned to the traveling salesman problem would work better.

    This particular implementation can use up to 16 points defined in the weight matrix stored in travel.dat. This weight matrix can either be defined by hand or generated using gendat.m from a list of points stored in points.txt. A chromosome is 64 bits wide, which is 16 points with 4 bits each. To make sure that every possible chromosome is a valid solution, the points are selected out of a circular queue. Every 4 bits describes how far along the queue to walk before pulling out a point. With the circular queue, the chromosome could be as short as 50 bits, but I was trying different things and 64 bits is the simplest way to represent a solution. Here are some sample chromosomes:

    1101100010100000011001010101010111000110101100111111000010111010, 9315
    0000110100000001000010010101010111011000101100010110000010111010, 9339
    1010001100010001010010011001010010100000101100011111000010111110, 9410
    0101001000000011010010011001010011010100101011100111000111011110, 9355
    0101001001000000010110100001010011010110101101000001000101000110, 9349
    0101011100010011000010011011011011010101101100011111010010111110, 9311
    0000111101000001000010011001010010110100101100011111100010000010, 9350
    1000001111100000010110101011011011100000111101010111000010111010, 9428
    0000111011000001000010010111011111111110101100010111000001000111, 9448

    The second number is the fitness value of the chromosome (10000 - path length). Below is a path found after 20000 iterations:

    It takes many iterations to find a reasonable solution and it never finds a really good solution. This is because each node in the chromosome depends on every single node before it. This is terrible for a genetic algorithm, but it’s really the best I could think of when using a generic genetic algorithm class like this.

    A much better method would have the genetic algorithm actually know about the problem at hand, working with nodes rather than bits. Breeding would make cuts on nodes. Mutations would swap single nodes. Perhaps this can be written another time.

    Neural Network Blackjack Game urn:uuid:d9bb1ed9-9d44-3747-6f94-a580912e68e5 2007-11-13T00:00:00Z Get the source code (C++):

    This is a neural network I wrote for an artificial intelligence class I took about a year ago. It includes a stand alone neural network class you can easily use in your own C++ program. Built around this neural network is a simple version of Blackjack (hit or stand only). You can play the neural network at Blackjack after it has finished training, which can take up to a minute or so.

    My implementation of the neural network is a really simple one, using only back propagation, but it still has some neat surprises in it. When I was working with it, I would use a simple GNU Octave script to watch what was going on in real time.

    The x-axis is the number of iterations in tens of thousands and the y-axis describes how often the neural network plays exactly the same way a cheater would at the same seat. A cheater is defined as someone who knows what card is next and can play perfectly. Note: the neural network itself is not cheating. At the end, it agrees with the cheater about 83% of the time. This is the script that reads the neural network output. For those who don’t recognize the she-bang, save this to the file plotdat and set the execution permission (chmod +x plotdat).

    #!/usr/bin/octave -qf
    # Usage:
    # plotdat filename [loop] [last index]
    dat = dlmread(argv{1});
    x = length(dat);
    loop = 0;
    if (length(argv) > 1)
      if (argv{2} == 'loop')
        loop = 1;
        x = argv{2};
      dat = dlmread(argv{1});

    When you run the program, a blank, dumb neural network is created. It doesn’t know how to play blackjack. In fact, just as it seems with my sister at times, it doesn’t know how to do anything at all. It’s like a newborn baby, but without any instincts. To make this neural network useful, it is taught to play blackjack by running it very quickly through about one million games, all tutored by a teacher who gets to cheat by looking ahead in the deck. This allows the teacher to always know the proper move.

    The training works by giving the network an input and the desired output (determined by the cheating). The network adjusts its internal weights depending on the error between what its current output for the input and the desired output. In doing this, the neural network picks up on the statistical nature of its inputs and will pick up on patterns.

    When setting up the neural network in your own program, the tricky part is determining how to encode the inputs so that patterns will be found. In this case, I provide 3 integers to the network: its lower bound score, its best score, and the visible opponent score. By lower bound and best score, I am talking about Aces. All aces are treated as 1’s in the lower bound and ideal (highest without bust) values in the best score. Scores never exceed 31, so we can encode this in 5 bits each for a total of 15 bits. We only need 1 output bit: hit (0) or stand (1). The network looks something like this, but with 30 hidden layer neurons and a lot more connections.

    Here is an example run of the blackjack game,

    Creating network ... created!
    Training ...
    Win, lose, total, c%, win%: 1536, 7640, 10000, 42.1168% , 15.36%
    Win, lose, total, c%, win%: 3728, 14438, 20000, 55.8875% , 21.92%
    ... (lots of output for a few seconds) ...
    Win, lose, total, c%, win%: 203744, 700338, 980000, 82.0455% , 20.3%
    Win, lose, total, c%, win%: 205849, 707461, 990000, 82.5488% , 21.05%
    Win, lose, total, c%, win%: 207981, 714515, 1000000, 82.3059% , 21.32%
    Begin game:
    Computer is dealt: (hole) 5
    Computer is dealt: (hole) 5 4
    Computer stands.
    Your hand: 2 8
    Hit? (y/n): y
    Your hand: 2 8 3
    Hit? (y/n): y
    Your hand: 2 8 3 10
    You bust with 23
    Computer wins with 19 against your 23
    Play again? (y/n) : y
    Begin game:
    Computer is dealt: (hole) 4
    Computer is dealt: (hole) 4 10
    Computer stands.
    Your hand: 10 A
    Hit? (y/n): n
    Your hand: 10 A
    You win with 21 against computer's 20
    Play again? (y/n) : n
    Computer wins, losses, push: 1 (50%), 1 (50%), 0 (0%)

    If you decide to try using the neural network in your own program, be sure to play with different sized networks to see what works best. In my implementation, a small network would be 1 layer with 3 nodes and a large network would be 3 or 4 layers with hundreds of nodes. Bigger networks may not work well at all, and there is no way to know what size is best other than trial and error.

    Iterated Prisoner's Dilemma urn:uuid:4068d624-311a-30f4-a291-63713ffbc932 2007-11-06T00:00:00Z

    I was reading about the prisoner’s dilemma game the other day and was inspired to simulate it myself. It would also be a good project to start learning Common Lisp. All of the source code is available in its original source file here:

    I have only tried this code in my favorite Common Lisp implementation, CLISP, as well CMUCL.

    In prisoner’s dilemma, two players acting as prisoners are given the option of cooperating with or betraying (defecting) the other player. Each player’s decision along with his opponents decision determines the length of his prison sentence. It is bad news for the cooperating player when the other player is defecting.

    Prisoner’s dilemma becomes more interesting in the iterated version of the game, where the same two players play repeatedly. This allows players to “punish” each other for uncooperative play. Scoring generally works as so (higher is better),

    Player A
    Player Bcoop (3,3)(0,5)

    The most famous, and strongest individual strategy, is tit-for-tat. This player begins by playing cooperatively, then does whatever the its opponent did last. Here is the Common Lisp code to run a tit-for-tat strategy,

    (defun tit-for-tat ()
      (lambda (x)
        (if (null x) :coop x)))

    If you are unfamiliar with Common Lisp, the lambda part is returning an anonymous function that actually plays the tit-for-tat strategy. The tit-for-tat function generates a tit-for-tat player along with its own closure. The argument to the anonymous function supplies the opponent’s last move, which is one of the symbols :coop or :defect. In the case of the first move, nil is passed. These are some really simple strategies that ignore their arguments,

    (defun rand-play ()
      (lambda (x)
        (declare (ignore x))
        (if (> (random 2) 0) :coop :defect)))
    (defun switcher-coop ()
      (let ((last :coop))
        (lambda (x)
          (declare (ignore x))
          (if (eq last :coop)
              (setf last :defect)
              (setf last :coop)))))
    (defun switcher-defect ()
      (let ((last :defect))
        (lambda (x)
          (declare (ignore x))
          (if (eq last :coop)
              (setf last :defect)
              (setf last :coop)))))
    (defun always-coop ()
      (lambda (x)
        (declare (ignore x))
    (defun always-defect ()
      (lambda (x)
        (declare (ignore x))

    Patrick Grim did an interesting study about ten years ago on iterated prisoner’s dilemma involving competing strategies in a 2-dimensional area: Undecidability in the Spatialized Prisoner’s Dilemma: Some Philosophical Implications. It is very interesting, but I really wanted to play around with some different configurations myself. So what I did was extend my iterated prisoner’s dilemma engine above to run over a 2-dimensional grid.

    Grim’s idea was this: place different strategies in a 2-dimensional grid. Each strategy competes against its immediate neighbors. (The paper doesn’t specify which kind of neighbor, 4-connected or 8-connected, so I went with 4-connected.) The sum of these competitions are added up to make that cell’s final score. After scoring, each cell takes on the strategy of its highest neighbor, if any of its neighbors have a higher score than itself. Repeat.

    The paper showed some interesting results, where the tit-for-tat strategy would sometimes dominate, and, in other cases, be quickly wiped out, depending on starting conditions. Here was my first real test of my simulation. Three strategies were placed randomly in a 50x50 grid: tit-for-tat, always-cooperate, and always-defect. This is the first twenty iterations. It stabilizes after 16 iterations.

    (run-random-matrix 50 100 20 '(tit-for-tat always-coop always-defect))

    White is always-cooperate, black is always-defect, and cyan is tit-for-tat. Notice how the always-defect quickly exploits the always-cooperate and dominates the first few iterations. However, as the always-cooperate resource becomes exhausted, the tit-for-tat cooperative strategy works together with itself, as well as the remaining always-cooperate, to eliminate the always-defect invaders, who have no one left to exploit. In the end, a few always-defect cells are left in equilibrium, feeding off of always-cooperate neighbors, who themselves have enough cooperating neighbors to hold their ground.

    The effect can be seen more easily here. Around the outside is tit-for-tat, in the middle is always-cooperate, and a single always-defect cell is placed in the middle.

    (run-matrix (create-three-box) 100 30)

    The asymmetric pattern is due to the way that ties are broken.

    The lisp code only spits out text, which isn’t very easy to follow whats going on. To generate these gifs, I first used this Octave script to convert the text into images. Just dump the lisp output to a text file and remove the hash table dump at the end. Then run this script on that file:

    The text file input should look like this:

    You will need Octave-Forge.

    The script will make PNGs. You can either change the script to make GIFs (didn’t try this myself), or use something like ImageMagick to convert the images afterward. Then, you compile frames into the animated GIF using Gifsicle.

    See if you can come up with some different strategies and make some special patterns for them. You may be able to observe some interesting interactions. The image at the beginning of the article uses all of the listed strategies in a random matrix.

    I will continue to try out some more to see if I can find something particularly interesting.

    Chess AI Idea urn:uuid:2e66347a-fe5d-3b70-58ea-9a9e9bd6248a 2007-10-24T00:00:00Z So, I had this idea using a genetic algorithm to optimize the parameters of a program that plays chess. Now, the genetic algorithm wouldn’t be used at all during a game, but rather to optimize the board evaluation parameters beforehand. I don’t know much about writing board game AI programs, as I have only written a few of them for fun (tic-tac-toe, connect 4, Pente). For this chess program, I am taking a simple approach because I am more interested in seeing the genetic algorithm at work than seeing the chess playing AI do well against other chess AI or people.

    The program would search the game tree using the minimax algorithm, with some possible optimizations added afterward. Tree searching is just a matter of generating all possible moves and looking at them. The hard part is the board evaluation function, which evaluates the a particular board’s score based on the arrangement of the pieces. Parameters to this evaluation function would be, for example, the piece values. The pawn would be locked in at a value of 1, which anchors the other values and provides a base unit to work from.

    Again, the parameters would not change during a game. We use the genetic algorithm ahead of time to determine the parameters.

    For the genetic algorithm, the set of parameters strung together makes up a single chromosome. We maintain a pool of different chromosomes, i.e. different sets of parameters, and breed these chromosomes together to improve our parameter sets. We start out with a random pool made of parameters that are most likely pretty terrible.

    To evaluate the chromosomes, we need a fitness function, which evaluates each chromosome for its level of “fitness” deciding if it breeds or not. To do this we simply play the chromosome we are evaluating against some base chromosome, which may just be parameters chosen intuitively by the programmer. Or, the base chromosome could be random too. Starting with a better base chromosome would be a good head start, though. The fitness of the chromosome is how often it wins against the base chromosome in, say, a few hundred games.

    The most fit chromosomes are bred by taking a few parameters from each to make a new chromosome. Mutations are occasionally added in order to keep the chromosome pool from getting stuck in a local maximum. A mutation involves changing one or more parameters in a chromosome slightly in some random way. Mutations are rare and will usually be detrimental to the chromosome quickly killing it off, but will occasionally cause a good change that will be spread to other chromosomes in the next generation, improving the gene pool.

    We iterate this until either the maximum fitness level in the pool is stuck for several iterations (we aren’t getting anywhere and mutations aren’t helping), or the chromosomes are so good they always beat the base chromosome, making the fitness algorithm meaningless. When this happens, we replace the base chromosome with the best chromosome in the pool and start over from scratch again with a random, or mostly random, pool.

    As you would expect, I have looked into parallelizing this process to take advantage of a cluster. This is easy for several reasons. First, evaluating chromosomes can be done simultaneously. No evaluation depends on another chromosome’s evaluation. Second, the minimax game tree search can be parallelized so that several different processes search the game tree and give their results back to the parent process. This works very well because the data being sent back to the parent will be a single integer. No need to send large amounts of data around the network.

    I spent an afternoon hacking at this, but its still too crude to share yet. I got the non-parallel version of the chess engine built but I am still working on the evaluation function. The genetic algorithm hasn’t been started. The only parameters at the moment are piece values. The board evaluation function just adds up the piece values on the board completely ignoring their positions. This makes the computer play extremely aggressively, capturing the opponent’s pieces whenever it can. This makes for a somewhat interesting bloodbath where the board goes empty after just a few moves.

    My problem right now is finding a good way to represent piece movements so that it can be recycled. That is, I want to represent movements when generating my search tree, verifying the legality of a move, and evaluating the board all the same way so that I don’t have to program in piece movements several times.