Answers.Body: <p>This sounds like a problem that might be solvable with a LSTM-DQN approach, as described in <a href="https://arxiv.org/pdf/1506.08941.pdf" rel="nofollow noreferrer">Language Understanding for Text-based Games using Deep
  Reinforcement Learning</a> by Narasimhan et al., 2015, and then extended to a domain very similar to your problem in <a href="https://aaai.org/ojs/index.php/AAAI/article/view/3882" rel="nofollow noreferrer">Deep Reinforcement Learning for Syntactic Error Repair in Student Programs</a> by Gupta et al., 2019.</p>
  
  <p>The basic idea is to treat the array of letters each of which can be 'circled' or not, plus the position of a cursor as a state. An action is to move the cursor or toggle the state of a letter. You then model the problem as a reinforcement learning problem, with rewards given every time an entire new word becomes 'circled', probably with a caveat about not circling any invalid letters (otherwise, it'll just learn to circle everything).</p>
  
  <p>This is just a guess, but it seems like it's very closely related to your problem, so it's likely to be effective.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T04:55:00.750Z
Answers.Text: Thanks. They seem like very modern papers. Surprising! I'll take a look.
Answers.UserDisplayName: zooby
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T06:46:17.007Z
Answers.Text: This kind of AI (reinforcement learning) has only really come into its own recently. The field has existed for a long time, but wasn't been feasible for real problems until [2015](https://www.nature.com/articles/nature14236).
Answers.UserDisplayName: Omegastick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T14:06:00.077Z
Answers.Text: @zooby There are other (older) ways you could try to solve this problem, but this is the approach I think is most promising given the modern state-of-the-art. Hope you find it useful.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T16:00:49.300Z
Answers.Text: I think yes, it is theoretically a reinforcement leaning problem. I wonder, however, whether such methods would solve the problem in a realistically human timeframe given the amount of combinations involved.... Well, I may have to just try it!
Answers.UserDisplayName: zooby
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T16:02:03.357Z
Answers.Text: An LSTM in theory should be able to solve the problem, but again I wonder about scaling... I feel like it needs some semantic knowledge somehow.
Answers.UserDisplayName: zooby
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T16:33:11.853Z
Answers.Text: @zooby This approach will probably require many times more exposure to word-search problems than a human would (keep in mind: it's going to have to learn _English_ from scratch, as well as to take the right actions). The beauty of the approach, to my mind, is that it doesn't need semantic knowledge. This is increasingly true of most of the best approaches to language-related problems, and usually these systems scale _better_ than semantic ones, rather than worse.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T01:15:35.077Z
Answers.LastActivityDate: 2019-11-11T01:15:35.077Z
Answers.UserDisplayName: John Doucette
Body: <p>This at first sounds ridiculous. Of course there is an easy way to write a program to solve a wordsearch. </p>
  
  <p>But what I would like to do is write a program that solves a word-search like a human.</p>
  
  <p>That is, use or invent different strategies. e.g. search randomly for the starting letter; go line-by-line; </p>
  
  <p>Probably the AI will eventually find out that going line by line looking for a given starting letter of a word is a good strategy.</p>
  
  <p>Any idea how you would write such a strategy-finding AI?</p>
  
  <p>I think the main "moves" would be things like "move right one letter in the grid", "store this word in memory", "compare this letter with first letter in memory" and a few more.</p>
  
Tags: <deep-learning><search><architecture><reasoning>
Title: How to create an AI to solve a word search?
UserDisplayName: zooby
ThreadText: # How to create an AI to solve a word search?
  
  (Asked by: username_0 on 2019-11-10)
  
  This at first sounds ridiculous. Of course there is an easy way to write a program to solve a wordsearch.
  
  But what I would like to do is write a program that solves a word-search like a human.
  
  That is, use or invent different strategies. e.g. search randomly for the starting letter; go line-by-line;
  
  Probably the AI will eventually find out that going line by line looking for a given starting letter of a word is a good strategy.
  
  Any idea how you would write such a strategy-finding AI?
  
  I think the main "moves" would be things like "move right one letter in the grid", "store this word in memory", "compare this letter with first letter in memory" and a few more.
  
  **Tags:** deep-learning, search, architecture, reasoning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-11-11. Score: 4
  
  This sounds like a problem that might be solvable with a LSTM-DQN approach, as described in [Language Understanding for Text-based Games using Deep
  Reinforcement Learning](https://arxiv.org/pdf/1506.08941.pdf) by Narasimhan et al., 2015, and then extended to a domain very similar to your problem in [Deep Reinforcement Learning for Syntactic Error Repair in Student Programs](https://aaai.org/ojs/index.php/AAAI/article/view/3882) by Gupta et al., 2019.
  
  The basic idea is to treat the array of letters each of which can be 'circled' or not, plus the position of a cursor as a state. An action is to move the cursor or toggle the state of a letter. You then model the problem as a reinforcement learning problem, with rewards given every time an entire new word becomes 'circled', probably with a caveat about not circling any invalid letters (otherwise, it'll just learn to circle everything).
  
  This is just a guess, but it seems like it's very closely related to your problem, so it's likely to be effective.
  
  > **Comments:**
  > **username_0**: Thanks. They seem like very modern papers. Surprising! I'll take a look.  
  > **username_2**: This kind of AI (reinforcement learning) has only really come into its own recently. The field has existed for a long time, but wasn't been feasible for real problems until [2015](https://www.nature.com/articles/nature14236).  
  > **username_1**: @zooby There are other (older) ways you could try to solve this problem, but this is the approach I think is most promising given the modern state-of-the-art. Hope you find it useful.  
  > **username_0**: I think yes, it is theoretically a reinforcement leaning problem. I wonder, however, whether such methods would solve the problem in a realistically human timeframe given the amount of combinations involved.... Well, I may have to just try it!  
  > **username_0**: An LSTM in theory should be able to solve the problem, but again I wonder about scaling... I feel like it needs some semantic knowledge somehow.  
  > **username_1**: @zooby This approach will probably require many times more exposure to word-search problems than a human would (keep in mind: it's going to have to learn _English_ from scratch, as well as to take the right actions). The beauty of the approach, to my mind, is that it doesn't need semantic knowledge. This is increasingly true of most of the best approaches to language-related problems, and usually these systems scale _better_ than semantic ones, rather than worse.  
  
  ---
  
  