Applying Empirical Modelling in practice

So far, the emphasis has been on explaining how Empirical Modelling concepts lead us to think afresh about computer programming and use. For that purpose, we've been focusing on how the computer model supports our interaction by maintaining significant relationships between observables. These ideas connect with traditional programming and come to life when we consider how the computer itself can act as an agent. For the first part of this workshop, you can close the Sudoku grid window and associated button menu, and just interact via the Input and Output windows.

Cricketing concepts revisited

In introducing Web Eden, we discussed a simple set of observables and definitions that recorded information about a batsman's innings. It made use of integer observables in Eden:

- a = 199; ## total runs scored
- b = 20; ## how many fours
- c = 1; ## how many sixes
- d is b*4 + 6*c; ## runs scored in boundaries
- e is a - d; ## runs in non-boundaries
- f = 336; ## balls faced
- g is float(a)/f *100; ## strike rate: runs per 100 balls
- writeln(e);
- writeln(g);

Adding agency to the cricket model

The simple model of a batsmen's innings does not illustrate Empirical Modelling to its full advantage unless we think of it in the context of an actual ongoing innings. In that setting, the fundamental state change occurs when the batsman faces the next ball. Everything else, the batsman's total, the number of balls faced, the strike rate are all derived from whether this ball yields 0,1,2,3,4,5 or 6 runs. The point of modelling with definitions is to ensure that this idea of a single conceptual action having many effects can be appropriately captured.

Exercise 1

Before reading on, think about what needs to change when a single ball is played by a batsman. Take a few minutes to reflect on what single observable can be used to account for the changes to all of these observables.

Extending the model

To extend the model we introduce a new observable: the scoring record. This is a list of the kind that gets recorded in the official scorebook. It indicates what happens to every ball faced by each batsman. For instance, the scoring record of a batsman at the present moment might be something like:

scoring_record = [0, 0, 1, 2, 4, 0, 0, 1, 3, 6, 4, 0, 0, 1];

After the next ball, the scoring record will have changed by the addition of a single entry to the end of this list. Before reading on, consider how you would be able to derive each of the observables a,b,c and f from the scoring record. Note carefully that whether you know how to express this in computer code is a separate issue - the most important thing to grasp initially is that (e.g.) the number of balls faced (f) is the length of the scoring record.

How the observables depend on the scoring record

The current total a is the sum of the entries in the scoring record. The number of fours b and number of sixes c can be calculated by inspecting the scoring record and counting occurrences of fours and sixes. The other observables d, e and g are already defined in terms of a, b, c and f. There aren't standard operators (like addition of integers, union of tables and composition of strings) to express these definitions. To do this we have to write a small program in a traditional style ...

An Eden function to relate a, b and c to the scoring record

Here is a suitable Eden function to calculate the total and the number of fours and sixes from the scoring record.

%eden

## Eden function to compute key statistics from the scoring record

func calculatescores {

para s_r; ## this is the input for the calculation

auto i, total, fours, sixes;

total = fours = sixes = 0;

for (i=1; i<=s_r#; i++) { ## this looks at each element of s_r in turn

total = total+s_r[i]; ## adding up the entries to get the total

if (s_r[i]==4) fours++; ## counting the fours

if (s_r[i]==6) sixes++; ## counting the sixes

}

return [total, fours, sixes]; ## this is the ouput

## the result of the calculation is expressed as a list of three values

}

The extended scoring model

To complete our scoring model, we can now redefine a, b, c and f:

- a is calculatescores(scoring_record)[1];
- b is calculatescores(scoring_record)[2];
- c is calculatescores(scoring_record)[3];
- f is scoring_record #;

The dynamic scoring model

The introduction of the extra observable scoring_record and the new definitions creates a model that can be used dynamically in the context of a game in progress. To check this out you can enter via the Input Window (if you have not already done so)

- the original definitions of the observables a,b,c,d,e,f and g given on p2
- the additional observable scoring_record defined on p5
- the Eden function calculatescores() given on p7
- the revised definitions of a,b,c and f on the previous page
- the Eden action currentstats() that is specified on p12 (to be discussed later)

Using the model

To use the model, you simply update the scoring record observable ball by ball. This can be done by making an assignment of the following form to tack a new value on to the end of the list:

scoring_record = scoring_record // [ number_of_runs_of_next_ball ];

where you substitute 0,1,2,3,4,5 or 6 for the number_of_runs_off_next_ball. For instance:

scoring_record = scoring_record // [4];

will register that the next ball has been hit for a 4. To confirm that updating scoring_record updates all the other observables in the model you can use the query:

?scoring_record;

and consult the list of observables defined in terms of scoring_record that is then displayed.

Automating human agency

Notice that in extending the scoring record you act in a purely routine rule-based way. You see what the batsman scores from the ball, then add this value to the list. Not everything we do as agents can be automated (e.g. how could we program a computer to develop the Sudoku model?), but some human agency can be captured as 'when you observe this, do that'. This motivates the introduction of computer agents specified on the same pattern ...

A computer agent to update the scoreboard

Here is the form of the simple 'agent' in Eden that writes out the vital statistics of an innings ball-by-ball:

%eden

## Eden action triggered by observing a change to the scoring record

proc currentstats: scoring_record {

writeln("nCurrent total ", a);

writeln("Non-boundary runs = ", e);

writeln("Strike rate = ", g);

}

With this agent in your model, the statistics will be redisplayed every time the scoring record observable is updated.

An agent to assist Sudoku solving

We can apply the same principle of automating routine human agency to help in solving a Sudoku puzzle. (You can now restore the sudokuGrid and buttonMenu using the Windows/Scout screens tab on the main menu.) For instance, when we observe that a cell is empty and the number of plausibles is 1, we can enter the only plausible digit into that cell. Take a few minutes to consider how this routine action might be expressed as an Eden action. The important point is to be able to recognise what observables and redefinitions are involved, even if you can't write the actual code. You may find it useful to revisit the discussion of plausibles in Workshop 2C at this point.

Exercise 2

The following template defines a suitable Eden agent that will insert a digit in the cell D1 when there is no other candidate for that cell:

proc D1_checkonedigit: ... {

if ((...) && (...) ) ## the && stands for 'and'

d_1 = possdigit14[1][1];

}

Your task is to supply

- the missing observable that is required to trigger the update
- the missing conditions that have to be substituted in the brackets after the if

Hints on Exercise 2

- To identify a suitable trigger observable, think about what might affect whether or not there is a single plausible digit for the cell D1. Putting a value in the cell B1 or the cell D3 would be examples of relevant observables. You only need a single observable though!
- To identify the conditions, first think about what properties the cell D1 must have in order for it to make sense to put a single digit in it.
- Once you've identified this information informally, you should think what specific observables in the Sudoku model to use, and how to formulate simple conditions involving them. For instance, to get the action to trigger when the value in cell D3 changes, you might add the trigger d_3. A example of a - in general most unsuitable! - condition would be d_3 != 8 (where "!=" means "is not equal to"). Note that, as shown in the template via (...), you have to enclose such a condition in round brackets.

Making use of agents in Sudoku solving

Having created an agent that will successfully insert a digit in D1 when there is only one plausible for it (as is the case e.g. in puzzle 1), you can make replica agents for all the other 80 cells! For an easy puzzle such as puzzle 1, it's possible that this will lead directly to automatic solution as soon as you load the grid.

Towards more advanced solving methods

A way to support the other simple pattern of reasoning commonly used in Sudoku solving was outlined in Workshop 3A (see p19). This pattern involves checking whether there is only cell within a given row, column or region where a digit may be placed. As explained in Workshop 3A, it is possible to make this check semi-automatically using the model. To do this for the digit 3 in row 4 (say), you first inspect the number of plausibles for all cells in row 4 (as defined by observables within the model), then redefine the table 'all' , comprising the digits from 1 to 9, so that 3 is omitted. By applying suitable criterion you devised in Workshop 3A, you can then spot where the most simple deductions apply.

Automating patterns of reasoning

The "Check row/column/region" buttons on the button menu demonstrate the crude automation of the two basic techniques for filling cells described on p19 of Workshop 3A in action. It is crude because it relies simply on repeating the manual checking procedure, as used on the prevous page to identify where 3s can be entered in row 4, for each possible digit and each row, column and region in turn.

Exercise 3

Why is it so inefficient to directly imitate the check on counts of plausibles that we might carry out for each digit, and each row, column and region in turn? [Hint: consider how many observables in the Sudoku model get to be updated when the observable 'all' is changed. For this purpose, you can inspect the observables that are defined in terms of 'all' - using

%eden

?all;

(cf. the way that such a query was applied to the observable scoring_record on p10). This suggests that you don't want to redefine 'all' more times than is absolutely necessary!]

Towards more efficient automation

This final section will sketch how you might go about building an alternative implementation that is much more efficient. To follow this sketch some conventional programming knowledge will be useful, but the approach has been developed so that you only need to know a relatively simple set of programming constructs. (Only the case of checking rows is considered in the sketch, but the generalisation to columns and regions is not difficult.)

Step 1: Computing the effect of changing 'all' on the plausible counts for all cells

As described in Workshop 3A, the number of plausibles for each cell in the grid is stored in the Eden observable rowcounts. The following function will compute the difference between the values in the list rowcounts before and after discounting the digit dig:

func diffcountlist {

para dig;

auto ix, jx, result;

result = rowcounts;

all = difference(all, [[["int"], "digit"], [dig]]);

## writeln(all);

for (ix = 1; ix<=9; ix++)

for (jx = 1; jx<=9; jx++) {

result[ix][jx] = result[ix][jx]-rowcounts[ix][jx];

}

all = [[["int"],"digit"],[1],[2],[3],[4],[5],[6],[7],[8],[9]];

return(result);

}

Displaying the counts of plausibles before and after changing 'all'

The Eden observable rowcounts is stored as a list of nine lists (corresponding to the nine rows), each of which is itself a list of nine values (corresponding to the cells in each row). This is hard to read from the output. To display the counts of plausibles in a table, and the changes to which these are subject when the digit associated with the Eden observable currdigit is discounted, you can introduce the following definitions, remembering to remove the space in the "%eddi " if you cut and paste!

%eddi

counttable(dig1 int, dig2 int, dig3 int, dig4 int, dig5 int,dig6 int, dig7 int, dig8 int, dig9 int);

diffcounttable(dig1 int, dig2 int, dig3 int, dig4 int, dig5 int,dig6 int, dig7 int, dig8 int, dig9 int);

%eden

countt0 = counttable;

counttable is countt0 // rowcounts;

currdigit = 3;

currdiffcountlist is diffcountlist(currdigit);

diffcounttable is countt0 // currdiffcountlist ;

To inspect the tables counttable and diffcounttable you can use:

%eddi

?counttable

?diffcounttable;

Deciding whether a given digit has just one place in a row

How do you know whether there's just one place for a digit in a particular row? This is the answer to Exercise 4 on p14 of Workshop 3A. Without spelling out the answer, here's an Eden function findix which can be applied to each of the rows of the diffcounttable to decide whether or not the digit currdigit can be placed in the corresponding row of the grid. As its name suggests, findix will compute the index of the column in which the digit must be placed if there is just one place, and otherwise returns the value 0.

%eden

func findix {

para boollist9; ## the list of 0s and 1s in a row of the diffcounttable

auto i, sum, result;

sum = 0;

for (i=1; i<=boollist9#; i++) {

sum = sum + boollist9[i]; ## sum the entries in the row

if (boollist9[i]>0) result=i; ## record where the last 1 in the row occurs

}

return (sum==1) ? result : 0; ## if there's just one 1 return its location

}

## ... and here are some tests that show findix in action:

writeln(findix([0,0,0,0,0,0,0,0,0]));

writeln(findix([0,1,0,0,0,0,1,0,0]));

writeln(findix([0,1,0,0,0,0,0,0,0]));

writeln(findix([0,0,0,0,0,0,1,0,0]));

Putting it all together

When we have a particular digit in mind (currdigit), we can determine where (if anywhere) this digit can be uniquely located in the each of the nine rows. The observable

currdiffcountlist is diffcountlist(currdigit);

defined on p22 records the differences in counts of plausibles before and after discounting the digit currdigit.

We can set up an observable for each row to record the specified location for currdigit. For instance, for row 3, a suitable definition is:

pos_in_row_3 is findix(currdiffcountlist[3]);

Suppose that the digit that we're currently trying to locate is 5:

currdigit = 5;

The value of pos_in_row_3 will then be column index of the unique cell in which 5 can be placed (if that exists) or 0. At this stage, you should make a further eight modified copies of the pos_in_row_3 definition to deal with trying to locate the current digit in the remaining rows.

Displaying the result

To define an appropriate message to output the information about where we can place the current digit in row 3, we can define a string:

info_row_3 is (pos_in_row_3==0)? "" : ("nIn row 3 there's a " // str(currdigit) // " in column " // str(pos_in_row_3));

You should now replicate this information for the other eight digits in a similar way, and combine the information for all the rows into a single message:

message is "nRow information:" // info_row_1 // info_row_2 // info_row_3 // info_row_4 // info_row_5 // info_row_6 // info_row_7 // info_row_8 // info_row_9 // "n********************************";

To display this message in the output window every time it needs to be updated, you can introduce an agent:

proc wmessage : message {

writeln(message);

}

The Very End

This is the end of Workshop 3. Please fill out the Feedback 3 form on the Sudoku Experience website - when it arrives there.