Basic mechanics of Empirical Modelling

The object of Workshop 2 is to give you sufficient familiarity with the Web Eden environment to appreciate how the Sudoku model is constructed. This will enable you to understand how we shall exploit the model in Workshop 3. Your first task is to find out something about the basic principles and notations used in representing observables and framing definitions. You will do this by carrying out an activity that visits states associated with redefining observables in the Sudoku model, as in a guided walk ...

Guidelines for walkers

Taking a walk is a good analogy for exercising a Web Eden model. The starting point for today's walk is the initial state of the Sudoku model as it is when all definitions have been loaded. Though we shall visit states that are quite unrelated to Sudoku, we shan't make very many new definitions. (You might contrast our short walk with what would be involved in tracing the path from the empty set of definitions step by step to the current model, for instance, which is a very long and complicated walk.) You can either copy the pattern of definitions outlined in the next few pages very precisely, or invent variations of your own. You will be appreciating Empirical Modelling best if you take time and look around as you walk. It's good to experiment and be bold, but if you deviate from the specified path you may from time to time encounter errors and warnings. Most of the time, you will be able to recover from a problem introduced by a redefinition simply by restoring the previous definition (if you have had the foresight to find out what it was and make a note of it). If you really get lost, remember that you can always restart the model by refreshing the browser.

Observables in the Sudoku model

The most obvious observables in the Sudoku model are those associated with the grid itself. For instance, each of the 81 cells in the grid has a size, a location, a background colour, a content and a foreground colour in which this content is displayed. Each of these observables has a direct counterpart in the model. A typical cell is a small window in itself (e.g. D3 is the cell in the 3rd row and the 4th column), its background colour is D3_bgcolour - in this case "white", its content is the string d3 comprising the single character "7", and its foreground colour is "red". The definitions that describe the display aspects of the Sudoku model are expressed in the Scout notation. If the tab at the bottom left does not show "scout", such definitions must be preceded by a "cout" before th ey are entered into the input window.

Modifying the display

The content of the display panel labelled "screen" corresponds directly to an observable in Scout. For instance, paste the following definition into the Input Window, and press Accept:

%scout

screen = <A1/B1> ;

and you will see that the Sudoku grid is replaced by the two adjacent cells in the top left of the grid. Follow this by entering the definitions:

A1_bgcolour = "red"; B1_fgcolour = "white";

and the background colour of the cell A1 and the foreground colour of B1 will change appropriately. Note that a redefinition of an existing observable replaces its old definition. Confirm this by entering the definition:

B1_fgcolour = A1_bgcolour;

You can show the dependency this creates by redefining:

A1_bgcolour = "green";

Exercise 1: A basic exercise in Empirical Modelling

Empirical Modelling is based upon framing definitions that precisely express the intended and expected relationships between observables. On the next page you will find a sequence of six Scout redefinitions that you can use to develop this basic skill. You should process these redefinitions in two ways:

i. Without using the Web Eden interpreter, imagine making each of the specified redefinitions one by one, and write down what you expect to happen.

ii. Paste the definitions 1-6 into the Input Window one by one and observe what happens.

If there's any discrepancy between what happened and what you imagined would happen, explain this by reconsidering step i. Then re-enter the definitions, modified as and if appropriate, so as to confirm or refute your explanation.

The six example Scout redefinitions for Exercise 1

1. B1_bgcolour = A1_fgcolour; B1_fgcolour = A1_bgcolour; A1_bgcolour = "white";

2. a1 = b1; b1 = "2"; ## a1 and b1 are of type string - hence the quotes around 2

3. A1_bgcolour = B1_bgcolour;

4. A1_fgcolour = B1_fgcolour;

5. A1_bgcolour = if (a1=="2") then "red" else B1_bgcolour endif; ## '==' stands for 'equals'

6. A1_fgcolour = "#38c755";

The number used to specify the foreground colour of window A1 is a hexadecimal. How might you be expected to know approximately what colour to expect without executing the definition?

Lessons to be learnt from the Exercise 1

From the exercise, you can observe the following

- repeating the same definition doesn't change the state
- the definition x=y means that if y changes, x becomes equal to y
- the definition x=y doesn't mean that if x changes, y becomes equal to x
- a definition can't be cyclic: an observable can't be directly or indirectly defined in terms of itself: but you can safely ignore the error message as a definition that introduces cyclicity will simply be ignored

(If you have time to repeat Exercise 1, first clicking on the cell B1 prior to performing the sequence of six sample definitions, you get very different results. The difficulties of prediction in open environments are notorious - they relate to the so-called Frame Problem in AI. Can you explain what happens?)

Other kinds of observable

There are other ways in which we can observe the Sudoku grid. We can think about the grid as a table with rows, columns and regions for instance. Quite different kinds of notation and structure are required for this purpose. This is supplied in the Web Eden environment by the Eddi notation. Before we can illustrate Eddi, we have to "retrace our steps" by restoring the original definitions to the screen and the two cells A1 and B1. The definitions you need for this purpose can be found on the next page. These are in small font - for several reasons: so that you can readily cut and paste them into the Input Window, you don't feel you need to read them, and you get some informal appreciation of the intricacy of the original definitions in the Sudoku model.

Definitions needed to restore the screen display to the state it was in originally

%eden

A1_fgcolour is a1_fixed ? SD_fixed_fgcolour : SD_fgcolour;

A1_bgcolour is a1_focus ? SD_focus_colour : ( ((current_row==1) || (current_col==1) || ( (current_row * current_col !=0) && (current_rowband==1) && (current_colband==1) ) ) ? SD_relevant_colour : SD_bgcolour);

B1_fgcolour is b1_fixed?SD_fixed_fgcolour:SD_fgcolour;

B1_bgcolour is b1_focus ? SD_focus_colour : ( ((current_row==1) || (current_col==2) || ( (current_row * current_col !=0) && (current_rowband==1) && (current_colband==1) ) ) ? SD_relevant_colour : SD_bgcolour);

a1 is mkstr(a_1);

b1 is mkstr(b_1);

screen is grid;

Notice the initial %eden - this indicates that these definitions are expressed in the Eden notation, rather than in Scout. This is possible because whatever notation you use is translated into Eden internally. (If it's simpler, you can restart the model at this point.)

Observing rows, columns and regions in the grid

Many features of the Sudoku puzzle relate to the structure of the grid. Information about rows, columns and regions is all conveniently recorded using tables. In the Eddi notation, we can define observables whose values are tables, and where the definitions use operations on tables. An Eddi observable X can be an explicit table, or be defined by a formula in terms of other table observables. To see the current value of (the hypothetical!) table observable X, you type*

%eddi

?X;

To see the current definition of X, you can use a query of the form ??X;

*NB Cutting and pasting a "%eddi" into the Input Window effectively pastes "%eddi " into the input. Due to a glitch in the underlying Eden interpreter, the presence of this space means that no switch to the Eddi notation is recognised. To fix this, you should either type the "%eddi" into the input window yourself, or - if you paste a "%eddi " into the window, remove the final space manually. To remind you of this, subsequent instances of "%eddi" are highlighted in red.

Tables in Eddi

The digits in the Sudoku grid are recorded in a table. Each row in this table (not to be confused with a row in the Sudoku grid) consists of a "tuple" of numbers (rowix, colix, digit, status). Here rowix (which row?) and colix ( which column?) specify the grid coordinates, digit the value at this location (in the range 0-9), and status whether or not the value is given in the puzzle or not. You can confirm this by querying the value of the observable sudokugrid:

%eddi

?sudokugrid;

to get the output as a table with 81 rows. The table header is:

---------------------------------

rowix | colix | digit | status |

---------------------------------

... and the first three rows are:

1 | 1 | 4 | 0 |

1 | 2 | 6 | 1 |

1 | 3 | 8 | 1 |

Some basic Eddi operations ...

The formula that define tables use simple operations. Some of these look just like ordinary arithmetic operators, such as plus (+) or minus (-), though they of course have different meanings! Two other operators (: and before you execute it (... and if necessary afterwards!)

Table observables defined by formulae ...

The digits in each row and column of the Sudoku grid are recorded in table observables:

%eddi

?row3;

?col4;

You may find it useful in interpreting these definitions to select the cell D3 on the grid, and compare the representation of a row and a column in the two tables. These row and column observables are defined by formulae:

??row3;

??col4;

From such a query you can find out the definition of row3:

row3 is sudokugrid : rowix == 3 olix, digit

Some sample queries to illustrate the : and 0perations

(Be sure to precede all queries by %eddi observing the NB on the foot of page 10! )

1. ?sudokugrid : digit>0;

2 . ?sudokugrid : colix==4

3. ?sudokugrid : colix==4 0igit;

4. ?sudokugrid : status == 1 : digit == 6

5. ?sudokugrid : status == 1 : colix == 4

Further table operators and definitions ...

It remains to consider other Eddi operators. The operator + ("union") combines the contents of two tables in a single table, whilst - ("difference") takes the contents of one table from another. The intersection of two tables A and B - the table of tuples that are common to A and B - is specified by A.B. These operators feature in defining other Eddi tables in the Sudoku model, such as record the digits in particular regions. You can query the definitions of some of these tables:

%eddi

??region4digits;

region4digits is (rowband2 . colband1) 0igit

??rowband1;

rowband1 is ((sudokugrid : rowix > 0).(sudokugrid : rowix < 4)) : digit>0

??possdig21;

possdig21 is (all - all21) - (region1digits + (row2 : digit>0 0igit) + (col1 : digit>0 0igit))

Exercise 2

1. What information does the following Eddi query return?

%eddi

?all - sudokugrid : colix==4 0igit;

2. How would you formulate a query to return the digits not in row 6 and not in column 7?

3. What does the observable rowband1 describe? Why is the definition of rowband1 on the previous page not a very good one?

4. Make your own definition of a new table called top3rows that defines the same result as rowband1 but uses a formula that contains '+' rather than '.'. Do you in fact need to use either '+' or '.'?

5. Interpret the definition of the observable possdig12 on the previous page. Why doesn't it always exactly correspond to "the set of plausible digits for the cell B1"?

PS It has been pointed out to me that questions 3 and (especially as now revised) 4 make more sense if you substitute rowband2 for rowband1, and consider defining a new table called mid3rows etc!

What we've illustrated about the Sudoku model

Through our 'guided walk', you have been introduced to two quite different ways of observing the Sudokugrid. It has been helpful to use quite different notations to express these observables and the dependencies that connect them using definitions. In practice, a lot of significant connections between observables link observables of quite different kinds. For instance, the number that is placed in cell D2 is recorded by an observable d_2 in the Sudoku model that isn't defined either in Scout (it isn't a visual component) or in Eddi (it isn't a table). Yet changing the value of d_2 affects the screen display, and the contents of the sudokugrid table.

Putting it all together

The challenge of integrating many different ways of observing the world and of representing data is fundamental to the work of the computer scientist. It presents profound problems, technical - to do with how computers store and manipulate data, social - to do with how different people view the world and human activities within it, and even philosophical. It is as if - in building a complex system - the software engineer not only has to worry about whether people like butter or margarine on their toast but also whether to treat light as made up of particles or waves. In Empirical Modelling, as illustrated in the Sudoku model, the aspiration is to allow all these modes of observation to co-exist, even if sometimes - necessarily - a little incoherently. As we have seen, depending on how you interact with a model, you can observe it in different ways. Some indication of how we can munge these various views together is given in the Workshop 2B.