My attempt at a Conquest AI

Before I move on, let me introduce Conquest – a chesslike minigame in Runescape. This isn’t a detailed description of the rules, just an overview to kind of get to know how the game works, if you haven’t seen it before.

You have a 20×20 board and some pieces (which you choose yourself and get to set up wherever you want, with some restrictions). You’re trying to kill all of your opponent’s pieces, which you have to do in order to win.

Each piece has a certain move radius — so it can move to any square within that radius (diagonals only counting as a distance of one). Then, once it has moved, it is allowed to attack an enemy within its range — again varying from piece to piece.

That’s the gist of the game. Oh yes, at certain times you can also use some silly special attacks in addition to moving and attacking — for instance, freeze an enemy piece for one move or temporarily boost the attack of one of your own pieces. And these special moves can be used on any pieces during your move, and in any combination.

A Conquest AI… or not

So some months ago, I was playing Conquest. I was a decent player, but after a string of losses, I thought: maybe I can write an AI to play this game for me — perhaps better than a human can? Perhaps the same way you would write a chess AI?

Well, I scribbled some back of the envelope calculations, but I quickly realized that the number of possible moves at each position was far too large.

How large? A player has maybe 5 pieces, and if a piece’s average move radius is 4, then we already have 5*9*9 (remember 4 is the radius, not diameter) which is over 400. And that’s if we never attack or use special moves. If we take special moves into account, since special moves can be stacked on top of each other, assuming 5 valid targets per special move and 3 special moves we would multiply the 400 again by 5*5*5. For one move, we would need to consider 50000 possibilities.

In comparison, from any position in chess there are typically 30 or 40 legal moves. So the standard minimax algorithm would probably be no good, at least not without an incredible amount of heuristics. I had to try something different for this to work.

Random has a chance

It turns out that there exists a very different strategy that worked quite well for Go-playing AIs. Instead of constructing and evaluating a huge search tree to find the best move, we simulate thousands random games, with random moves from each side. The move that gives us the best win percentage is played. All else being equal, a position that gives you a 90% chance of winning given random play from that point on is usually better than one with only a 30% chance of winning.

Here’s a screenshot of a connect-4 AI using this technique:

The Monte Carlo approach, as that’s what it’s called, seems absurd — there’s no way playing random moves can beat a good minimax! Indeed, Monte Carlo is never used to play chess, and I could sometimes beat the above AI. But where Monte Carlo really shines is when standard minimax is impractical — my scenario.

After finding and reading a few papers describing the method in detail, I was ready to start coding. However, there is still one more catch: to make it practical to set up the AI against other players over Runescape (and where the time limit for each move is usually 30 seconds), I would have to find a way to integrate the back end — the part that does the computations — with a front end that relayed the moves back and forth to the Runescape game client.

All is not lost, however: there were several freely available hacked clients for botting purposes: Powerbot allowed for users to write java scripts that automated tedious ingame actions.

That was about as far as I got though, unfortunately. Coding the game logic proved trickier than expected. A month or so after I started my account was banned for botting; later, Jagex (the company behind the game) made an update that rendered Powerbot (as well as every other similar hacked client) unusable. Without a game account nor a practical front-end, I called it quits.

Solving the AB Game by Brute Force

The AB game, a variant of Mastermind, is played with pencil and paper and with two people. One person chooses a four digit number in which no digit is repeated, say X, and the other person tries to guess it in as few moves as possible. After the guesser guesses some number, say Y, the other person gives information on how closely Y matched with X:

• If some digit in Y coincides with a digit in X (in the same position), then the guesser scores an A.
• If some digit in Y exists in X but is in the wrong place, then the guesser scores a B.

For instance, if X is 1234 and we guess 2674, we get an A and a B, because the 4 is in the right place, and the 2 is one of the right numbers but isn’t in the right place.

This proceeds until the guesser gets the exact number.

When humans (or at least beginners) play the AB game, they usually do some form of uncoordinated trial and error, which gets the right answer after some large number of moves. This takes anywhere from about 8 to possibly 30 guesses. When I played this game with a friend, I didn’t have a very systematic strategy, but I wondered if a computer program could solve the game, always entering the optimal guess.

A Bruteforce Solver

My first approach happened to work fairly well. Simply, the computer keeps track of a list of all possible numbers that the answer can be. At random, the computer guesses one of the numbers, and upon receiving feedback, eliminates every number in its list that doesn’t match that feedback. Quickly it eliminates whole swaths of combinations and arrives at the answer.

A typical session might go like this:

Guess 1: 6297. Score: 5040
b
Guess 2: 8512. Score: 1440
abb
Guess 3: 2315. Score: 83
bb
Guess 4: 5842. Score: 29
bb
Guess 5: 9581. Score: 13
ab
Guess 6: 8021. Score: 1

It took only 5 guesses for the computer to narrow down the choices to the only possible answer (8021).

A variant that is usually much harder for humans to solve is to allow the number chosen to have repeats. Although significantly trickier for humans to guess by trial and error, brute force doesn’t seem to be affected too much by it:

Guess 1: 1796. Score: 10000
b
Guess 2: 5881. Score: 3048
a
Guess 3: 0131. Score: 531
abb
Guess 4: 3311. Score: 15
aa
Guess 5: 3201. Score: 9
abb
Guess 6: 2011. Score: 1

The computer’s average of five or six is much better than a human can normally do! (although I haven’t researched possible human algorithms).

Optimal or Not?

At this point you may begin to wonder if this strategy is the optimal one. Unfortunately, it is not — and I only need one counterexample to demonstrate that.

Suppose that instead of four numbers, you were allowed to choose 4 letters from A to Z. You choose the combination ABCW. Now suppose that the computer ‘knows’ that the first three letters are ABC — that is, it has eliminated all other combinations except for ABCD, ABCE, …, ABCZ.

By the random guessing algorithm, the computer is forced to guess ABCJ, ABCP, etc, until it eventually hits on ABCW at random. This may take a very high number of guesses.

A smarter strategy would be to guess combinations of four unknown letters, say DEFG, then HIJK, etc. Instead of eliminating one letter, you eliminate four letters at a time. Although some guesses have no chance of being correct, the number of guesses required is fewer in the long run.

Source Code

I’ll put my somewhat unwieldy java code here for all to see:

import java.util.*;

public class ABSolver{
  
  // Does cc1 and cc2 together match the pattern?
  // If repeats are allowed, cc2 is matched against cc1.
  static boolean fits(char[] cc1, char[] cc2, int A, int B){

    int a = 0;
    int b = 0;
    for(int i=0; i<4; i++){
      if(cc1[i] == cc2[i]) a++;
      else{
        for(int j=0; j<4; j++){
          if(i != j && cc1[j] == cc2[i] && cc1[j]!=cc2[j]){
            b++;
            break;
          }
        }
      }
    }

    return a==A && b==B;
  }

  public static void main(String[] args){
    
    Random rand = new Random();
    Scanner scan = new Scanner(System.in);

    // Combinations that haven't been eliminated yet
    List<char[]> ok = new ArrayList<char[]>(10000);

    // Generate all possible combinations
    for(int i = 0; i <= 9999; i++){
      
      String i_s = Integer.toString(i);
      while(i_s.length() != 4) i_s = "0" + i_s;

      // Check for sameness
      char a = i_s.charAt(0);
      char b = i_s.charAt(1);
      char c = i_s.charAt(2);
      char d = i_s.charAt(3);
      boolean same = a==b || a==c || a==d || b==c || b==d || c==d;

      // Comment this line out if we're allowing repeats
      if(same) continue;

      char[] i_ia = i_s.toCharArray();
      ok.add(i_ia);

    }

    // Pick the first guess randomly
    char[] firstg = ok.get(rand.nextInt(ok.size()));
    char[] guess = null;

    int nguesses = 1;

    // Question answer cycle until we get it right
    while(true){

      // Ask for user response
      if(nguesses > 1){
        String ans = scan.nextLine();
        int A = 0;
        int B = 0;
        for(char cc : ans.toCharArray()){
          if(cc == 'a') A++;
          if(cc == 'b') B++;
        }

        if(A==4) return;

        // For each one check to see if it still fits
        List<char[]> ok_ = new ArrayList<char[]>(ok.size());
        for(char[] zhe : ok){
          if(fits(zhe, guess, A, B))
            ok_.add(zhe);
        }
        ok = ok_;
      }

      char[] nextguess = null;
      if(nguesses == 1)
        nextguess = firstg;
      else nextguess = ok.get(rand.nextInt(ok.size()));

      System.out.println("Guess " + nguesses + ": " + new String(nextguess)
                       + ". Score: " + ok.size());
      
      // we win!
      if(ok.size() == 1)
        return;

      guess = nextguess;
      nguesses++;
    }
    
  }
}

Calculating the Plane Angles of Platonic Solids

What is the angle between two planes of a tetrahedron?

The angle between any two edges of the tetrahedron is , so it’s easy to (falsely) conclude that the angle between two faces must also be .

But this isn’t the case: the plane angle is defined as the angle between two lines on the two planes that are both perpendicular to the edge. None of the edges in a tetrahedron is perpendicular to any other, so the answer of is invalid.

We can try to compute the angle using regular Euclidean solid geometry, but things tend to get messy. A different way to approach the problem is by using vector geometry: using vector methods we can easily calculate the plane angle of the tetrahedron (as well as the icosahedron and the dodecahedron).

Assume symmetry. We represent three concurrent edges of the polyhedron as three vectors beginning at the same point: , , and ; let and be the angles between the vectors (by symmetry we’re assuming that the two alpha’s are equal):
(in case my poor drawing skills does not make this apparent, vectors a and b form one face of the polyhedron and c and b form another face)

For simplicity, let’s also say the lengths of each of the three vectors is 1.

We want to compute the angle between the plane formed by and , and the plane formed by and . Hence let and be the perpendiculars to and respectively each ending at the same point as their respective vectors:

For any two vectors, the dot product is defined with being the angle between the vectors. Given that the lengths of the vectors are all 1, we have:

Also, by vector addition:

Hence and .

We want to find the angle between and — call this angle . Then

The dot product of vectors x and y is simply:

Additionally . Hence the cosine of the angle is:

We can now use this newly derived formula to calculate plane angles! For example…

Tetrahedron

In the tetrahedron, both and are 60:
So  and .

Icosahedron

In the icosahedron, but :
The top ‘cap’ is a regular pentagon, which has a vertex angle of 108; each side of the pentagon constitutes a side of an equilateral triangle. Since , , and .

Dodecahedron

Computing angles for the dodecahedron works a bit differently from the tetrahedron and icosahedron. Instead of using existing edges as vectors, we construct an equilateral triangle by connecting three vertices:

So (since it’s part of a regular pentagon) and . Then and .

Varignon’s theorem proved in one line with vectors

Today I was reading some math book when the author mentions Varignon’s theorem, and gives a proof. The proof was not very long, but it was somewhat confusing. On Wikipedia, several more short proofs were given, but they were all more confusing than need be.

I remembered seeing the theorem proven using vector geometry before, but I couldn’t find the text (nor any other page / book that proves it this way) –

[image shamelessly taken from Wikipedia]

Varignon’s theorem states that in any quadrilateral, if we join the midpoints of the sides, then we get a parallelogram.

In the diagram, it suffices to prove that vector HG is equal to vector EF — vectors must have both the same orientation and length to be equal. This works since any method that proves HG = EF can also prove HE = GF. The proof goes as follows –

And we’re done. (the last step is due to symmetry of HG and EF)

Algorithmic Counterpoint: How I Wrote a Computer Program to Generate Music at Mathcamp 2011

Hello all; I have just returned from Mathcamp, a five week math program for high school students. I’m not going to write in detail about life at Mathcamp, other than that it was amazing in every way.

This year at Mathcamp, I chose to do a computer programming project to ‘teach’ a computer to write ‘music’. The word ‘music’ is in quotes because what it’s expected to generate is more or less random and nothing like actual music by Bach or Mozart; on the other hand, the ‘music’ generated resembles actual music closely enough that it can still be called music, not a random string of notes. Anyways, here’s a short sample of what it can generate:

What can be considered ‘music’ in some sense here is really just a set of rules backed by a random number generator. Hence what it does is really the following:

1. Generate a main melody using a bunch of rules: ie, what notes are allowed to go with each other, what rhythms are allowed to go with what notes, etc.
2. Using the main melody as a sort of a baseline, generate one or more counterpoint melodies: a counterpoint melody is constrained by the same rules that the main melody must follow, but also has to harmonize with the existing melody, thus being constrained by another set of rules.
3. Once all the notes are generated, the program simply uses some library — in our case JFugue – to play the notes through the speakers.

The bulk of our time was spent implementing, tweaking, and debugging the rules and the various other substeps in the above process.

The source code, mostly written by myself over about two weeks, is available as a Google Code project.

Mathcamp 2011

This year I got invited to Mathcamp, a five week summer camp for “mathematically talented high school students”. The camp will run from July 3 to August 7 this year, in Reed College in Portland, Oregon. This means I will be leaving three days from the time of writing!

The camp is quite expensive — $4000 for normal students — but thankfully, Mathcamp has given me a pretty generous scholarship.

Application to Mathcamp required, among other things, a eight question qualifying quiz. After working on them for one week, I managed to solve six of the problems and half of a seventh problem. One of my favorite problems in the quiz is the third:

In a park there is a merry go round with seats, and kids waiting to get on (the kids are evenly spaced around the merry go round). The kids climb on one by one in some order, only taking the seat in front of them and only if the seat is empty; however, each time a kid climbs on, the merry go round rotates counterclockwise by one position. For what values of is it possible for every kid to get a seat?

My solution goes as follows (I’m assuming that it’s okay to discuss solutions by now as the deadline for submitting solutions has passed more than two months ago):

Let the children be numbered clockwise and the seats also numbered so that child is matched with seat , and so on.

Let us denote a sequence of moves by as the sequence that the children get on the ride: for example if then child 0 gets on, followed by child 2 then child 1. Each time a child gets on, the seats shift counterclockwise by one, so child gets onto seat , but child gets onto seat (modulo ), child gets onto seat , and so on.

Suppose that a particular sequence works at getting every child on the ride. Then must take on every value between 0 and modulo . We claim that this is possible when is odd, and impossible when is even.

If is odd, let . We use sums to show that this sequence indeed works, and every child gets a different seat (by every sum being different modulo ). The sums in this case are so the sums modulo are . Clearly, this covers every integer modulo exactly once.

We claim this is impossible when is even. Suppose the contrary, that this is possible, or in other words, take on every value between 0 and modulo . Adding everything up gives

But since is a permutation of , their sum is . Hence

Since is even, it can be written as for some integer . Then

This is a contridiction. Hence the arrangement is impossible when is even.

Eyes!

I randomly made this thing out of boredom:

Cute, but it’s probably a sign that I need some better ideas for hobby programming projects xD

It uses the pyglet library, and is only a page or so of python code.