Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> General Discussion >> Research Arising From Arimaa
        
(Message started by: 99of9 on Mar 3^rd, 2005, 9:31pm)

Title: Research Arising From Arimaa
Post by 99of9 on Mar 3^rd, 2005, 9:31pm

As most of you know, one of Omar's objectives in offering the Arimaa challenge is to encourage research into games AI.

I thought I'd let you know about research that arose as a result of my participation in the challenge. It's not games AI, but it's an unintended consequence (strangely enough this often happens in science - it even has a name: serendipity).

Many of you probably know about the Zobrist key. It's a hash function for chess/go/arimaa boards to recognise whether you've already evaluated or searched a particular board position, and hence can ignore it when you get up to it again. It's really fast to calculate updates, similar board positions give very different hash keys, but the key doesn't change at all when you switch two of the same pieces around (because the board position is really the same as it was).

Well when I learned of this, I realised it was the answer to a problem one of my colleagues had asked my advice on about 6 months earlier:

He was working on simulations of metal crystals with more than one type of element in them. There is a computational procedure called kinetic Monte Carlo, which allows you to follow the changes inside the metal as a function of time, by switching atoms, and seeing if the energy of the crystal goes up or down (these energy calculations can sometimes take a long time if it is a large crystal). One problem with this method is that when you are simulating low temperatures, the system gets stuck, and you find yourself repeatedly searching the same set of states, going around and around and getting nowhere. He wanted to be able to recognise whether he'd ever seen a state before.

At the time he asked me, we had come up with almost nothing. A full check of all the states we'd ever seen, comparing every atom to every atom in our current state would take way too long.

Of course it turns out there is a direct analogy between 2-D arimaa board positions, and 3-D crystal compositions. If you switch two rabbits around, you haven't changed anything. If you switch a rabbit with an elephant, you have. If you switch two copper atoms around, you haven't changed anything. But if you switch a copper with an iron, you have.

So we used the Zobrist key. It turned out that in some cases we could speed up our simulation by a factor of 100 by just making sure we never bothered to recalculate any energy we had calculated before.

We wrote a paper about the application which has just been published in Computer Physics Communications (2005), 165(1), 37-48. [D.R. Mason, T. S. Hudson, A. P. Sutton].

Now it's true that Zobrist did his work 40 years before arimaa was even invented, and it has been widely used in both Chess and Go. But I may never have heard of it if I hadn't had to look at all the chess literature when I was writing an arimaa robot. So I think arimaa gets the credit for the Zobrist key breaking into materials chemistry simulations!

Now all I've gotta do is discover something that goes the other way. If I can bring something from materials chemistry into arimaa... maybe I'll get gnobby fired up by a factor of 100.

Title: Re: Research Arising From Arimaa
Post by omar on Mar 11^th, 2005, 4:40pm

Wow a 100 times speed up is quite a bit; its like taking a plane instead of ridding a bike. I would consider that a breakthrough. It allows things that couldn't be done before.

Very interesting. Thanks for sharing this with us.