The Setting
Fix a mean-payoff game on a set of vertices with edges, transformed weights , and top width . The randomized solver for is run with a global sample count , a power of two, and a trial count , both fixed by . The randomized solver works on solver inputs : a box with corners in and reference width , with positive rational support weights and budgets . We call the budgets of the input; they give the measure of a set . An orientation for is one of the two choices and together with a list of exception sets of vertices.
The procedure Orient maps a solver input to an orientation. On a box with it decides from the vector that the basic solver computes on the box. On a wider box it moves a center times, each time by two calls to the procedure Ask, and then decides from the displacement of the last center, or calls itself on a smaller box around a center drawn at random.
In the library, Orient runs on a stack machine over raw data, where numbers are binary words and unary counters, a counter of length standing for , and where a call leaves on a stack a frame that waits for the answer. One step of the machine is given case by case, one case for each job that can be called and each frame that can receive an answer; the library states Orient as eight such cases, together with the raw operations they use.
The Raw Machine
A register pack is a record of eight registers holding raw data: budgets , a box , a counter , two vectors and , a list of vectors, an orientation and a list of orientations.✦ A raw vector is a list of binary words. A raw box is a box whose corners are raw vectors; it has a width and a midpoint . A mask is a list of booleans marking a set of vertices, and we use set notation for masks. A raw orientation is a bit , true for , with a list of masks.✦ We write a pack by the registers it fills, as , where a hat marks a raw object, being raw budgets and a raw box; the other registers hold the zero budget, the zero box, empty counters and lists, and the orientation with no masks.✦ The pack with every register at its default is the empty pack.✦
A stack cell is a tag with a pack, the tag being a counter whose length names the job or the frame the cell stands for.✦ A machine state is a current cell with a stack, the list of the cells of the pending frames.✦ We write for the state that calls the job on the pack over the stack , for the state that returns to , and for with a frame holding pushed on top; , and take the pack . The jobs , , and have the tags , the frames , , , , and have the tags , and a returned pack has the tag .
The environment is a tuple of the raw arena of the game and four counters: the sample exponent , the sample count , the trial count and a step budget for the basic solver.✦ The environment represents at when its arena is the vertex code of with raw words holding the transformed weights of the edges, its first three counters have the lengths , and , and its step budget has length at least .✦ A machine input is an environment, a counter , the random index of the step, and a state .✦ Of the cases use the current pack of the current cell, the stack , the caller pack of the frame on top of , the empty pack when is empty, and the rest of below that frame.
Raw data represent the solver’s objects, and we write when represents . A mask represents the set it marks. A list of raw vectors represents a list of points of a box when its entries represent them one by one.✦ A raw orientation represents an orientation for when its bit is the choice of and its masks represent the exception sets of in order.✦
Boxes, Centers and Displacement Sets
Let be a box of the solver at top width , with midpoint , and write for the box of half width around . When , the narrowed box of at is and the widened box is . On raw data, and are the raw boxes centered at whose half width is the width of divided by , with read from the environment, and by .
For a point of , the positive and negative displacement sets of at are (1) The raw masks and make the two tests of (1) on binary words, with a word as the scale, the midpoint of for and its width for .
For a counter , the center lookup is the entry of index , counting from , of the vector list of the current pack, or the midpoint of the caller’s box when the list has no such entry.✦ The last masks of are the displacement masks of the caller’s box at the center of index , with the sample count of the environment as the scale: (2)
Let be the exact vector of in , the vector that the basic solver computes on , and . The base orientation of for the budgets is (3) On raw data, is the test whether the budgets give the set marked by measure above , and makes the choice of (3) with this test, from the mask of the coordinates with , the lower corner of .✦ The basic solver call runs the raw basic solver on the arena of the environment, the box and the basic step budget, and returns a raw vector.✦
The reduced budgets and are with the budget , respectively , replaced by its reduction , respectively , with the reduction factor . For raw vectors and and a raw box with corners , the clipped average is the raw vector of , where moves each coordinate into the interval between the corresponding coordinates of and . The extension of a raw orientation by two masks keeps its bit and appends and to its masks.✦
The Claim
Definition 1 (Orientation on the raw machine). Let be a machine input with random index , current pack , stack , caller pack and rest . The procedure Orient on the raw machine is given by the following cases, each the next state . On a call of , or : (4)✦ (5)✦ (6)✦ On a return to a frame , or : (7)✦ (8)✦ (9)✦ On a return to a frame or , with the last masks and of (2): (10)✦ (11)✦
In the paper, the result reads: for with , compute ; (O1) if , compute and , and return with the one-entry list if , otherwise with ; (O2) set , and , and for make independent calls and and set ; (O3) with and , return and if , else and if ; (O4) otherwise draw uniformly from with fresh bits, evaluate and return with the list followed by , where and are the reduced budgets. Here and are parameters of the paper, and stands for the measure of the budgets. On the machine, the case of makes the test of O1 and starts O2, the cases of , , , and make the moves of O2, and the cases of and make O3 and O4.
What Is Checked
The cases are stated over machine inputs with their environment, random index, packs and stack, and the facts below over a game at top width , a box of the solver at with midpoint , and a raw box .
The library shows that the raw operations of the cases represent the solver’s objects. Given budgets and a raw vector , the raw base orientation stands for (3): (12)✦
Take with and let . If the environment represents at , the narrowing gives the narrowed box, and the widening gives the widened box with no condition on the environment: (13)✦ (14)✦
For a point of with and a word of value , (15)✦ (16)✦
Let be a machine input whose caller’s box represents and whose current vector list represents a list of points of , and put for . Then for every counter (17)✦ and, when the environment of represents at , the last masks (2) mark the displacement sets at : (18)✦ (19)✦
Last, let for an orientation for , and let and be masks of two sets that an orientation for may have as exceptions. Then (20)✦