0

This is a homework assignment that I'm trying to develop more, but I'm having trouble figuring out how to go further.

The assignment is basically about solving Lights Out of different sizes using different approaches. I have developed a brute-force approach which works, but it takes a lot of time when the board size is big.

My problem comes when I'm trying to implement a best-first search or a A* approach to solve the game. I have to design a heuristic function for the game and this is where I'm having trouble. I don't have the slightest clue about what could be a good heuristic function in this case.

Having no prior experience in AI, I'd like to have some guidance/tips on how to develop a good heuristic function for the case of Lights Out.

Thank you for all your help.

sobosama
  • 150
  • 8

1 Answers1

1

The heuristic only needs to give you a vague estimate of how many button presses at minimum are required. One simple heuristic would be the numberOfLightsRemaining/5, since each press can at most turn off 5 lights.

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • Thanks for your answer. That is indeed an interesting heuristic, but how would one judge it to be good or not? – sobosama Feb 11 '20 at 02:02