Answers.Body: <p>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.</p>
  <p>If you are unfamiliar with alpha-beta pruning and minimax see <a href="https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm" rel="nofollow noreferrer">this article</a>.</p>
  <p>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:</p>
  <ul>
  <li>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.</li>
  <li>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).</li>
  <li>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.</li>
  </ul>
  <p>Of course, this is just one way, and you would need to find game data first.</p>
  <p>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.</p>
  <p>Finally, it's helpful to know Gomoku is solved. See <a href="https://stackoverflow.com/q/6952607/3924118">this post</a> for others' thoughts and ideas.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-12T20:18:43.130Z
Answers.LastActivityDate: 2021-01-30T22:13:35.237Z
Answers.LastEditDate: 2021-01-30T22:13:35.237Z
Answers.UserDisplayName: sma
Body: <p>Currently, I'm doing a project that's about creating an AI to play the game <a href="https://en.wikipedia.org/wiki/Gomoku" rel="nofollow noreferrer">Gomoku</a> (it's like tic tac toe, but played on a 15<em>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</em>15 board, the possible game states become too large to implement this project.</p>
  <p>My question is, should I use neural networks or genetic algorithms for this problem? And more specifically, how should I implement this?</p>
  
Tags: <neural-networks><game-ai><genetic-algorithms><minimax><alpha-beta-pruning>
Title: Should I use neural networks or genetic algorithms to solve Gomoku?
UserDisplayName: Conway
ThreadText: # Should I use neural networks or genetic algorithms to solve Gomoku?
  
  (Asked by: username_0 on 2017-12-12)
  
  Currently, I'm doing a project that's about creating an AI to play the game [Gomoku](https://en.wikipedia.org/wiki/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 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?
  
  **Tags:** neural-networks, game-ai, genetic-algorithms, minimax, alpha-beta-pruning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2017-12-12. Score: 7 | Accepted answer
  
  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](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 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](https://stackoverflow.com/q/6952607/3924118) for others' thoughts and ideas.
  
  
  ---
  
  