6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – DukeZhou
    Jan 30, 2018 at 23:50

4 Answers 4

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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 ...

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .