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 15*15 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 15*15 board the possible game states become too large too 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$
  • 2
    $\begingroup$ Welcome to AI! Excellent question imho. $\endgroup$ – DukeZhou Dec 12 '17 at 21:20
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 https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

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 an 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 currently 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.

A side note, applying 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 gomuku is solved. See https://stackoverflow.com/questions/6952607/ai-strategy-for-gomoku-a-variation-of-tic-tac-toe for others' thoughts and ideas.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Nice point about gomoku as a solved game. This makes it easy to validate the AI's strength (i.e. does it solve the game and express perfect play, or is it just playing more optimally than an opponent, as in the case of AlphaGo.) $\endgroup$ – DukeZhou Dec 12 '17 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.