Given the Blokus game, where players try to score points by occupying most of the board with pieces of their colour (The board is a square regular grid and the pieces are polyominoes), we define the Blokus Corners problem as follows: there are three locations to cover, one in each corner (other
than the starting location). The search problem is to find the most efficient way through the board to cover all four corners. Note that you may place a tile on the board only if it touches at least one piece with only corner-to-corner contact allowed; edges cannot touch! The cost of an action in this search problem is the size of the tile.
That is, we want to cover all the corners while leaving the board as vacant as possible.
For example:
I need to find a consistent heuristic for this problem.
This is the heuristic that I came up with:
def heuristic(state, problem):
uncovered_corners = [corner for corner in problem.corners if
not is_covered(state, corner[0], corner[1])]
total_distance = 0
filled_tiles = numpy.argwhere(state.state != -1)
if len(filled_tiles) == 0:
return 0
for corner in uncovered_corners:
min_distance = float('inf')
for x, y in filled_tiles:
distance = manhattan_distance(corner, (x, y))
min_distance = min(min_distance, distance)
total_distance += min_distance
return total_distance
However, I couldn’t formally prove that the heuristic is consistent, although it gives pretty good results.
I would like an opinion on whether heuristics are consistent, and if so, how can it be proven