Answers.Body: <p>A MLP only does pattern recognition, it will not learn search. </p>
  
  <p>Tictactoe, (Oughts and Crosses), is such a simple game that your network should learn the moves from the training data by heart, no generalisation required. If it still loses games, maybe your training data doesn't consist of particularly good moves. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:24:14.517Z
Answers.Text: Thanks. Would be able to extract good moves out of a mix (let's say training data generated from a random player) if the training data consists of hundreds of thousands moves consisting of both good and bad moves?
Answers.UserDisplayName: Achilles
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:27:22.573Z
Answers.Text: It should learn the board positions by heart and learn a probability distribution over the moves made in that position, with the highest probability for the most common move.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:31:40.083Z
Answers.Text: So, if you only learn the moves of the winner, that might be enough to extract good moves, if you learn all moves, it will only learn random moves.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:35:06.633Z
Answers.Text: Ok, so if it consistently sees bad moves, it'll learn bad moves, makes sense. I've been looking for emergent phenomenon where it learns human like strategies while playing with random players.
Answers.UserDisplayName: Achilles
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:39:39.980Z
Answers.Text: I feed in only the winner's moves for training but the winner could be winning by fluke even after making bad moves, that explains it. How does it work in games like chess etc where people say that the AI is coming up with its own strategies and what not?
Answers.UserDisplayName: Achilles
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:44:03.713Z
Answers.Text: Yeah, but good moves should win more often after many random games, so it should actually work. Chess programming is completely different, it's mostly about tree search. AlphaGo uses neural networks, but it has been trained using reinforcement learning and it has an additional tree search component.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:53:55.830Z
Answers.Text: Cool, thanks for the explanation. This (that MLPs would be able to do nothing more than pattern recognition) is true for all other types of neural networks (convolution, dnn, deep belief etc) as well?
Answers.UserDisplayName: Achilles
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T09:00:58.160Z
Answers.Text: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/54478/discussion-between-blindkungfumaster-and-achilles).
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-02-28T08:19:14.450Z
Answers.LastActivityDate: 2017-02-28T08:19:14.450Z
Answers.UserDisplayName: BlindKungFuMaster
Body: <p>I'm doing a little tic-tac-toe project to learn neural networks and machine learning (beginner level). I've written a MLP based program that plays with other search based programs and trains with the data generated from the games. </p>
  
  <p>The training and evaluation are strictly policy based - Inputs are board positions and outputs are one-hot encoded array that represents the recommended move for that board position. I've not added search algorithms so that I can understand what to expect from a purely MLP approach.</p>
  
  <p>The MLP model has 35 features and 1 hidden layer and after a few hundred thousands games it has sort of learned to draw 50% games. It has learned the basic stuff like how to block the player from winning and some good board placements.</p>
  
  <p>Now, my question is - It hasn't learned advanced strategies that require making a move that may not be as beneficial for the current move but will improve its chances later. But should I expect that from a strictly policy MLP based no-search approach? Since all that it is being trained on is one board and the next recommended move (even if thousands of those pairs), is it logical to expect it to learn a lookahead approach that goes beyond "the best move for the current board" training? </p>
  
  <p>Put another way, would it be a possible at all for a MLP to learn lookahead without any search strategies? If not, are there any alternatives that can do it without search?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-02-28T08:11:32.350Z
Comments.Text: What are those 35 features? And where do you get the recommended move from?
Comments.UserDisplayName: BlindKungFuMaster
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-02-28T08:20:49.890Z
Comments.Text: 35 is the number of neurons in the hidden layer (or feature maps in the convolution version). The recommended moves are the moves made by the winners of games in the training data. The idea being that it tries to figure out what the winner of the games did and extracts patterns and strategies by itself.
Comments.UserDisplayName: Achilles
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-02-28T08:23:09.270Z
Comments.Text: But we are talking about tictactoe: 3x3 board and 0 and X moves?
Comments.UserDisplayName: BlindKungFuMaster
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-02-28T08:25:02.757Z
Comments.Text: Yes, that's the one. It's an overkill but I'm using it to understand how neural networks work.
Comments.UserDisplayName: Achilles
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-02-28T08:36:56.123Z
Comments.Text: You should probably avoid spatial pooling if you use a convnet, because it might throw away the exact position of the Xs and 0s. Also, if your maps are 3x3, that's already the full board, they'll have to be smaller.
Comments.UserDisplayName: BlindKungFuMaster
Tags: <machine-learning><multilayer-perceptrons>
Title: Is it a valid assumption that a purely MLP based tic-tac-toe player will learn lookahead strategies?
UserDisplayName: Achilles
ThreadText: # Is it a valid assumption that a purely MLP based tic-tac-toe player will learn lookahead strategies?
  
  (Asked by: username_0 on 2017-02-26)
  
  I'm doing a little tic-tac-toe project to learn neural networks and machine learning (beginner level). I've written a MLP based program that plays with other search based programs and trains with the data generated from the games.
  
  The training and evaluation are strictly policy based - Inputs are board positions and outputs are one-hot encoded array that represents the recommended move for that board position. I've not added search algorithms so that I can understand what to expect from a purely MLP approach.
  
  The MLP model has 35 features and 1 hidden layer and after a few hundred thousands games it has sort of learned to draw 50% games. It has learned the basic stuff like how to block the player from winning and some good board placements.
  
  Now, my question is - It hasn't learned advanced strategies that require making a move that may not be as beneficial for the current move but will improve its chances later. But should I expect that from a strictly policy MLP based no-search approach? Since all that it is being trained on is one board and the next recommended move (even if thousands of those pairs), is it logical to expect it to learn a lookahead approach that goes beyond "the best move for the current board" training?
  
  Put another way, would it be a possible at all for a MLP to learn lookahead without any search strategies? If not, are there any alternatives that can do it without search?
  
  **Tags:** machine-learning, multilayer-perceptrons
  > **Comments:**
  > **username_1**: What are those 35 features? And where do you get the recommended move from?  
  > **username_0**: 35 is the number of neurons in the hidden layer (or feature maps in the convolution version). The recommended moves are the moves made by the winners of games in the training data. The idea being that it tries to figure out what the winner of the games did and extracts patterns and strategies by itself.  
  > **username_1**: But we are talking about tictactoe: 3x3 board and 0 and X moves?  
  > **username_0**: Yes, that's the one. It's an overkill but I'm using it to understand how neural networks work.  
  > **username_1**: You should probably avoid spatial pooling if you use a convnet, because it might throw away the exact position of the Xs and 0s. Also, if your maps are 3x3, that's already the full board, they'll have to be smaller.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2017-02-28. Score: 3 | Accepted answer
  
  A MLP only does pattern recognition, it will not learn search.
  
  Tictactoe, (Oughts and Crosses), is such a simple game that your network should learn the moves from the training data by heart, no generalisation required. If it still loses games, maybe your training data doesn't consist of particularly good moves.
  
  > **Comments:**
  > **username_0**: Thanks. Would be able to extract good moves out of a mix (let's say training data generated from a random player) if the training data consists of hundreds of thousands moves consisting of both good and bad moves?  
  > **username_1**: It should learn the board positions by heart and learn a probability distribution over the moves made in that position, with the highest probability for the most common move.  
  > **username_1**: So, if you only learn the moves of the winner, that might be enough to extract good moves, if you learn all moves, it will only learn random moves.  
  > **username_0**: Ok, so if it consistently sees bad moves, it'll learn bad moves, makes sense. I've been looking for emergent phenomenon where it learns human like strategies while playing with random players.  
  > **username_0**: I feed in only the winner's moves for training but the winner could be winning by fluke even after making bad moves, that explains it. How does it work in games like chess etc where people say that the AI is coming up with its own strategies and what not?  
  > **username_1**: Yeah, but good moves should win more often after many random games, so it should actually work. Chess programming is completely different, it's mostly about tree search. AlphaGo uses neural networks, but it has been trained using reinforcement learning and it has an additional tree search component.  
  > **username_0**: Cool, thanks for the explanation. This (that MLPs would be able to do nothing more than pattern recognition) is true for all other types of neural networks (convolution, dnn, deep belief etc) as well?  
  > **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/54478/discussion-between-blindkungfumaster-and-achilles).  
  
  ---
  
  