My attempt at a Conquest AI

December 9, 2011

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.


Notes on interpolating polynomials

February 12, 2010

My first post here, so I’m not really sure how to do all the formatting and stuff. It’ll take me a while to get used to the Latex.

I’ll get started.

We have a set of points, [(x_0,y_0), (x_1,y_1), \cdots, (x_n,y_n)] ; how would we find a polynomial function f(x) that passes through all of the points?

Let’s have an example here. We have the four points (1,100), (2,30), (3,70), (4,1000) and we need to find a polynomial function so that f(1) = 100, f(2) = 30, f(3) = 70, and f(4) = 1000.

Remember that a polynomial function of order n can be represented by f(x) = a_0 x^n + a_1 x^{n-1} \cdots a_{n-1} x + a_n. So a line would be f(x) = a_0 x + a_1 , which is more commonly seen as y = mx + b. Similarly a quadratic would be f(x) = a_0 x^2 + a_1 x + a_2.

What we need to do to find the polynomial is to determine a set of coefficients a_0, a_1, \cdots, a_n so that for every point (x,y) in our set of points [(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)] the statement y = a_0 x^n + a_1 x^{n-1} + \cdots + a_n is true.

Notice here that the number of coefficients a_n is always one more than the order of the function. This implies that to interpolate a polynomial of P points we need an order P-1 polynomial.

We have four points, so we need to determine the correct cubic polynomial:

y = ax^3 + bx^2 + cx + d

We simply substitute the four points into the equation:

100 = a (1)^3 + b (1)^2 + c (1) + d
30 = a (2)^3 + b (2)^2 + c (2) + d
70 = a (3)^3 + b (3)^2 + c (3) + d
1000 = a (3)^3 + b (3)^2 + c (3) + d

Simplify:

a + b + c + d = 100
8a + 4b + 2c + d = 30
27a + 9b + 3c + d = 70
64a + 16b + 4c + d = 1000

Now we have a simple set of linear equations. We solve this and get:

a = 130
b = -725
c = 1195
d = -500

y = 130 x^3 - 725 x^2 + 1195 x - 500

Plot this in Mathematica:

Of course we could have saved all that work and just used the built in function:

Expand[InterpolatingPolynomial[{{1, 100}, {2, 30}, {3, 70}, {4,
    1000}}, x]]

> -500 + 1195 x - 725 x^2 + 130 x^3

So now that we know how to do polynomial interpolation, let’s have some fun with this. Take the Runescape level XP table (don’t laugh) and find a function that generates these values.

I used Vim to transform the table into a mathematica input, then computed the 98-th degree generating polynomial. The computation only took about a second, and produced a very large (several pages worth) output. Here’s an image.

This is normal, right? Now let’s try plotting the polynomial, as before:

Yes, this function passes through all of our 99 points. But with such a large number of points, the function oscillates wildly between points. This is known as Runge’s phenomenon.


Follow

Get every new post delivered to your Inbox.

Join 72 other followers