9
$\begingroup$

Currently, I'm doing a project that's about creating an AI to play the game Gomoku (it's like tic tac toe, but played on a 1515 board and requires 5 in a row to win). I have already successfully implemented a perfect tic tac toe AI using Q-learning and having game states/actions stored in a table, but, for a 1515 board, the possible game states become too large to implement this project.

My question is, should I use neural networks or genetic algorithms for this problem? And more specifically, how should I implement this?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

For Gomoku, it seems a bit of an overkill to use neural networks or the genetic algorithm as both take a while, and more often than not, don't go how you want it to. The Gomoku game tree is rather large, but you can get a decent AI from minimax, game tree pruning, and a good heuristic function (that includes counting half and full 2s,3s,4s,...etc.) as opposed to mapping out the full space.

If you are unfamiliar with alpha-beta pruning and minimax see this article.

If you really want to use neural networks or genetic algorithms you can for the learning experience. Regarding neural networks, one way to do it is the following:

  • Define a heuristic function that receives a board state input (sequence of 0,1,2 for empty, black, white), and outputs a 'goodness' value of the board state. The neural network is our heuristic function.
  • Assuming that the moves in these game are optimal, train off of the difference between the current best move (by your current parameters) and what move your data says is the best. This is how we define our error function! Thus you are minimizing this difference so that what move your neural network says is the strongest is ideally what your game data says is the strongest (Optimization of this error function can be done via backpropagation or genetic algorithm).
  • Ideally, by this point, you can now use your ('strong') neural network-based evaluation function for your game tree move evaluations instead of hardcoded heuristics.

Of course, this is just one way, and you would need to find game data first.

As a side note, applying a genetic algorithm can occur in a few ways, such as parameter optimization in a neural network as mentioned above or game tree searching, so make sure you are clear how you define the problem setting with it! The same goes for alternative ways to apply a neural network.

Finally, it's helpful to know Gomoku is solved. See this post for others' thoughts and ideas.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .