Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Tree generation in abalone artificial intelligence

I need to implement an intelligent agent to play Abalone game, for this kind of game the best way to proceed seems a min-max strategy with alpha beta pruning.

I have already implemented a naive search algorithm that use min-max with pruning,
enter image description here

my problem is…

How to generate the nodes of the tree where perform the search?

I have no idea of the right way to do this, and how assign the weigh to each node.

Tags:

2

Answers


  1. 0

    For generating the tree nodes: You need to implement a method that returns a collection of all possible legal moves given the current board position and the player whose turn it is. All these moves will become children of the node representing the current board position. Repeat until memory is exhausted to generate the game tree 😉 or rather until you reach a reasonable tree depth.

    For alpha-beta search you also need an evaluation function which calculates the weight for each board position/node. You can do some research or think about such a function yourself, maybe considering the number of stones still on the board. However a bad evaluation function can seriously screw up your results, so take care and run a lot of tests.

    If you have trouble coming up with a reasonable evaluation function, I recommend you take a look into Monte-Carlo techniques such as UCT.

    http://en.wikipedia.org/wiki/Monte_Carlo_tree_search

    These tackle the problem using a probabilistic approach and have some nice advantages over alpha-beta. Also they don’t require an evaluation function so you could skip this step.

    Good luck!

    Login or Signup to reply.
  2. 0

    I have published two libraries for move generation in Abalone. You didn’t mention the programming language used for your search implementation, but you can easily port the functions.

    For an evaluation function, distance between all your marbles, or distance to their gravity center (same thing), works nicely. Tino Werner used this with a twist for his program that won ICGA 2003.

    For understanding distance when using hex coordinates, I can recommend Amit Patel’s page: https://www.redblobgames.com/grids/hexagons/

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search