![]() Strategy 2: Consider all Neighboring Same-Box Sequences If it does, keep the new solution.įor example, if our push sequence, in terms of box pushes, is AAABBCCBAD, we would evaluate AABABCCBAD first, and it does not lead to an improvement, consider AAABCBCBAD next, etc. Just iterate over all pushes, and if two neighboring pushes are for two different boxes, try swapping the push order and then evaluating the new push sequence to see if it solves the problem with a smaller move count. ![]() Two pushes that are spread out a lot in time are likely to not be switchable – other pushes are more likely to have to happen in-between. We consider neighboring pairs because they are temporally close, and thus more likely to be a valid switch. The simplest optimization strategy is to try permuting neighboring push pairs. Strategy 1: Consider all Neighboring Box Pairs We can easily evaluate a given push sequence for validity by playing the game through with that push sequence, which we have to do anyway to calculate the number of player moves. We thus have a simple constrained optimization problem – to minimize the number of player moves by permuting the pushes in a provided push-optimal solution subject to the constraint that we maintain solution integrity. As we’ll see, this basic assumption works pretty well for the problems at hand. The number of player moves is the number of box pushes plus the number of moves to walk to the appropriate location for each push.Īll of the strategies I use here simply shuffle the pushes around. As such, our objective function takes in a potential push sequence solution and evaluates both its validity (whether it is, in fact, a solution), and the number of player moves. Here, we are trying to find solutions with fewer player moves. Solution EvaluationĮvery optimization problem needs an objective function. In this post, I’ll just cover some very basic approaches to improve my push-optimal solutions from the previous posts. ![]() There are many approaches for optimizing solutions. Thus, Sokoban solvers typically find push-optimal solutions, or more commonly some valid solution, and Sokoban optimizers work with an existing solution to try and improve it. ![]() Rather than doing that, it is common to optimize a given solution to try to find another solution with a smaller player move count. ![]() Rendering the same push-optimal solution above with its player moves clearly shows how inefficient it isĭirectly solving for move-optimal solutions from scratch is difficult. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |