UCT Charts

Today’s topic is a little different: it’s as much an art project as it is engineering or science. Pretty graphs below, but first, an introduction.

UCT is messy by computational standards. It wends its way towards perfect play, but the answers you get depend on how long you waited before asking and how fast the hardware was running, not to mention a stream of pseudo-random numbers. An antivirus program running in the background, a network blip on another continent, bubbles in your CPU’s thermal paste – they can all affect what a general game player ends up returning as its move.

So what happens if we take some of that messiness away?

2016 Tiltyard Open format

It's time to reveal the types of matches at this year's Tiltyard Open tournament. A few things have changed from last year, so use this as your guide to what's ahead.

Alloy 0.10.0 graphical log streaming is live

You can now get some insight into what Alloy is thinking by watching a live graphical representation of its logs as it plays on Tiltyard.

I decided to do this primarily as a way to better understand my player and UCT. I had moved Alloy to run on a dedicated computer so it can run continuously, but this made it difficult to view information directly from the program. Streaming this publicly makes it easier to see regardless of where I am, and it also allows others to watch this information and gather their own insights about game AI.

By moving from a few lines of logging at a time to a full screen of graphical information, I can also afford to include a wider array of information useful for debugging or for understanding my player's weaknesses.

The GDL engine performance-testing framework

The Game Description Language is declarative, not imperative. It defines the rules of a game, but not the process by which a program should apply those rules to produce facts. This has led to a wide variety of implementations of GDL interpreters, or engines, that handle this computation, with a wide range in their speed and accuracy across games.

A paper presented at the GIGA'13 conference by Yngvi Björnsson and Stephan Schiffel compared the performance of six such engines on 12 games. (To access the paper, select "proceedings" on the conference website and scroll to page 55.) To follow up on this experiment, and to test my own creations, I decided to write an open-source framework for this type of performance testing.

2015 Tiltyard Open format

Here's a somewhat more in-depth explanation of the sets of matches that will be played in the 2015 Tiltyard Open. Hopefully this will help make sense of the overall tournament structure and how match results affect the final results.

We expect to use version 0.0.7 of the ggp-tournament library for scheduling the matches, so you can check out that library for details beyond the explanations here.

Bases and inputs

I don't know if there are any clear full descriptions of how base and input sentences work in GDL. (They were added to GDL since the last full specification was written.) So, here's a brief write-up of how they work.

The base and input keywords are used to specify the possible true sentences (i.e., components of the game state) and legal moves that could occur over the course of the game.

GDL perf framework preview

I've been working on and off on a performance-testing framework for interpreters of GDL games (i.e. rule engines). There's still more work to be done before it's sufficiently complete and well-documented for others to use, but here's a sneak peek of output. Suggestions are welcome on the Github issues page.

RuleEngine interface

I've mostly been forgoing work on the current version of Alloy in favor of a newer, better-factored framework with better logging support. Partly I'm working to support a new interface to replace StateMachine.

Amazons and Efficient Recursion

I recently rewrote Amazons to make it more efficient, and thus more attractive as a GGP game. I've also been doing some unrelated work on a compiled prover rules engine, which is much faster than the ProverStateMachine GGP-Base. In the process, I've had some ideas about how to deal with recursion efficiently in provers, which could have implications for many other important games.

Griddle: a GDL editor for Eclipse

Griddle is an Eclipse plugin that provides a specialized GDL editor for game files. The editor makes it easier to write new games while avoiding typos and syntax errors.

Implication deduction: Logic over propnets

Today I'd like to share a simple and surprisingly useful algorithm for making logical inferences about games using propositional networks.

I developed this as part of the implementation for a more specific feature (one of the applications listed below). Although it was developed in the context of a larger feature, I wrote the code for this step to stand alone, and it has proved useful in quickly writing other features that involve understanding games more deeply.

The question that it answers is simple: given a set of components that we know to be true or false in a propnet, which other components are also guaranteed to be true or false? I call this implication deduction.

Rewriting chess (again)

One of the embarrassing questions about GGP: "So, how good are they at chess?"

Not very good. Not very good at all.

There are several reasons for this.

Sancho gets a blog

Steve Draper and Andrew Rose have put together a blog describing their work on their (very good) general game player, Sancho. Sancho is the successor to Quixote, the winner of the first MOOC iteration of Stanford's General Game Playing class.

I fully expect their blog will update more frequently than mine.

The Annotated Tic-Tac-Toe

Tic-tac-toe is a classic and widely-understood game. Introductions to GDL typically use it as a sample "first game", as the rules are fairly simple and usually already known by the reader. However, the GDL representation can still be foreign enough to be difficult to understand. This post is my attempt to flesh it out with explanations of what each component of the rules is doing. This isn't my first attempt at an introduction to GDL, but different people will find different approaches better.

The General Game Playing Forum

Just a short note and link: There is now a long-term forum for discussion of General Game Playing, born from the discussions out of the GGP Coursera course last fall. (Speaking of which, a new session is starting right now.)

Improving Chinese checkers performance

This is another post on improving the performance of game simulations by modifying the GDL by hand. Today, we look at chineseCheckers4, a game known for its particularly poor performance, especially for propnets.

Arithmetic in GDL

As a rather minimalist language, GDL doesn't have any native support for arithmetic. This hasn't stopped games from making use of arithmetic as needed.

The Dresden server, plus rewriting Othello

I recently found that the Dresden server is up and capable of hosting round-robin matches again. (It doesn't have a hostname at the moment, and I don't want to link directly to an IP address, so reach it via the first link on this page.)

The Dresden server is different from Tiltyard in that it has a wider variety of games, somewhat less curated than Tiltyard's selection in terms of the GDL and ease of processing the game descriptions. Unlike Tiltyard, Dresden will have gamers play pretty much every game it has.

Rewriting checkers

I had a suspicion a while back that some GDL games were poorly written in terms of performance, and could be improved upon. Recently, I was looking over the checkers rules and decided they would be a good test case for this treatment.

A quick guide to GDL terminology

I'm writing another post which is pretty heavy on the GDL terminology. I may not have the time to make every such post readable for someone who doesn't know a sentence from a term. Hopefully, this will also be of use to anyone trying to sort out the Gdl classes in GGP-Base.