Draft

W h i r l y - G a m e f r o m P l a y e r P e r s p e c t i v e G a m e p l a y User action is an action made by a player by click or keyboard stroke. Action causes a "Move" which is a set of steps. Each step is a change of location of single unit. G a m e p l a y s t a t e r e p r e s e n t a t i o n Between moves, the state of game is represented with position, often denoted as map.pos, where map is a game map. pos has few properties, but suffiecient-to-describe-the-playstate-property is pos.lid2uid which means a mappimg from location-id to unit-id. location-id is an index of all legal locations of units. Locations are contained in array map.locs. Index of this array is location-id, lid. For example, location of unit on second row, first cell, on second z-level is loc = [2,1,1] In fact, there are two master arrays which represent the position: lid2uid and tops tops[x][y] is a z - index of highest unit in z-order stack Of course, tops can be deduced from lid2uid, but tops is autimatically rebuilt when lid2uid chanded. In source code, the core function to make a move was gio.do_move_steps=function(direction, gm, pos, unit, mode, freeze_pos) in map.js file M o v e .. .. begins its life in gio.do_process_move = function( ... As of version 1.143 move format is set here: //: validates and creates new_move in core/navig/map.js 1. Until all move steps are not verified, position is not changed. 2. When all steps of move are confirmed valid, then position is changed step-by-step in function gio.do_process_move after section /// avoids changing position and leaves C a n o n. I d e a o f P o s i t i o n - S t a t e R e p r e s e n t a i o n. lid2uid is too big to be used in solver which memorizes already tested states. Another array is used to represent a state: The name is "ordered_hids" or "canon". Hid is a shortcut for "hole id". "Hole" is another weird name. There is an array, hid2lid, exists. It contains only locations which are reachable to dynamic unit in the map. Black walls are excluded. We think about holes like about "holes" in the map where one can "drop" a dynamic unit. Hence, index of hid2lid is "hid" and value is location-id, lid. When we have hid2lid, we can further encode board-position by mapping units to hids. For example, consider map: - A B # A @ A - are boxes of color 1. - dcolony 0 B - is box of color 2. - dcolony 1 # - is a black wall. @ - is a pusher of color 0. - dcolony 2 - is an empty cell "dcolony" stands for "dynamic colony". Assume, for a moment, that there are no grounds and targets. Lids are mapped to this board this way: 0 1 2 3 4 5 Hids are: 0 1 3 2 4 (Wall is omitted, it is not dynamic.) hid2lid is = [ 0, 1, 4, 2, 5 ] Unit ids are 0 1 2 3 4 There are three dynamic colonies: A, B, and @. Then, finally, the position can be mapped as "ordered hids": (1 2) (3) (4) or simply 1 2 3 4, where hids are grouped by dcolony. Hids inside the colony are always put in ascending order, so distribution (2 1) will never happen, hence representation of distribution for given dcololy is always unique. The terms "ordered_hids", "solver node", "pstate", "playstate", "canon" mean the same in the program. "Solver node" sounds like a part of some tree, and indeed, there is a tree: "nodes_repository" in adapter.js which keeps discovered canons in following manner: nodes_repository is an array, for given example, its dimension is 4, non-leaf elements point to array of next nodes, leafs denote existing canons. Leafs do not keep canons. Leafs keep boolean "true" value and are used to mark discovered canons. Such tree is built when solver does a search. For above example, this tree is organized in following natural order: 0 1 ... ... 1 2 ... ... 1 2 3 4 ... .... 0 1 2 0 1 2 3 0 1 2 4 .... Here, the leaf nodes "0 1 2 3", "1 2 3 4" are canons. C a n o n R e p r e s e n t a t i o n V a r i a n t s As of Version 1.191, there are 3 modes for Solver in gio.solver.config: CANON_STRING CANON_ARRAY CANON_LINKED_LIST (default) String representation looks like "0.1:2:3" for canon (0,1)(2)(3). In CANON_ARRAY, canons are stored in spheres array. In CANON_STRING, canons are stored in spheres array as strings. In CANON_LINKED_LIST, elements of spheres array and nodes_repository are coinsided, but canon is stored as a address-path to itself in nodes_repository. P o s s i b l e s o l v e r o p t i m i s a t i o n Hids range is redundant at the game beginning and possibly at the end. Hids can be dynamically reindexed. The initial index is taken from start position which will look like 0.0.0:0.0.0:0 This will preserve memory in the beginning. There are 7 index-arrays in this example. When solver progresses, these arrays are gradually being filled. At every sphere we know how much space takes each index: if worse case 4.7.9:0.10.11:1, bits are: 3.3.4:1.4.4:1 which takes total 20 bits. Big savings if tere are 17 hids which take 5.5.5:5.5.5:5 ... 35 bits.