```

Map Difficulty Metrics

Map Creativity Metric ..
Pros and Cons
Metrify. Practical Steps to Calculate.
Results.
Discussion.
Samples Digest. Former Versions.

Map Creativity Metric ..

.. is a creativity demanded from human-player to solve the map,
.. does not necessarily measure aesthetic or entertaining qualities of the puzzle,
.. ( perhaps can be named as intrinsic, inner, or inherent difficulty, puzzleness, or cracks number. )

C = d / v, where
difficulty, d = I + ( p - i ) * g, where

i = number of interactions between hero and other units,
p = number of moves,
p, i are taken for p-minimal solution,

g = min( density, 1 ) is "effective density" of units, to eliminate idle moves in sparse maps,
density = u / s,  when s > 0
u,      when s = 0,
u = number of dynamic units,
s = number of empty cells,

I = effective interactions.

v, volumability, non-creative factor to be eliminated by division: d / v.

w = C / maxc, where

w - is a number of whirps of stonecracker machine to crack walls in Sokoban maps,
maxc - C for the game with maximal C in given family.

Let's look at idea ..

.. it is assumed, that game difficulty is a "nested composition" of difficulties with increasing creativity.

The first level is a number of mouse-clicks to handle game navigation. We ignore it. Assume GUI is well done.

v - the second level of difficulty is a number of brain-clicks to handle a number of units, dimensions of the map,
number of rules to remember. This sort of creativity can be interesting in arcade games, but not of Whirly's interest.
We are going to exclude it. We call it "volumability" to emphasise its "mechanical" nature.
We'll discuss it in a moment.

Suppose, the puzzle is not solved in the second level. What next?
Beyond second level, there are brain-clicks required to accomulate experiences of the game, built strategies,
deal with surprises of the gameplay, and consult intuition.

There can be more levels. But we don't go there. We include all of them as level 3.
Every level below 3 is a boredom by definition.
Level 3 is a creativity measured with C, creativity-metric.

So, d = C * v.

Applying the same idea, we don't take d as plain number of moves: d != p. (**).
We would try to use formula dtry = i + density * ( p - i ) to remove low-level difficulty.
But this is not enough, we are trying to remove low-level difficulty even from i,
when we calculate I in formula (*).

Let's consider the details

When we calculate the difficulty, we still trying to remove boredoms.
We don't use i in place of I for difficulty. Simple pushing a box along the line is
not a creative difficulty. Changing boxes is more creative.

I = 2( 2t + ( i - t ) ) / 3.   ( * )

t, "reinteractions" are changes of a target by hero. For example in Sokoban context,
t = "box changes" when hero leaves one box and turns own attention to other which is
considered as one brain-click.

Formula (*) is arbitrary crude and needs research. An extreme case i = t gives I = 4i/3 and
is rewarded by about +30%, the case of no reinteractions: t = 0 is gratified by about -30%.

Let's discuss boredoms, v.

When number of boxes and walls grows, difficulty is growing, but not necessarily
demands player to be creative.
Whirling up geometrical elements without increasing of their number may contribute to
creativity ( or may not ).
There also is possible increase of creativity-demand due not only complex geometry, but
due unexpected scenario stemmed from specific geometry.

Excessively complex rules are also part of volumability.

Volumability:

v = n' * b' * r', where

n', b', r' are cells, breeds, rules boredoms respectively.

For each of these boredoms a', we select a range of comfortability:
amin < a > asense where "a" penalized slightly, ( see near ... do_boredomize = function ... ),
and when
a > asense, penalized as a' = 1 + a/asense.

"a" stands for one of the following:

b = number of scenarioble breeds,
n = number of internal cells in the map,
r = number of effective rules and objectives in game.

We don't try to build one formula for all families of puzzles.
Instead "we build a perspective user" for given family of puzzles.

We restrict comfortability ranges for our user and use them as
parameters for our formulas.

See comments in near object EXPECTED_USER.

For example, we would take these parameters for "Sokoban User":

Because of in Sokoban game number of scenarioble breeds is not changed:
hero, box, target - 3, we exclude criteria "breeds" completely
by making bmin = 3. The user completely comfortable with 3 breads.
This is an enthusiastic Sokoban player.
bsense does not matter, breed = 1 always. No penalty.

Rules? The is only one rule: push. So Rmin = 1. rules = 1 always.

Cells? We noted of abandance of "big" maps. So, for Soko-user:
nmin = 4 * 4 = 16. User do not note any boredom when less than this.
nsense = 10 * 10 = 100. User feels presence 100 internal cells. Penalty begins work around nsense.

Finally: v = 1 + n / nsense,  when n > 100,
1                when n < 16,
smoothly grows from 1 to 2 otherwise.

But for Whirly-family including many Sokoban-like families, one must compare maps with
different game-rules and different breeds. The chosen parameters are near object
EXPECTED_USER.

Examples for maps without hero-targets:

Sokoban:  b = 3,  ( hero, box, and target )
r = 1   ( push )

Colorban: b = 3 -- 30, ( 3 races * color )
r = 1, ( push )

PullPush: b = 3 -- 30,
r = 2  ( pull and push )

Monkeyban: b = 3,
r = 2  ( push or push with sticky-boxes effect )

Flocks:    b = 3 -- 30,
r = 2  ( push or push with sticky-boxes effect )

PushMan: b = 3, ( no targets for boxes, but htarget for hero. )
r = 1  ( push )

Pros and Cons

Practical Cons.

It is hard to calculate this metric because of

1.	Solver sorts solution by p, minimal path length, and takes the top item.
However, this order is not necessaritly the same as order by i, number of interactions, or by t.
To have a correct creativity metric calculated, solver must sort by C.

2.	Not every solver can solve the map. One may use human-built solutions, which
can be far from optimal.

Cons.

1. Formulas are crude and not adequate. They don't reflect a nature of a game-family.
It is not difficult to calculate additional metrics of solution, like turns, returns, correlations ... and
construct adequate formulas. This is not done.

Maps are penalized by increasing number of cells ultimately. Patterns are not felt.
However, patterns cancel human difficulty and instead make game more creative.

2. Metric C has unknown upper bound. C allows only to order maps, not to measure them.
Relative measure depends on max known map.

3. p-optimal solution is not necessary is i - optimal, but i is more significant in d.

4. fails in multihero games. "Changing a horse number", h, counts non-trivial moves;
for example, P = p-i+h can be used instead of p-i.

Pros.

1. Simplicity.

Possible Metrics

d = p( 1/2 + 2(p-i)i/pp ).
Behaviour: maximumal and = 1 when i = p/2 which favours interactions.
Advantage: no need to calculate density.
Penalizes by 50% when i=p which is not fair. However, it seems: p ~ i is rare case.

"Progressive difficulty"
P = ( a*p + b*i + c*t ) / ( a+b+c )
Behaviour: favours interactions with weight b and reinteractions with weight c.
Most sofisticated solution should be close to upper bound of Dp which is Dp ~ p.
Choice of coefficients a, b, c depends how one values i and t.
Disadvantage: arbitrary. Coefficients a, b, c are for simplicity, not for adequateness.

F, flat difficulty, coefficients a, b, c = 1 and norm = 1.
F = p + i + t.

Practical Steps to Calculate

The following cases are listed in order of decreasing accuracy.

Solution is C-optimal ( has minimal possible C ).   --- Exact accuracy.
Solution is p-optimal ( has minimal path length ).  --- Not exact. Other i or t still possibly produce smaller C.
Solution has unknown optimality at all.
Possibly found by human and there is no solver
which can traverse through all possible solutions.  --- Not exact. Worse accuracy.

If you have a map with solution, but don't know its parameters p, i, t,
beside of using Orc's Wallcracker, here are a few examples how to calculate metrics.

1.  The map is posted on Internet:
http://users.bentonrea.com/~sasquatch/sokoban/m1
and you have solution in your hands:

urrDDuulldRlulldRdddddrrrrrrrrrruuuuulll
ddllldlluRRRRdrruLuurrrdddddlllllllllluu
uuuurrdLurrrdLddrrRdrUUdlllluuulldRurDDu
llulldRdddddrrrrrrrrrruuuuullulldRRlddll
ldlluRRRRdrUUdlllluululldRRurDDulllddddd
rrrrrrrrrruuuuuulldRlulldRRlddllldlluRRR
RdrUU

Add to URL-query following parameters and land to player:
?akey=sokoban&map_ix=123&metrify&curl=http://users.bentonrea.com/~sasquatch/sokoban/m1&solpath=urrDDuulldRlulldRdddddrrrrrrrrrruuuuulllddllldlluRRRRdrruLuurrrdddddlllllllllluuuuuurrdLurrrdLddrrRdrUUdlllluuulldRurDDullulldRdddddrrrrrrrrrruuuuullulldRRlddllldlluRRRRdrUUdlllluululldRRurDDullldddddrrrrrrrrrruuuuuulldRlulldRRlddllldlluRRRRdrUU\e\

Note that path must be terminated with 3 characters "\e\" to detect browser's URL-truncation.

2.  The map is posted on Internet and contains solution inside of collection.
../def/albums/sokoban/collections/weirdy/documentation_test.txt
(use http-form, not //-form to secure correct location).
Add to URL-query following parameters and land to player
?akey=sokoban&map_ix=1&metrify&pix=0&metrify&curl=//def/albums/sokoban/collections/weirdy/documentation_test.txt

pix=0 is an index of solution in the list of solutions in script.

3.  Sokoban map with solution is in your hand.
Land to a player, select Sokoban, paste map with solution into "Edit Map Scripts",
then select "Metrify Map" from
editor's selection box.

4.  Finally, you know only map. If your computer is enough powreful, set
solver to run on link or
after landing on map.

Example of solving on link ( set slim according to your resources, don't overestimate ):
?akey=sokoban&map_ix=0&solve&slim=4000000&curl=http://users.bentonrea.com/~sasquatch/sokoban/m1

5.  To look at metrified map again, go to Help/About Map and find metrics there.

It has been scientifically proven that number of braincracks to solve the map = whirps. (*)
We had good stonecracker borrowed from Orcs after they broke last human city
and no longer needed the equipment. When map did not have walls,
the machine began cracking boxes so equality (*) still held.
Unfortunately the machine sank into sinktarget embedded into one of the maps by malicious author.
Some authors protect their solutions brutally ...