7

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.

nbro
  • 42,615
  • 12
  • 119
  • 217
Suhail Gupta
  • 171
  • 1
  • 5

4 Answers4

4

First thing you're going to want to add is probably a Transposition Table, as also suggested by SmallChess.

Afterwards, I'd look into Aspiration Search and/or Principal Variation Search (also see this page).

Then I'd look into things like the Killer Move Heuristic, and maybe also see if you can simply implement existing parts of your engine more efficiently (e.g. use bitboards for your state representation).

Other than all of that, the chess programming wiki probably has lots of other interesting pages as well.

Community
  • 1
Dennis Soemers
  • 10,519
  • 2
  • 29
  • 70
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 ...

Abhinav Ravi
  • 111
  • 3
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* I will update the answer as soon as i get a better solution.

Dennis Soemers
  • 10,519
  • 2
  • 29
  • 70
vasurb
  • 11
  • 2
1

Try cache or transposition table. Without it, your search tree might explode.

SmallChess
  • 1,421
  • 1
  • 9
  • 14