Answers.Body: <p>First thing you're going to want to add is probably a <a href="https://en.wikipedia.org/wiki/Transposition_table" rel="nofollow noreferrer">Transposition Table</a>, as also suggested by SmallChess.</p>
  
  <p>Afterwards, I'd look into <a href="https://www.chessprogramming.org/Aspiration_Windows" rel="nofollow noreferrer">Aspiration Search</a> and/or <a href="https://chessprogramming.wikispaces.com/Principal%20Variation%20Search" rel="nofollow noreferrer">Principal Variation Search</a> (also see <a href="https://www.ics.uci.edu/~eppstein/180a/990202b.html" rel="nofollow noreferrer">this page</a>).</p>
  
  <p>Then I'd look into things like the <a href="https://en.wikipedia.org/wiki/Killer_heuristic" rel="nofollow noreferrer">Killer Move Heuristic</a>, and maybe also see if you can simply implement existing parts of your engine more efficiently (e.g. use <a href="https://chessprogramming.wikispaces.com/Bitboards" rel="nofollow noreferrer">bitboards</a> for your state representation).</p>
  
  <p>Other than all of that, the <a href="https://chessprogramming.wikispaces.com/" rel="nofollow noreferrer">chess programming wiki</a> probably has lots of other interesting pages as well.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-03-08T09:16:23.443Z
Answers.LastActivityDate: 2019-10-14T21:05:40.977Z
Answers.LastEditDate: 2019-10-14T21:05:40.977Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>Try cache or transposition table. Without it, your search tree might explode.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-05T22:58:22.400Z
Answers.LastActivityDate: 2018-02-05T22:58:22.400Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>You can try <strong><em>move ordering</em></strong> where we store the values till depth d, sort them and use them in particular order before we go for depth d+1 ...</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-23T09:03:18.780Z
Answers.LastActivityDate: 2020-01-23T09:03:18.780Z
Answers.UserDisplayName: Abhinav Ravi
Answers.Body: <p>To make boost iterative deepening with alpha-beta pruning you can use the 
  SSS* Search algorithm, its a best first strategy algorithm. The SSS* Algorithm can improve the time efficiency of the overall algorithm but it increases the space complexity.
  I am linking the wiki to it <a href="https://en.wikipedia.org/wiki/SSS*" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/SSS*</a>
  I will update the answer as soon as i get a better solution.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-03T05:19:53.603Z
Answers.LastActivityDate: 2018-03-09T18:16:52.280Z
Answers.LastEditDate: 2018-03-09T18:16:52.280Z
Answers.UserDisplayName: vasurb
Body: <p>I read about minimax, then alpha-beta pruning, and then about iterative deepening. Iterative deepening coupled with alpha-beta pruning proves to quite efficient as compared to alpha-beta alone.</p>
  <p>I have implemented a game agent that uses iterative deepening with alpha-beta pruning. Now, I want to beat myself. What can I do to go deeper? Like alpha-beta pruning cut the moves, what other small change could be implemented that can beat my older AI?</p>
  <p>My aim to go deeper than my current AI. If you want to know about the game, here is a brief summary:</p>
  <p>There are 2 players, 4 game pieces, and a 7-by-7 grid of squares. At the beginning of the game, the first player places both the pieces on any two different squares. From that point on, the players alternate turns moving both the pieces like a queen in chess (any number of open squares vertically, horizontally, or diagonally). When the piece is moved, the square that was previously occupied is blocked. That square can not be used for the remainder of the game. The piece can not move through blocked squares. The first player who is unable to move any one of the queens loses.</p>
  <p>So my aim is to cut the unwanted nodes and search deeper.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-30T23:50:14.107Z
Comments.Text: Welcome to AI!  Sounds like an interesting problem.  (I've take the liberty of adding combinatoric and combinatorial-games tags.)  Can I ask, do you have a sense of the size of the gametree?  What are your restriction on number of plies the algorithm can search in a reasonable time?  I mention it because, if the game tree expands sufficiently, depth search may not be fruitful until the game tree starts to become tractable.
Comments.UserDisplayName: DukeZhou
Tags: <game-ai><heuristics><alpha-beta-pruning><combinatorial-games><adversarial-search>
Title: What else can boost iterative deepening with alpha-beta pruning?
UserDisplayName: Suhail Gupta
ThreadText: # What else can boost iterative deepening with alpha-beta pruning?
  
  (Asked by: username_0 on 2018-01-28)
  
  I read about minimax, then alpha-beta pruning, and then about iterative deepening. Iterative deepening coupled with alpha-beta pruning proves to quite efficient as compared to alpha-beta alone.
  
  I have implemented a game agent that uses iterative deepening with alpha-beta pruning. Now, I want to beat myself. What can I do to go deeper? Like alpha-beta pruning cut the moves, what other small change could be implemented that can beat my older AI?
  
  My aim to go deeper than my current AI. If you want to know about the game, here is a brief summary:
  
  There are 2 players, 4 game pieces, and a 7-by-7 grid of squares. At the beginning of the game, the first player places both the pieces on any two different squares. From that point on, the players alternate turns moving both the pieces like a queen in chess (any number of open squares vertically, horizontally, or diagonally). When the piece is moved, the square that was previously occupied is blocked. That square can not be used for the remainder of the game. The piece can not move through blocked squares. The first player who is unable to move any one of the queens loses.
  
  So my aim is to cut the unwanted nodes and search deeper.
  
  **Tags:** game-ai, heuristics, alpha-beta-pruning, combinatorial-games, adversarial-search
  > **Comments:**
  > **username_1**: Welcome to AI!  Sounds like an interesting problem.  (I've take the liberty of adding combinatoric and combinatorial-games tags.)  Can I ask, do you have a sense of the size of the gametree?  What are your restriction on number of plies the algorithm can search in a reasonable time?  I mention it because, if the game tree expands sufficiently, depth search may not be fruitful until the game tree starts to become tractable.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_2 on 2018-03-08. Score: 4
  
  First thing you're going to want to add is probably a [Transposition Table](https://en.wikipedia.org/wiki/Transposition_table), as also suggested by SmallChess.
  
  Afterwards, I'd look into [Aspiration Search](https://www.chessprogramming.org/Aspiration_Windows) and/or [Principal Variation Search](https://chessprogramming.wikispaces.com/Principal%20Variation%20Search) (also see [this page](https://www.ics.uci.edu/~eppstein/180a/990202b.html)).
  
  Then I'd look into things like the [Killer Move Heuristic](https://en.wikipedia.org/wiki/Killer_heuristic), and maybe also see if you can simply implement existing parts of your engine more efficiently (e.g. use [bitboards](https://chessprogramming.wikispaces.com/Bitboards) for your state representation).
  
  Other than all of that, the [chess programming wiki](https://chessprogramming.wikispaces.com/) probably has lots of other interesting pages as well.
  
  
  ---
  
  ### Answer by username_3 on 2018-02-05. Score: 1
  
  Try cache or transposition table. Without it, your search tree might explode.
  
  
  ---
  
  ### Answer by username_4 on 2020-01-23. Score: 1
  
  You can try ***move ordering*** where we store the values till depth d, sort them and use them in particular order before we go for depth d+1 ...
  
  
  ---
  
  ### Answer by username_5 on 2018-02-03. Score: 1
  
  To make boost iterative deepening with alpha-beta pruning you can use the
  SSS\* Search algorithm, its a best first strategy algorithm. The SSS\* Algorithm can improve the time efficiency of the overall algorithm but it increases the space complexity.
  I am linking the wiki to it [https://en.wikipedia.org/wiki/SSS\*](https://en.wikipedia.org/wiki/SSS*)
  I will update the answer as soon as i get a better solution.
  
  
  ---
  
  