MENACE is the acronym of Donald Michie's Matchbox Educable Noughts-And-Crosses Engine. The construction of a MENACE construal is scaffolded using an extended presentation that makes use of the JSPE. (You may need to click the '>>' button in the JSPE panel to start the presentation.)
The idea behind the presentation is to trace the stream-of-thought that has been followed in building up resources that can aid understanding of MENACE, and can in principle be the basis for an emulation of its behaviour. As the presentation proceeds, a wide range of auxiliary issues that relate to making construals in general as well as to MENACE specifically are briefly reviewed and motivated. The aim of presenting the construal in this way is to show how (or determine whether!) schoolteachers with backgrounds in computing and mathematics can collaboratively compile teaching resources that both have independent interest and, when taken together, contribute to a fully developed construal that can help to explain and illustrate the principles behind MENACE. Were we to adopt a conventional approach to programming, writing an emulator for MENACE would perhaps be considered to be a relatively advanced topic. In making construals, we aspire to reduce the conventional programming content to the specification of functions and procedures in a basic procedural style in such a way that all functions and procedures are direct by-products of an application-oriented thought process. A relevant research question is \"to what extent can the difficulty in making a MENACE construal and associated emulator suitable for classroom use and experiment be reduced merely to understanding the principles of MENACE itself?\".
The development of the MENACE construal builds upon a pre-existing simple construal of the game of noughts-and-crosses which is a useful resource for teaching making construals in its own right.
There is provision in the presentation for this to be loaded from an online directory.
For convenience, to make the presentation more self-contained, a copy of the relevant file, called simpleNandC.js-e, will be explicitly included.
");
## the file: simpleNandC.js-e
x = 1;
o = -1;
u = 0;
boardstate = [u,u,u,u,u,u,u,u,u];
s1 is boardstate[1];
s2 is boardstate[2];
s3 is boardstate[3];
s4 is boardstate[4];
s5 is boardstate[5];
s6 is boardstate[6];
s7 is boardstate[7];
s8 is boardstate[8];
s9 is boardstate[9];
allsquares is boardstate;
WN is Point(100+size*0.5, 100+size*4.5);
NW is Point(100+size*2.5, 100+size*6.5);
NE is Point(100+size*4.5, 100+size*6.5);
EN is Point(100+size*6.5, 100+size*4.5);
ES is Point(100+size*6.5, 100+size*2.5);
SE is Point(100+size*4.5, 100+size*0.5);
SW is Point(100+size*2.5, 100+size*0.5);
WS is Point(100+size*0.5, 100+size*2.5);
sq1 is Point(100+size*1.5, 100+size*5.5);
sq2 is Point(100+size*3.5, 100+size*5.5);
sq3 is Point(100+size*5.5, 100+size*5.5);
sq4 is Point(100+size*1.5, 100+size*3.5);
sq5 is Point(100+size*3.5, 100+size*3.5);
sq6 is Point(100+size*5.5, 100+size*3.5);
sq7 is Point(100+size*1.5, 100+size*1.5);
sq8 is Point(100+size*3.5, 100+size*1.5);
sq9 is Point(100+size*5.5, 100+size*1.5);
WNEN is Line(WN.x,WN.y,EN.x,EN.y);
WSES is Line(WS.x,WS.y,ES.x,ES.y);
NWSW is Line(NW.x,NW.y,SW.x,SW.y);
NESE is Line(NE.x,NE.y,SE.x,SE.y);
picture is [WNEN, WSES, NWSW, NESE];
size = 40;
lab1 is (s7 == o) ? "O" : ((s7 == x) ? "X" : "");
piece1 is Text(lab1,sq1.x-10, sq1.y+10, "black", 32);
lab2 is (s8 == o) ? "O" : ((s8 == x) ? "X" : "");
piece2 is Text(lab2,sq2.x-10, sq2.y+10, "black", 32);
lab3 is (s9 == o) ? "O" : ((s9 == x) ? "X" : "");
piece3 is Text(lab3,sq3.x-10, sq3.y+10, "black", 32);
lab4 is (s4 == o) ? "O" : ((s4 == x) ? "X" : "");
piece4 is Text(lab4,sq4.x-10, sq4.y+10, "black", 32);
lab5 is (s5 == o) ? "O" : ((s5 == x) ? "X" : "");
piece5 is Text(lab5,sq5.x-10, sq5.y+10, "black", 32);
lab6 is (s6 == o) ? "O" : ((s6 == x) ? "X" : "");
piece6 is Text(lab6,sq6.x-10, sq6.y+10, "black", 32);
lab7 is (s1 == o) ? "O" : ((s1 == x) ? "X" : "");
piece7 is Text(lab7,sq7.x-10, sq7.y+10, "black", 32);
lab8 is (s2 == o) ? "O" : ((s2 == x) ? "X" : "");
piece8 is Text(lab8,sq8.x-10, sq8.y+10, "black", 32);
lab9 is (s3 == o) ? "O" : ((s3 == x) ? "X" : "");
piece9 is Text(lab9,sq9.x-10, sq9.y+10, "black", 32);
picture is [WNEN, WSES, NWSW, NESE, piece1, piece2, piece3, piece4, piece5, piece6, piece7, piece8, piece9];
near = 50;
mouseXnear1 is ((mouseX-160)*(mouseX-160)
The Matchbox Educable Noughts And Crosses Engine (MENACE) was devised by Prof Donald Michie ...
MENACE consists of an array of about 300 matchboxes each of which corresponds to a distinct position in a game of noughts-and-crosses.
Each matchbox contains a set of beads that are coloured-coded.
A bead of a particular colour corresponds to a possible move in the position represented by the matchbox.
MENACE 'plays' nought-and-crosses by identifying the matchbox corresponding to the current position, then selecting a bead at random from the matchbox, and making the corresponding move.
By monitoring the outcomes of games, the distribution of coloured beads in each matchbox can be adjusted to increase the probability of making a good move.
... some relevant references
";
html = html // dataRows[j][i];
html = html // " \n";
}
html = html // " \n";
}
html = html // "\n";
return Div(name, x, y, width, height, html);
}
buttonPrev is SlideButton("buttonPrev","<< Slide #" // str(currentSlide), jspeleft, 0, buttonPrevEnabled);
buttonNext is SlideButton("buttonNext",">>", jspeleft+150, 0, buttonNextEnabled);
## to protect against loss of information whilst constructing patterns
${{
var workIsDone = false;
window.onbeforeunload = confirmBrowseAway;
function confirmBrowseAway()
{
if (!workIsDone) {
return "Are you sure? If you leave this page now, your work will NOT be saved.";
}
};
}}$;
iggy4 is Slide("
About MENACE
In concept, MENACE is based on the idea that
As a first step towards making a computer model that helps us to understand more about MENACE, we'll first introduce a model of Noughts and Crosses.
On the default HTML5 canvas, there are some lines. They represent a grid on which you can play noughts and crosses. In the top left corner, there is a drop down menu in which you can select whether you wish to make a move for O or X (adding a 'nought' or a 'cross' to the grid). To play in a particular square, you simply click with the mouse near the centre of the square. Try playing a game ...
What you are interacting with when playing noughts and crosses in this environment is quite different from a traditional computer program. Perhaps you can think of some reasons why?
"); slideList is [iggy4, menace1, iggy5]; iggy5b is Slide("
Call this peculiar 'interactive artefact' a construal. Making a construal is based on principles altogether very different from writing a user-friendly program.
Cf. What are the principles of writing a user-friendly program?
Exercise: identify the observables in the construal that answer the above questions (if they exist!). If they don't exist, consider how you would introduce them. In each case, explain:
Note that the checkxwon and checkowon functions are generic - they determine whether a line of arbitrary length comprises only x's or only o's. The oline function was originally introduced with a view to eliminating complex procedural functions, and specifying dependencies simply with scripts.
"); slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a]; iggy8a is Slide("When we initially make a visualisation, we typically do this in a rough-and-ready way. Worth studying the way in which the noughts and crosses board has been constructed, and its limitations.
The exploration of a construal is an empirical activity, for which no prescription can be made. Identifying observables and finding observable names involves some idea of the naming conventions and an element of serendipity. Here's a possible way in which we can find out how the noughts-and-crosses board is constructed without any prior knowledge of the observables involved:
Several types of automated player are conceivable:
Exercises in the context of discussion of agency. What do we attend to when playing noughts-and-crosses? LSD notions.
And more ambitious than these approaches - incorporating machine-learning prospects: MENACE construal
"); slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a, iggy8a, iggy8c, iggy9]; menace2 is Slide("In MENACE each position is represented by a matchbox, and each possible move by a coloured bead with one of nine colours. It would not be feasible to construct an array of matchboxes so that every distinct position had its own matchbox. Michie optimises by taking into account the fact that many positions in N+C are the same up to symmetry. This makes the number of matchboxes manageable. It also has the effect of consolidating the information that is gained about what are essentially equivalent positions in one place.
It may well be possible to make a representation on a computer in which every possible position is distinguished. (I have not yet succeeeded in doing this!) There are arguments against doing this: apart from the consolidation of empirical data about moves that are not essentially different, there is a better chance that the human observer can appreciate the smaller model, and find more effective modes of visualisation and manipulation to understand their interaction with it.
Michie's matchbox-with-beads representation offers a natural concrete way in which to select a move in a given position (select a bead from the appropriate matchbox at random and make a move based on its colour), together with a mechanism for building in ways of changing the weighting associated with moves (increase the number of beads of a colour if it corresponds to a move with better winning prospects). It makes good sense to combine using MENACE to play the game at the same time as it is adapting its behaviour so as to reflect the end-results of its play. (We might like to call this 'learning' from 'experience'.) When imitating the MENACE principle with a computer, a conceptually simpler strategy can be adopted: the computer can be cast in the role of an observer who witnesses a very large number of games without participating and subsequently adjusts the weighting of moves so as to determine its own strategy of play.
"); slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a, iggy8a, iggy8c, iggy9, menace2]; menace3 is Slide("The first step towards making a construal for MENACE is to address the two broad needs: representing all the possible positions and moves in N+C, and setting up a way to simulate and record the paths taken in the course of suitably generated games.
A natural way to encode an N+C position is to interpret the o,x,u asociated with each cell as a -1,-0,1 value modulo 3, and to interpret the state of the board as a nine-digit ternary number in the range -9841 to +9841, where 9841 is the integer part of (3^9)/2. You can define an observable numpos associated with the position boardstate as follows:
The following script inverts this dependency: if ixpos is the index of some N+C position, then boardstateix it defines the associated board position.
The process of converting a script to a function can in principle be automated. In this way, framing a script can be regarded as a way to develop a program by making a construal.
"); slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a, iggy8a, iggy8c, iggy9, menace2, menace3, menace4]; menace5 is Slide("
You can improve the interface to suit a particular experimental purpose. For instance, numpos depends on boardstate, which can be changed manually by using the mouse. Initially, there's no provision for deleting O and X symbols by clicking in a cell, hence this redefinition:
A theme here might be configuration and instrumentation - customising the interface to a very specific targeted mode of observation and experiment cf. lab work.
Support for investigations, such as what is the largest value of numpos for which numpos is valid in N+C? What criterion can be used to determine the sign of numpos by inspecting the board? [Note the support that the construal gives for empirical study directed at solving such puzzles.]
Checking the Dependency Map first to be sure that there is no risk of creating a cyclic dependency, you can introduce the dependency:
Configuration can operate at many levels - for instance, can revise the JSPE interface:
The previous slides show how to associate an index with each position in Noughts and Crosses. The important observables associated with a position are: whose turn it is to move, whether or not the position is a terminal position, and what position is reached by playing in each of the nine squares, subject to its being unoccupied.
On the assumption that O plays first, we can identify the player whose turn it is via:
If the current position in a noughts-and-crosses game is recorded in 'boardstate', we can define the result of playing in each of the nine squares - with the convention that if a square is already occupied then the resulting boardstate is undefined (designated by '@'). To do this, we first define a function that returns a sublist of a list that is specified by given 'first' and 'last' indices:
There are two different kinds of ways of observing the move information. For purposes of calculating the sequence of positions followed in a game, it is useful to consider a move as mapping the number representing the initial position to the number representing the next position (if defined). For the purpose of displaying the information about what possible moves can be made, it is helpful to have a string representation that can be used in a tabular display.
"); slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a, iggy8a, iggy8c, iggy9, menace2, menace3, menace4, menace5, menace6, menace7]; menace8 is Slide("
To display the possible moves in a table, we exploit a prototype Table() constructor devised by Elizabeth Hudnott. Before introducing the table, we record the current state of the picture observable so that it can be easily recalled.
To display the information about the current position 'boardstate' as a row of a table:
With this display in place, it is possible to change the noughts-and-crosses position via the ComboBox on the Canvas and read off the information relating to this position in the table.
"); menace8a is Slide("
The table of possible positions to be considered is potentially a large table.
As set up so far, the table has a single entry which is dependent on the current value of 'boardstate'.
To set up the table so that we can record positions as we encounter them, we can introduce the following pattern of definitions:
This doesn't change the current value of the table observable, but makes it easy to add new rows.
For instance, if we make an assignment:
When using this technique to record the positions encountered in a noughts-and-crosses manually, it is convenient to recofigure the Combobox so that it alternates between the O and X defaults:
We convert information about positions into strings in order to inform the maker of the construal. Human interpretation of experience is so flexible that the maker may not even consciously register the distinction between seeing a 'O' in the top-left hand corner of the board and knowing that in the current position O has played in the first square, so that 'the value of s1 is o'. The purpose of making construals is in some respects to exploit and reinforce precisely this power of the human imagination to make associations without thinking about them. It may also be a valuable means to expose and challenge such unthinking associations.
When positions are to be processed by the computer, as (e.g.) in automating the generation of moves, it is appropriate to maintain observables with numerical values:
The function mkixpos is a modified form of mknumpos that handles an undefined argument more gracefully, explicitly returning a dummy value NONE. If mknumpos is used instead, the value of bsmoves evaluates to undefined.
At this point, it is possible to imagine writing a procedure to generate all noughts-and-crosses positions automatically but this may not be straightforward - or even feasible. My attempt to do this with coarse algorithms for list processing crashed the browser after generating more than a thousand distinct positions. Before introducing symmmetries to address this problem, we first consider a conceptually simple way to trace and record many games.
"); slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a, iggy8a, iggy8c, iggy9, menace1, menace2, menace3, menace4, menace5, menace6, menace7, menace8, menace8a, menace8b]; permnine1 is Slide("One way of generating a game of noughts and crosses is to enter Os and Xs as specified by a permutation of {1,2,3,4,5,6,7,8,9} until such time as the end of the game is reached. This is a possible way in which to generate the 'large number of games' to be witnessed by an observer who is going to adjust the weights attached to moves (as discussed previously). Generating games in this way will mean that the games that end after fewest moves will feature most often - there may be good reason to consider this advantageous.
Particular points of interest are:
The general idea is to set up scripts to make a correspondence between permutations of 9 symbols - in total 9!=362880 - and indices from 0 to 362879. One way to do this (this could be how I'm doing it below!) is to map the permutation that can be expressed (in a unique way) as a product of cycles: (123456789)^a * (12345678)^b * (1234567)^c * (123456)^d * (12345)^e * (1234)^f * (123)^g * (12)^h where a is in the range 0-8, b in the range 0-7 etc, to the number a*8!+b*7!+c*6!+d*5!+e*4!+f*3!+g*2!+h*1!
A permutation will be represented by a list in JS-EDEN. We require two functions, one of which may be in a JS-EDEN library:
The translation of a permutation of {1,2,3,4,5,6,7,8,9} to a sequence of numbers a,b,c,d,e,f,g,h that can be used to determine an index for it can be done simply by writing a function that takes a permutation of {1,2, .., n} and removes n to leave a permutation of {1,2, ..., n-1}. By applying this function to remove 9, 8, ..., 3 successively from an initial permutation you derive permutations of {1,2, .., n} for n = 8, 7, ..., 2. The location of n in each of these permutations supplies the coefficients a,b,c,d,e,f,g,h:
Entering the RE 'currperm|index' into a symbol list sets up an environment in which to test and refine the mapping from a permutation to an index. Assigning different values to currperm will show the value of indexcurrperm and the intermediate results used in computing this. Inspection shows that the indices of the permutations are in what can be deemed to be 'reverse' order, so that if currperm = [1,2,3,4,5,6,7,8,9] then indexcurrperm is 362879, and if currperm = [9,8,7,6,5,4,3,2,1] then indexcurrperm is 0. This can be remedied by revising the script:
Now if currperm = [1,2,3,4,5,6,7,8,9] then indexcurrperm is 0, and if currperm = [9,8,7,6,5,4,3,2,1] then indexcurrperm is 362879.
"); permnine5 is Slide("objects and constraints testing possibilities - can prevent conditions arising, or monitor and advise: natural ingredients of the test harness are developed in the course of making construals (but typically discarded) more appropriate to constrain as construals becomes mature
Playing a game of noughts-and-crosses based on a given permutation ('currperm') of {1,2,3,4,5,6,7,8,9} has the following component actions:
Starting a new game:
Making a move:
To trace the positions of the game in a table, and record the game in a list of games, we shall substitute another table to record games. For convenience, we record the current definition of picture, with the original form of the table to display lists of positions, at this point:
We can then embellish the definitions on the previous slide as follows:
Start the next game, first assigning a new value for currperm:
When the game is over, record the game and outcome in the list of games, and initiate a new game:
The prescription for tracing and recording games of noughts and crosses described on the previous slide is an interesting blend of manual ('human') and automated ('computer') interaction and interpretation. It illustrates what Steve Russ has characterised as 'human computing' (cf. the use of an abacus to perform a calculation). As an example, consider the instructions 'first assigning a new value for currperm' and 'when the game is over'. Such actions and interpretations can be of course automated, but there may be specific advantages in blending human and computer agency from a pedagogical or pragmatic perspective. As a teacher, we may need to be open-minded about the scope for misinterpretation on the part of a learner, for instance, and have to take account of this characteristically human behaviour.
With some basic knowledge of how to prescribe a procedure, it should be relatively straightforward to develop a fully automated procedure for playing and recording 'randomly generated' games of noughts-and-crosses.
One way to assign a random permutation of {1,2,3,4,5,6,7,8,9} to currperm for instance is to introduce the following function:
Relevant issues concern how best to conceptualise and to develop the MCE to support 'human computing'. An interesting alternative to thinking of the computer as a monolithic agent is to consider tasks such as 'starting a new game', 'making a move' etc as associated with different agents. Modulo a technical issue regarding the JS-EDEN interface, it is possible to enter conceptually different actions through separate Input Windows, for instance. A richer conceptual framework for making construals is provided by the 'Abstract Definitive Machine' - conceived 25 years ago, but only recently prototyped in its most appropriate form in JS-EDEN (by Ruth King in her WEB-EM-10 submission in January 2014).
The different qualities of the human and the computer in carrying out recipes are highlighted in the rest of the study of MENACE. Consider for instance, how the human calculator remembers whether something has already been calculated and may have noted the result (cf. memoisation), can perceive symmetries and shortcut calculation accordingly through on-the-fly translation and reinterpretation to eliminate redundancy, and can adapt calculation procedures in a pragmatic way using a different techniques for different instances etc. Much complexity in conventional programming relates to implementing the book-keeping that is associated with refining calculation processes so that they are feasible and efficient, and one pervasive ingredient in this is organising computation to ensure the maintenance of dependencies. There are limitations in the ways that functional programming attempts to address this through declarative variables (cf. smears of history to capture observables) and literate programming (cf. use of the JSPE).
"); ## space around < is needed in a JSPE context ## ## comments don't survive in aIn principle, the resources that we have developed to this point are sufficient to support some form of 'machine learning' such as we described in introducing the idea behind MENACE. Playing randomly generated games of noughts and crosses will clearly build a large inventory of games for which the sequence of moves and the outcome have been recorded. The space of positions is so large that generating comprehensive data is difficult - if not infeasible - with our current MCE, and the knowledge that can be inferred from games will probably be too sparse to yield an effective strategy. Following Michie's example, it is now appropriate to consolidate the data by taking account of the symmetries in the game of noughts-and-crosses.
"); slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a, iggy8a, iggy8c, iggy9, menace2, menace3, menace4, menace5, menace6, menace7, menace8, menace8a, menace8b, permnine1, permnine2, permnine3, permnine4, permnine5, gamesNandC1, gamesNandC1b, gamesNandC2, gamesNandC3, gamesNandC4]; symmetryNandC1 is Slide("
The symmetries of the noughts-and-crosses board (which - it should be borne in mind - not only permute the squares but also respect the winning lines) are the symmetries of the square, as defined by D8, the dihedral group of order 8. [D8 was coincidentally the subject of a study of groups of order 8 that made use of Web EDEN, the online precursor to JS-EDEN. For details, consult the Web EDEN presentations that display the multiplication table and illustrate subgroups and quotients of D8.]
The eight symmetries of a square comprise four rotations by through multiples of a right angle, and four symmetries that are obtained by first performing a reflection about the diagonal (a 'flip') followed by such a rotation. The rotations will be denoted by the observables elt1, eltR, eltR2 and eltR3 and the reflections followed by a rotation by eltF, eltFR, eltFR2 and eltFR3. When these symmetry operations act on the noughts-and-crosses board they permute the squares in the following way:
Two positions in the game of noughts-and-crosses will be regarded as essentially the same if one can be mapped to the other by applying one of the eight above symmetry operations.
"); symmetryNandC2 is Slide("
The group D8 can be represented by its list of elements:
The way in which a position is transformed by applying a symmetry operation is represented by the function mappos:
The general principle is that for each position we shall determine all the positions that are equivalent up to symmetry, and record the numerical indices of these positions in an ordered list. The assumption is being made that we are only concerned with positions that arise when O makes the first move. We use the largest index in the set as the 'canonical' representative for the symmetry class: to test whether two positions are the same up to symmetry we then only need to check whether the canonical representatives of their symmetry classes are the same.
"); ## continuity in stream of thought - don't have to attend carefuly to whether something has been said twice ## cf. the idempotence of relational data base assertions slideList is [iggy4, menace1, iggy5, iggy5b, iggy6, iggy7, iggy7a, iggy8a, iggy8c, iggy9, menace2, menace3, menace4, menace5, menace6, menace7, menace8, menace8a, menace8b, permnine1, permnine2, permnine3, permnine4, permnine5, gamesNandC1, gamesNandC1b, gamesNandC2, gamesNandC3, gamesNandC4, symmetryNandC1, symmetryNandC2]; symmetryNandC3 is Slide("
The ordered list of positions in a symmetry class is built up by inserting the elements one-by-one:
The statements in the body of the insertpos function correspond precisely to the various possible cases:
The following functions can then be used to compute the equivalence class for a position ('symclosure')
and the canonical representative within that class ('symrep'):
The simplest approach to the systematic generation of all possible positions involves repeatedly inserting into a list that initially contains only the empty position all the positions that can be reached by a single move from an element in the list until the length of the list becomes stable. This was infeasible without consideration of symmetry, but does work if applied with patience to the equivalence classes under symmetry.
To generate all the positions up to symmetry in this way, we initialise an observable 'poslist' to the list containing 0
- the index of the empty board.
We then extend poslist stage by stage by (in a very crude manner!) iterating through poslist element by element inserting
in the indices of those positions that can be reached by a single move in that position, as determined by setting the observable bsmoves to the appropriate value through manipulation of the observables ixpos, boardstate and boardstateix.
The procedure is derived from a manual process that was first played out by the maker of the construal and subsequently automated.
It is characteristic of procedures derived in this way that they are full of redundancy, inefficient, and use procedural constructs in an unsubtle way.
It is a fact that you should NOT attempt to verify (unless you have an hour or so to spare and don't mind locking up the browser)
that if you now keep repeating the generation of distinct classes of positions that are equivalent up to symmetry,
and monitor the contents and length ('poslistlen') of the list of positions generated ('poslist') by invoking:
This definition can be inspected more easily by first using the 'copy to input' option.
To get better access to the values of observables of this size, you can also write out the value using
and consult the answer as displayed in the console of the browser.
"); slideList is [iggy1, iggy2, iggy3, iggy4, iggy5, iggy5b, iggy5c, iggy6, iggy7, iggy7a, iggy8, iggy8a, iggy8b, iggy9, menace2, menace3, menace4, menace5, menace6, menace7, menace8, menace8a, menace8b, permnine1, permnine2, permnine3, permnine4, permnine5, gamesNandC1, gamesNandC2, gamesNandC3, gamesNandC4, symmetryNandC1, symmetryNandC2, symmetryNandC3, symmetryNandC4, symmetryNandC5]; symmetryNandC6 is Slide("The above approach directly constructs an ordered list of the positions up to symmetry. A more efficient way to generate all positions is to successively generate positions with 0,1,2, ...,9 symbols ('level 0', 'level 1', ...) and record a separate list for positions at each level. Functions that can be used to compute the positions at one level from the previous level are:
The positions can then be generated level by level in the ten observables:
By consulting the values of the observables poslevel1, poslevel2, ..., poslevel9, we find that the number of positions up to symmetry at each level is then
0: 1, 1: 3, 2: 12, 3: 38, 4: 108, 5: 174, 6: 204, 7: 153, 8: 57, 9: 15The observable allsympos has the value 765:
To single out the non-terminal positions, we can use:
To make up a table of rows comprising representatives of all the positions up to symmetry, we first initialise the tableNandCpos observable to an appropriate form:
To initialise the table:
Manual simulation to populate the table from the levels:
etc ... from which we can derive the following automatic procedure:
To populate the table from an initially empty currrowlist can then use:
As described it doesn't terminate quie correctly - the content of the table is in the observable rowlist,
so that the last row subject to change with bsrow. To fix this, use:
Assuming that poslist has been computed (or assigned) can [check this!] generate a sorted list of positions up to symmetry using:
| "; html = html // dataRows[j][i]; html = html // " | \n"; } html = html // "