lsiecker / foundations-of-ai Goto Github PK

Implement the Alpha-Beta-Pruning to increase the speed of the search tree.

If in a leaf there is no possible move, then the previous move to get to that leaf is a TabooMove.

This is already in the code:

 181           # If there are no possible moves (when no move is valid), return a infinite value
 182           if len(getAllPossibleMoves(state)) == 0:
 183               if isMaximizingPlayer:
 184                  return None, float("-inf")
 185              return None, float("inf")

The idea is to check how many empty squares there are, if this is favourable for us to have the last move, do nothing.
If we do not have the last move at that moment, do the newly found TabooMove.

Checking how many empty squares there are can be done by counting the Sudokuboard.empty in the sudokuboard string.

Implementing this table will increase the speed of the iterative deepening implementation. With this table, not the whole tree has to be created in every iteration.

https://www.sudokudragon.com/sudokustrategy.htm Links to an external site., for an overview of different strategies.

• search on only a subset of legal moves
• focus on exploring moves that are guaranteed to be part of the sudoku puzzle's final solution
• do not work from left to right