Answers.Body: <p>An optimal value function from reinforcement learning on a game is a perfect heuristic, allowing a single ply search for the best action.</p>
  <p>Other than very basic games, such as tic tac toe (noughts and crosses), an RL agent will not learn a perfect value function. The issue is then that the value function is not <em>admissible</em> (it may over-estimate as likely as under-estimate), therefore it can mislead a search.</p>
  <p>However, in practice, the non-admissibility of a heuristic in game playing agents is not a complete showstopper. It means the agent will be less efficient and may make some mistakes, but an approximate learned heuristic is stll pretty good.</p>
  <p>In practice, the main issue I have found when using a neural network or other ML approximator in minimax is the number of evaluations that need to be made. For efficiency you may be able to batch them up, but for a significant depth you may still need 100s or 1000s of value function prediction runs to resolve the minimax. This can take far more CPU time than a simpler heuristic.</p>
  <p>In my own project (playing Connect 4) where there was a strict time constraint for turns, I resolved this issue by:</p>
  <ul>
  <li>First performing a deep minimax (e.g. 12-ply) with simplest heuristic (1 for winning, -1 losing, 0 for draw or unresolved) plus a flag for whether the search was to game completion (i.e. unresolved). This deep search could be highly optimised around win condition detection only.</li>
  <li>Second, if <em>that</em> search did not resolve the game, I ran a much shallower minimax (3-ply) with the ML value predictions as a heuristic.</li>
  </ul>
  <p>This combination performed well enough to get into top 10 positions in a coding competition where several competitors had coded perfect play. The main issue with it is that the first search could prune a branch for good reasons that the second search then preferred due to inaccuracies in the value function, causing the agent to lose to perfect play agents. There are probably ways around that, but I did not investigate further.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-12T09:34:02.023Z
Answers.LastActivityDate: 2022-02-12T09:34:02.023Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am taking a course where we write minimax, alpha-beta pruning and interative deepening in Python for the game of Isolation.<br />
  I am supposed to write heuristics for an evaluation function of the game state.<br />
  But I wondered if training an RL agent on this game, have it master it, are there any examples of a deep RL agent that returns heuristics based on what it learns while training?</p>
  
Tags: <reinforcement-learning><minimax><heuristics><alpha-beta-pruning>
Title: Can Deep Reinforcement Learning come up with heuristics for a game it trains on and masters?
UserDisplayName: mLstudent33
ThreadText: # Can Deep Reinforcement Learning come up with heuristics for a game it trains on and masters?
  
  (Asked by: username_0 on 2022-02-12)
  
  I am taking a course where we write minimax, alpha-beta pruning and interative deepening in Python for the game of Isolation.  
  I am supposed to write heuristics for an evaluation function of the game state.  
  But I wondered if training an RL agent on this game, have it master it, are there any examples of a deep RL agent that returns heuristics based on what it learns while training?
  
  **Tags:** reinforcement-learning, minimax, heuristics, alpha-beta-pruning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-12. Score: 1 | Accepted answer
  
  An optimal value function from reinforcement learning on a game is a perfect heuristic, allowing a single ply search for the best action.
  
  Other than very basic games, such as tic tac toe (noughts and crosses), an RL agent will not learn a perfect value function. The issue is then that the value function is not *admissible* (it may over-estimate as likely as under-estimate), therefore it can mislead a search.
  
  However, in practice, the non-admissibility of a heuristic in game playing agents is not a complete showstopper. It means the agent will be less efficient and may make some mistakes, but an approximate learned heuristic is stll pretty good.
  
  In practice, the main issue I have found when using a neural network or other ML approximator in minimax is the number of evaluations that need to be made. For efficiency you may be able to batch them up, but for a significant depth you may still need 100s or 1000s of value function prediction runs to resolve the minimax. This can take far more CPU time than a simpler heuristic.
  
  In my own project (playing Connect 4) where there was a strict time constraint for turns, I resolved this issue by:
  
  * First performing a deep minimax (e.g. 12-ply) with simplest heuristic (1 for winning, -1 losing, 0 for draw or unresolved) plus a flag for whether the search was to game completion (i.e. unresolved). This deep search could be highly optimised around win condition detection only.
  * Second, if *that* search did not resolve the game, I ran a much shallower minimax (3-ply) with the ML value predictions as a heuristic.
  
  This combination performed well enough to get into top 10 positions in a coding competition where several competitors had coded perfect play. The main issue with it is that the first search could prune a branch for good reasons that the second search then preferred due to inaccuracies in the value function, causing the agent to lose to perfect play agents. There are probably ways around that, but I did not investigate further.
  
  
  ---
  
  