0

I'm working on an AI to play a fairly simple game, using minimax and genetic algorithms to find weights to score board states with.

The game resembles 4x4 tictactoe, but a turn can be spent to move a piece to an adjacent space, pieces come in different sizes, and larger pieces can cover up smaller pieces.

I want to score the board by looking at a variety of factors, such as how close they are to completing a 4 in a row, and how many adjacent enemy pieces could potentially be moved onto, but I have no idea what these factors should specifically be.

My ideas: For each line, making a scoring expression based on number of friendly pieces, number of empty spaces, and number of enemy pieces, but I can't think of a simple expression to score that with weights, since the value probably won't be a linear function.

For each line, making a piecewise scoring expression split based on the number of enemy pieces in the row, and an expression based on the number of allies. Hence having 1 piece in an empty row might be worth more than having 1 piece in a row full of enemies, thus blocking them off, and the inverse would be true for having 3 in a row in a row that is already blocked.

Some complications I've noticed: Having 3 pieces in a row, but then one of the enemy large pieces also in the row, is virtually worthless for anything except preventing their piece's movement.

Having 3 pieces in a row, with a small enemy piece in that row is almost a win, if you can place a large piece adjacent to their small piece to move onto it. This seems particularly hard to detect. It's also possible if this is worked into a factor, the above "number of adjacent enemies that can be moved onto" won't be necessary.

Thanks for any help. I have no clue how to proceed.

Toren Darby
  • 9
  • 4
  • It seems you want to invest a lot of time/brains into a handcrafted evaluation function. It might be much easier to (1) Stick to Monte Carlo Tree Search (which does not really need this function; but could be improved by it) (2) Learn an evaluation function by Q-Learning (with a general function-approximator: e.g. NN). The former is possibly your best bet to implement a strong AI with manageable work. The latter is a more complex approach with huge potential. One more remark: minmax is not really there to learn scoring weights, but helping to evaluate a more precise board (which is reachable). – sascha Jul 21 '16 at 02:51
  • This is really helpful, but I don't see a way to upvote you and tell you you're special. Thank you for the advice. – Toren Darby Jul 21 '16 at 17:54
  • Take a look at http://stackoverflow.com/q/1291377/3235496 there are some ideas you could find interesting. – manlio Jul 22 '16 at 12:15

0 Answers0