冰塔解題器

2014-2020?

平面上有很多冰塊跟火團
每次可以把一個冰塊往縱向或橫向推，冰塊會一直往同個方向移動到

碰到障礙物停下來，或

碰到火團然後兩者都消失 (金色冰塊碰到火團不會消失，會繼續往前進)

消冰器 (recycler) 然後掉進去消失

把所有火團滅掉就完成

2014 剛學 Python 的時候亂寫的 solver

網頁版，可以當做是懶人包：氷塔　―魔法使いの挑戦―

Preface

If not otherwise mentioned, the game spec is according to the original game, 氷塔.

maximum map size = 20 * 14 (18 * 12 if excluding borders); ice count has a hard limit 200 in source code; all indices can be stored in short int (2 bytes long).

Hierarchy

A level/solver can be classified with the max index it contains/supports, with increasing complexity:

Index	Item + repr.	Remarks
N/A	wall `#`
-	ice `%`	A regular one.
1	fire `*`
2	recycler `-`	When a regular ice block moves to this cell, it is destroyed.
3	golden ice `$`	A golden ice is permanent in a level. There is no way to destroy one.
(4)	magician `@`	Since here, the magician's reachability is considered
4	arrows `v^<>`	Magician/ices are allowed to co-exist on the same spot
5	dispenser `+`	dispense ice blocks randomly to four directions, if possible

Note: Despite seemingly complicated, "recyclers only" stages are usually easier for brute-forcing.

Considering only 1. or additionally 2. may be a good practice on various space searching techniques (like sokoban).

For example, W-21 is a good demonstration, that some simple configurations lead to hard enough puzzles at least for humans:

####################
#*################*#
#                  #
#     %      %     #
##    *      *    ##
##      *  *      ##
##     %    %     ##
##                ##
##  %     @    %  ##
##                ##
####################

Can you spot out a 21-step solution? See one in this sample output from my solver. Note that it requires a correct implementation of reachability-checking to admit a legitimate solution.

A straightforward solver typically considers 1. & 3. only; The aim here is to consider 1. ~ (4). and it's far more challenging than before.

We can call the above simple configurations static. Adding some arrows & dispensers, the game becomes dynamic and is dramatically complicated.

Here is a popular construction that makes use of arrows: Some arrows may form a cycle which traps everything entering it. A tight arrow cycle forms a n-barrier, requiring (n-1) ice blocks inserted for the magician to pass through. Otherwise, the magician will stuck forever.

State transitions

Move in empty area & Push an ice block

For static configurations, this is the only possible transition
Step onto an arrow (optionally being transported)

the region it can move to (w/o any side-effects) can be seen as a contiguous partition over total space, which is invalidated when any ice block is moved
Move elsewhere to make a moving ice block stop

how to define "elsewhere" is hard
(various techniques exploiting time gaps; maybe a TAS is more reliable)

heuristics? potential method?

Pruning…

dead state detection: prune states where

at least one fire is of no reachable ice blocks (?)
- ice block reachability is hard to tackle??
(movable ices > fire count) && no movable golden ices.
The following cases are considered non-movable ("dead-position" detection):
- a block at a 90-degree shaped wall
- two blocks next to each other along a wall
- generalize -> for a state, a contiguous group of ice blocks of no associated pushable entries

(not knowing if it's correct): (non-edge ice blocks > non-edge fire count) && no non-edge golden ices

observation: (# of ice blocks that is at edge position) is monotonic?

      ####
#######  #
#        #
#      % #
#        #
#        #
#      %##  <-- this ice is not considered an edge one!
#       #
#########

block reachability?
bipartite matching?

My thoughts on implementations

Full state = Board configuration (static) + {initial, incremental} state

Board configuration:

Flatten 2D array storing static obstacles: walls, fires, recyclers

walls are special: ice blocks is stopped one cell off instead of onto them.
Positions of fires
List of ice blocks, their types

When exploring possible transitions, a shared BoardView (i.e., a full sized map to put objects on; Possibly one in each stack) is faster, but storing it in each state is too expensive. Without pruning, a 11-step stage may grow to 10⁹ states (OG-13):

####################
#                  #
#                  #
#                 *#
#                 *#
# % % % % $   @   *#
#                 *#
#                 *#
#                 *#
#                 *#
# *****************#
#                  #
#                  #
####################

Initial state:

Initial positions for ice blocks
Initial position for the magician (to be normalized)

Incremental state (should be as tiny as possible):

Reference to parent state
Depth (i.e. number of operations made from root state)
~~Zobrist hash, 64-bits are usually enough~~ no need to store it!
Position of magician, TO BE normalized
Cleared fires (~~as bitmap~~ store pattern hash id instead)
Position of moved ice blocks, index of old+new, with one special value for eliminated by a recycler

old pos. is only for going back to parent state
… (?)
Some misc. factors for evaluating state badness

→ ~ 24 bytes so far

Q: How to compute the map from an incremental state?

From scratch: Use configuration + initial state to populate the view. Walk until root state, recording states along the way and apply accordingly.

A state to another: Go backwardly to their LCA (knowing their depths is convenient) and then go forwardly to the other state. ref.

Q: How to store/update 2D map efficiently?

Preprocessing: One can pre-calculate all blocks' destinations for all directions as if only static obstacles are present. When a dynamic block is added/removed, only the corresponding column/row needs to be updated.

Q: Is there anything missing?

Note that a recycler/dispenser is not purely an "obstacle". An ice block may happen to overlap on top of it for a brief period (refer to the code for details). As per the spec, golden ices are not eliminated by recyclers – which simply pass through them. Even a naive approach needs to handle this, since a golden ice may stop on top of it upon stopping by a wall, e.g.,

##     #  ##
##-****$ @##
##     #  ##

##     #  ##
##$    @  ##
##     #  ##

None of official levels has this edge case AFAIK, though. Verification required: Is the above block pushable vertically afterwards?

Psuedocode

Some sketch:

Input: board B, initial state S
Output: a sequence of states leading to a complete state, if any

def EXPLORE(mutable board view b, state s):
  calculate reachable area,
  > updating b for normalized magician position
  return pushables of s

init queue: {S}
initialize board view "b", and
> a stack storing pushables at depth=n

EXPLORE(b, S) -> stack[0]

for each state "s" in queue:
  if s is complete:
    return state
  pop s from queue
  
  retrieve pushables from stack[s.depth]
  (TODO: prioritize moves that "reduce" fires?)
  
  for each "pushable": (iceIdx, dir):
    (s', clearedFireList) = APPLY(b, s, pushable)
    EXPLORE(b, s') -> stack[s.depth+1]  <-- should be the bottleneck
    calculate hash(s') from hash(s)
    if s' is not visited
      insert s' to queue
      mark hash(s') as visited
    UNAPPLY(s', clearedFireList)

Iterative-deepening DFS: performs poorly since game graphs are tend to be cycle-rich (?). To preserve optimality, a transition table has to remember the depth it last visits and do relaxation… but the information has been forgotten then. If we try to memoize, this is essentially BFS, but we would have memory issues soon!

Heuristics

See the following levels that surely require heuristics.

OG: https://www.youtube.com/watch?v=jVoDiq131I4

OG-7
OG-24

TODO…

資源們

四個官方認可的關卡集：

氷塔 (50 關)
冰塔2：氷塔～2度目の冬～ (349 關，東西南北各50+中央99+裏50, thread, alt. source)
504i (20 關，據說最早是設計給手機版的？)

Solutions: https://www.youtube.com/watch?v=RXHTMalW9lE
魔法使いの挑戦 (50關，有一些關卡有 extensions，比較少在討論)

Chi-Feng: https://www.youtube.com/channel/UCjD7AdR1BW_NdVO3NHdqzjQ/discussion

(Naive) solver by Chi-Feng: mainly BFS + transition table
https://drive.google.com/file/d/106G1ffVkFVGpo8gPSeggq4N148I4TGJK/view
Modified by me:
https://gist.github.com/andy0130tw/fed21b0d1c8298098470bf34db50153f

王兆成: https://www.youtube.com/channel/UCnP6EicvzKWkLx1DC-v0utA

~~《冰塔攻略總論》：https://drive.google.com/file/d/1zjFQlsSoPrv219z_92cxMwSvWpHl-R5q/view~~

http://gameschool.cc/user/gorck820/#!mywork/forumTopic

http://web.archive.org/web/20161128090314/http://milkpot.sakura.ne.jp/icetower/index.html