Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> What now?
        
(Message started by: erict on Apr 17^th, 2009, 12:36pm)

Title: What now?
Post by erict on Apr 17^th, 2009, 12:36pm

So I re-wrote the Perl Move Generator script in on this page:
http://arimaa.com/arimaa/download/
in Python (Omar do you want this? You only listed that you wanted a C/C++ version, not sure if you would consider Python).
It wasn't easy, since the Perl script didn't use very good variable names nor very many comments.

My question is, what is the typical approach to developing the bot?
What me and my friend are doing right now is generating all the possible moves that the bot can make and evaluating the board states using the evaluation values in this thesis:
http://arimaa.com/arimaa/papers/HaizhiThesis/haizhiThesis.doc
However, it's very time consuming especially when we try to determine what the next player's move will be using Minimax (or one of its derivatives).

Should the bot have functions that look over the board to see if it can do any of the well known strategies/attacks like the one on this page?
http://en.wikibooks.org/wiki/Arimaa

Title: Re: What now?
Post by lightvector on Apr 18^th, 2009, 3:14pm

You can do pretty much whatever you want - there are lots of approaches you can experiment with (different methods of tree search, learning features, monte carlo, heuristic pruning, etc).

The "standard" algorithm is basically what you seem to be doing - search down the tree, using a hand-coded evaluation function after a certain depth. It sounds like you are doing straight minimax, in which case you should look at alpha-beta pruning (a quick search online will reveal any number of explanations and pseudocode). If you want to go the "traditional" route, following that, you can try heuristic move ordering, heuristically extending or pruning various parts of the search, and so on..

As for higher level strategies, typically these are built in by making the evaluation recognize such situations and score them appropriately. But you might find other ways to do this.

Game-tree search is always very time consuming and difficult, simply because the exponential branching, and the difficulty of evaluating intermediate positions in the game. Anyways, good luck!

Title: Re: What now?
Post by Janzert on Apr 18^th, 2009, 5:45pm

It sounds like you may already be past this point but if it helps you any, two different arimaa position representation/move generators in python can be found in the pyrimaa package of my custom bot interface at https://code.launchpad.net/~janzert/+junk/aei. The first and fastest (board.py) uses a bitboard representation (http://chessprogramming.wikispaces.com/Bitboards). The other (x88board.py) uses a 0x88 board representation (http://chessprogramming.wikispaces.com/0x88).

Janzert