This session is based on an EM construal of the game of Nim (called nimLeeke2008) that was initially developed by Matthew Leeke (now a lecturer in Computer Science at Warwick). To display the construal, you can press the Expand button at the bottom left of the screen.
This model was submitted together with an associated paper to the Warwick Electronic Bulletin on Empirical Modelling (WEB-EM-4) as coursework for the annual Introduction to EM module given at Warwick.
This EMPE presentation is to be read in conjunction with the session handout. It includes the resources for a number of exercises that illustrate different ways in which the Nim construal can be explored and elaborated. For instance, it shows how nimLeeke2008 can be used to illustrate the winning strategy for Nim, based on the so-called Nim-Sum. Details of this strategy can be found from the Wikipedia entry for Nim.
"); s2 is Slide(" Introducing the nimLeeke2008 construalAn EM construal provides an interactive envionment in which to explore the way agents interact. We conceive such interaction in terms of observables to which an agent can respond.
Observables include any entity whose current status can be changed by an agent.
Possible agents include: the Nim players, the computer - which acts in response to actions on the part of a player, the model-builder.
The number of stones in pile 1 is an example of an observable - it is recorded as pileSizeOne. Different agents can change the value of pileSizeOne in different ways, according to their roles.
"); s3 is Slide("The model-builder can change the value of pileSizeOne directly.
A Nim player isn't allowed to change pileSizeOne directly. They are restricted to instructing the computer to change pileSizeOne by clicking on the \"Take from pile 1\" button.
Clicking on this button changes the value of the observable pileButtonOne_mouse_1.
"); s4 is Slide("The model includes actions for the computer to execute in response to changes to observables associated with mouse clicks.
This is the action that responds to changes to the observable pileButtonOne_mouse_1:
Dependency is a key concept in EM construals.
If, at the start of a turn, a player takes a stone from pile 1, then - as of that moment, without any independent action on the part of the player - it becomes impossible to select from piles 2 and 3. For the duration of the turn, pile 1 also has a special significance for the player.
The observable 'activePile' determines which pile - if any - is currently specially significant.
The colour of the 'Take from pile X' button is determined by dependency via the definition:
The action takePile1 only removes a stone from pile 1 when activePile has the value 1. This means that the impact of selecting a stone from pile 1 is instantaneously registered at the interface.
The size of pile 1 is displayed in decimal and in binary. The way these displays depend on pileSizeOne is expressed using definitions that you can find using the symbolviewer (see later).
"); s6 is Slide("
In real-life Nim, the players observe the rules without being explicitly constrained to obey them. For instance, it is physically possible to select from more than one pile.
Other irregular events might occur. Some stones may roll away or split into two. The players may get distracted and forget whose turn it is.
The support that the computer model gives for inspecting the Nim-Sum reflects what goes on in the imagination of the expert player.
The EM construal supports all these kinds of activity: things that can accidentally happen in the world, and things that can only be 'realised' in the virtual world.
"); s7 is Slide("In addition to using the EMPE and referring to the handout for this session, you will also find it useful to have access to a text editor. This will be necessary in order to inspect files to be introduced in the exercises.
The environment includes a basic symbolviewer that can also be used to view the observables in the Nim construal. This is accessed via the obsdetail display, where you can select Next and Previous observables. This takes the form of an auxiliary model that is linked by dependency to the Nim construal.
The Help tab on the EDEN Input Window is a useful source of information about the tkeden notations.
"); s8 is Slide("Nim is a game in which two players take turns to remove stones from piles of stones. At each turn, a player can take one or more stones from just one of the piles. The object of the game is to be the player who removes the last stone.
Exercise 1: Your first exercise is to familiarise yourselves with the game of Nim. For this purpose, you can use the variant of the construal that is derived by including the humanNim.js-e file:
As part of this exercise, you should reflect on the \'observables\' that are involved - many of which are implicit in the situation. For instance, the human players hold in their minds the answers to questions such as: Whose turn is it to play? Is the game over? Did my opponent cheat?
"); s9 is Slide("Exercise 2: Inspect the script that defines the first pile of stones within the humanNim.js-e file.
To restore the construal to its original state, we must re-introduce the initial script. Note that the button observables which relate to selecting from piles and starting a new game are common to both scripts. The actions associated with these observables are modified to reflect the different context in which they are being used.
Exercise 3: Study the way in which the %scout notation is used to specify the layout of the screen in the file Nim.s. Note the implications of making the following redefinitions of the observable 'screen' in %eden:
Exercise 3 (cont.): Study the way in which the %scout notation is used to specify the layout of the picture in the file Nimdisplay.js-e. Note the implications of making the following redefinitions of the observable \'picture\' :
Note the distinction between the environment for playing Nim that humanNim.e supplies and the computer interface that the last of the definitions of screen above affords. This interface maintains the integrity of the model by imposing program-like constraints on human action rather than relying on human discretion to respect the integrity of state. This is quite typical of the impact of computing technology on human affairs.
One of the features of EM is the way in which construals can be blended together by combining their scripts. This principle is illustrated by the way in which the representation of the piles of stones in humanNim.e can be imported into the Nim construal to replace the digital display of the pile sizes.
To this end, the file blendWinPiles.e can be introduced:
Exercise 4: Study the file blendWinPiles.e to see how the windows winPileOne, winPileTwo and winPileThree in which the piles of stones are displayed are transformed and relocated so that they can be integrated into the Nim construal. By applying the same principles to the Scout window backBox, as it is used in the last of the screen definitions specified in Exercise 3, introduce an observable displayBinaryRep that can be set to true or false to reveal and hide the information about the binary representations of the pile sizes.
It is true, but not obvious, that a situation in which the Nim-Sum of the piles is zero is lost with best play.
This situation arises when the current player's opponent has just picked up the last stone.
To prove that any other situation in which the Nim-Sum is zero is lost, it suffices to show that
This exploits inductive reasoning, whereby best play leads to the losing player being confronted with situations in which the Nim-Sum is zero, each time with fewer stones present than before. On this basis, the losing player eventually will have no stone left to remove.
"); s16 is Slide("A key observation is that if n numbers have Nim-Sum zero, then the value of each of the numbers can be inferred from the other n-1. Specifically, the value of the i-th number is that number whose binary representation is the Nim-Sum of the other n-1 numbers.
This observation is enough to show that any action taken when the Nim-Sum is zero renders the Nim-Sum non-zero, since it changes just one of the n numbers.
To prove the existence of an action that will transform a situation in which the Nim-Sum is non-zero into a situation where the Nim-Sum is zero, it is enough to show that there is an index i for which the number whose binary representation is the Nim-Sum of the other n-1 numbers is less than or equal to the i-th number.
For this purpose, we simple have to locate a number X that has 1 in its binary representation in the leftmost position k in which a 1 appears in the current Nim-Sum.
If the Nim-Sum of the n-1 numbers other than X has a 1 in any position to the left of k in its binary representation, then so does X, since the Nim-Sum has a 0 in this position.
"); s17 is Slide("Proofs are arrived at by considering many different situations and making observations. You may be able to follow a proof even though you don\'t know what observations went into its construction. This is similar to what happens when you use a program - what the user is allowed to explore is constrained by the programmer to be as safe and uncontroversial as possible. Quite a lot of experience of playing Nim might be required before the significance of zero Nim-Sum could be observed. This condition is here simply \'pulled-out-of-the-hat\'.
The Nim construal is reasonably well-suited to exploring and documenting the contexts for observation that play a role in arriving at a proof.
For instance, we can assign sizes to the piles at will:
Limitations are: the interface to the construal is clumsy and relatively inflexible when compared with pencil and paper. For instance, it would not be easy to generalise the construal to more than 3 piles, and the number of stones in each pile is limited to 15. Fortunately, the empirical evidence from studying this limited form of Nim is sufficient to infer general principles.
"); s18 is Slide("Exercise 5: Mathematical proofs are typically constructed through making conjectures and looking for evidence to confirm or refute them. Here are some assertions that came to mind in formulating a proof of the existence of a Nim winning strategy. See if you can find out whether they are valid, open questions or misconceptions.
To access answers to the questions on the previous slide, you can execute the following redefinition:
To hide answers to the questions on the previous slide, you can execute the following redefinition:
If appropriate, answers will be shown on the next slide.
"); s20 is Slide("These observations respectively disprove assertions 1 and 2. Taken together, they prove the validity of assertion 3.
"); s21 is Slide("Exercise 6:
Disposing the stones in 8-4-2-1 formation is interesting in cognitive terms. It makes it much easier to execute the winning strategy when playing Nim.
To test this out, you can load the file dispose_8_4_2_1.e which provides a solution to Exercise 6.5.