SOME DETAILS
OF THE MACHINE

Its size is 12 feet x 5 feet x 9 feet but these figures are very misleading since most of this space is used for display purposes only. In fact less than 2% of the whole volume is taken up by the actual computer.

There are 480 electronic valves in the machine which are used in the computer itself, for display purposes and in "conditioning" circuits in which valves are "aged" before going into service, the effective number of valves in the computer being about 350. All the electronic valves are double triode of the 12AT7 type and a number of germanium crystal rectifiers are employed mainly for the purpose of D.C. restoration.

Most of the components are worked at a small fraction of their maximum rating in order to try to improve their life.

Normally high frequency supplies would be used but in Nimrod single phase 50 c.p.s. has been used throughout. D.C. supplies use silenium rectifiers and normal choke-capacitance filters, the chokes being specially designed in order to obtain good regulation. The A.C. mains are stabilised to within 1 % by an automatic induction regulator. All power supplies and heaters are switched on slowly by means of a cascade of thermal delay switches.

The conventional computer uses pulses to represent numbers but Nimrod uses voltage levels instead. Thus it is possible to have slow speed demonstrations which are extremely useful when the programme of instructions is being explained. During these slow demonstrations the list of instructions on the front display (see page 00) is illuminated, each instruction being illuminated just for the period during which that instruction is being obeyed. (It is also made possible for the demonstrator to go through the instructions one by one at any good speed which he requires by means of a manual push-button which causes a single instruction to be obeyed each time it is pressed).

A further part of the display contains the following statements which can be lit as required:

(1) Opponent wins.

(2) Computer wins.

(3) Opponent's move.

(4) Opponent has moved, computer will now move.

(5) Computer's move.

The last is only lit on slow and manual operation and during self play when computer and opponent are considered to be two players.

 

NIM

This game has been played throughout the world for many centuries but only recently has the game been analysed mathematically. This analysis is beyond the scope of this booklet which is concerned with computers and not with the theory of games. It is sufficient to know that there is a reliable "rule of thumb" method for playing the game and this is the method used by Nimrod in making its moves.

Many variations of Nim are possible and Nimrod is able to play any of them but for the present we shall confine ourselves to the simple game. The game is for two players, being played nowadays with matches. At the beginning of the game one of the players arranges the matches in any number of heaps in any way he chooses. The players then move alternatively taking any number of matches from any one heap but at least one match must always be taken. In the normal simple game the player who succeeds in taking the last few matches wins but in the reverse simple game the player who takes the last match or matches looses.

After each move a player leaves a combination of matches which may be "safe" or "unsafe." If he leaves a "safe" combination then his opponent is unable to make a correct move as any move which he makes will result in an "unsafe" combination. If he leaves an "unsafe" combination then it is possible for his opponent to make a correct move and leave a "safe" combination. Thus if both players know the correct method of play, the player who arranges the matches at the beginning of the game is sure to win unless he makes an incorrect move at some time. We shall now consider the steps which must be taken to ensure that an "unsafe" combination is operated on in the correct fashion to produce a "safe" combination. For this purpose it is necessary to make use of binary numbers which are discussed in the glossary. Thus the game of Nim is particularly suited to the use of the usual binary computing elements.

Suppose that you are confronted with a combination which is "unsafe" for your opponent, e.g., for heaps of matches containing 7, 1, 6 and 2 matches respectively. First express the number of matches in each heap in binary form:- i.e.

7 is expressed as 1 1 1
1 ,,   ,,   ,, 0 0 1
6 ,,   ,,   ,, 1 1 0
2 ,,   ,,   ,, 0 1 0

(The zero digits are inserted on the left to keep all binary numbers equal in length).

These binary numbers are then arranged in columns thus :--


Column 2 Column 1 Column 0
Heap 0 1 1 1
Heap 1 0 0 1
Heap 2 1 1 0
Heap 3 0 1 0

Now examine the sum of the column on the left i.e., in this example column 2. If the sum is even, as in this example, this column is "safe" and it should remain unaltered. The sum of column 1 is then examined to see whether it is odd or even. Our example gives an odd sum for column 1 and this is "unsafe." It is therefore necessary to modify one of the heaps so that the sum of this column becomes safe. This is done by choosing a heap which has a 1 digit in column 1 and changing it into a 0. Heap 2 could be selected and so the 1 digit in heap 2 and column 1 is replaced by a 0. When a 1 digit is replaced by a 0 in this manner the digits to the right of the modified number must also be changed into I's. Therefore the number of matches in heap 2 is changed from 110 to 101. The resultant arrangement of matches in binary columns will now be


Column 2 Column 1 Column 0
Heap 0 1 1 1
Heap 1 0 0 1
Heap 2 1 0 1
Heap 3 0 1 0

Both columns 2 and 1 are now "safe" so we pass on to column 0 and examine its sum. The sum is 3 and thus column 0 is "unsafe." It is made "safe" by modifying heap 2 again since we are restricted in the simple game to removing matches from only one heap at a time. The number 101 in heap 2 is changed to 100 giving the final arrangement which is a "safe" combination.


Column 2 Column 1 Column 0
Heap 0 1 1 1
Heap 1 0 0 1
Heap 2 1 0 0
Heap 3 0 1 0

In the above fashion the "unsafe" arrangement of four heaps of matches containing 7, 1, 6 and 2 matches respectively has been changed into the "safe" arrangement of 4 heaps of matches containing 7, 1, 4 and 2 matches respectively.

The rules for playing the normal simple game correctly may be in general stated as follows:— Express the contents of each heap in binary form and arrange the binary numbers obtained in this way in columns. Find the sum of the column on the extreme left. If this sum is even pass on to the next column on the right. If the sum is odd then choose a heap which contains a 1 digit in this column and modify it. Modification of a heap is always carried out in the same fashion, the 1 digit in the column under consideration being replaced by a 0, the digits to the right of this column being replaced by I's and the digits to the left of this column being unaltered. After a heap has been modified go to the next column and obtain its sum. If the sum is even continue to the next column but if the sum is odd the heap which was previously modified must be re-modified before passing to the next column on the right. This is repeated until all the columns have been inspected and all the necessary modifications made so that the sum of every column is even and the correct move has therefore been made.

If the inspection of columns shows that every column is "safe" then it is impossible to make any move which will result in a "safe" combination and a move must be made at random.

The rules for the reverse simple game are identical to the above rules until a certain stage known as "transition" is reached. This occurs when there is only one heap or no heaps containing more than one match. After this point has been reached the new rule is to leave either one heap or three heaps containing only one match.

To illustrate this we will take an example and go through a reverse simple game move by move. Let us name the two players A and B and assume that B has set up four heaps at the beginning of the game so that they contain 7, 1, 6 and 4 matches respectively.

Move 1. (To be made by A)
  Heap 0
Heap 1
Heap 2
Heap 3
111
001
110
100
 

The sum of column 2 is 3 and a heap must therefore be modified. A selects heap 2 and changes its contents from 110 to 011. The arrangement then becomes

    111
001
011 (Modified)
100
 

The sum of column 1 is 2 so A passes on to column 0. The sum of column 0 is 3. Therefore A re-modified heap 2 i.e., he replaces 011 by 010 leaving the arrangement

    111
001
010
100 -which is safe
 

Thus the correct move for A is 7, 1, 2, 4.

Move 2. (To be made by B)
A has left a "safe" combination and B cannot make a "safe" move. B makes a move at random taking 3 from heap 0 and leaving 4, 1, 2, 4.

Move 3. (To be made by A)
A makes a mistake in this move and removes 1 from heap 1 leaving 4, 0, 2, 4. (The correct move was 4, 1, 1, 4).

Move 4. (To be made by B)
B makes a correct move leaving 4, 0, 0, 4.

Move 5. (To be made by A)
It is now impossible for A to make a correct move and so he makes a random move taking 3 from heap 3 and leaving 4, 0. 0, 1.

Move 6. (To be made by B)
Transition has occurred since only heap 0 remains with more than one match in it. B makes the correct. move leaving 0, 0, 0, 1.

Move 7. (To be made by A)
A must now take the last match and he loses.

 

MULTIPLE NIM

A more general game of Nim may be played in which more than one heap may be operated on in a single move. Before the game commences the two players must decide which form of multiple game they are to play and fix a number k which is the maximum number of heaps which may be operated on in a single move. In order to simplify demonstration Nimrod has been designed to use a maximum of four heaps each of which may not contain more than seven matches. Only two forms of the multiple game can therefore be played viz.— for k = 2, in which either two heaps or one heap may be operated on in a single move, and for k = 3, in which three heaps, two heaps or one heap may be operated on in a single move. Obviously the game for k = 4 would be trivial.

The rules for the correct playing of multiple Nim are very similar to those used in the simple game. In all variations the first step is the same, i.e., the contents of the heaps are always expressed in binary fashion and arranged in columns as shown above. There is a new rule for judging the safety of each column in a multiple game. For the simple game where k = 1 it will be remembered that the test for safety was to see whether the columns were exactly divisable by two. An extension of this method to multiple games is used and in this case the test for safety is to see whether each column is exactly divisible by k + 1. A column is safe if it is exactly divisible by k + 1 (N.B. 0 is always exactly divisible by k + 1 as 0/k + 1 leaves no remainder). When a column is found which is not exactly divisible by k + 1 then this column is "unsafe" and a modification must be made. Therefore choose a heap which has a 1 in the "unsafe" column being investigated. Modify the number of matches in this heap in the usual way. Again inspect this same column and if it is now divisible by k + 1 pass to the next column on the right. If, however, it is still not divisible by k + 1 choose a second heap with a 1 digit in this column and modify it. Further heaps may have to be modified until the column is divisible by k + 1 and the column is "safe." When the column has been made "safe" pass on to the next column on the right. If this is "safe" pass on to the next column but if it is "unsafe" heaps must be modified until it is made divisible by k + 1. Care must be taken to re-modify heaps which have been previously modified before modifying a new heap. This process is repeated on all columns until the arrangements is "safe." If the arrangement was originally safe all columns will be found to be divisible by k + 1 and a random move must be made which will result in an "unsafe" combination.

Transition in the reverse multiple game occurs when only k or less heaps remain with more than one match in them. After this point the rule for a correct move is to leave either k + 2 heaps or 1 heap containing only one match. (Or more generally n (k + 1) + 1 heaps, where "n" is any integer).

 

THE WAY IN WHICH
NIMROD PLAYS NIM

Nimrod has been designed so that it can play the game of Nim with an opponent from the general public or it can be given a "split personality" so that for demonstration purposes it will play a game without an opponent. At the outset the machine is set to the variation of Nim which is to be played. Instead of matches lights are used and the required combinations are illuminated by a set of 32 push-buttons which are operated by the machine's opponent. These push-buttons are arranged in four rows of eight, each row corresponding to a heap of matches. The buttons in each row are labelled 0, 1, 2, 3, 4, 5, 6 and 7. To change the contents of a heap the player must press the button corresponding to the number of matches he wishes to leave in that heap. So that the player need not look at the large display the state of the game at any time is shown by coloured lights in between the push-buttons.

White lights at the end of each row are also used to indicate the heap which was last operated on. After the player has completed his move he initiates the computer's move by pressing a "computer move" button. Nimrod then makes a move by following the "rule of thumb" method described above, in much the same way as a human player.

The display in front of the machine is used to demonstrate the processes involved when Nimrod carries out a move. To simplify this display a portion of the operation performed by the machine is selected. The chosen portion is that involved in making a correct move in the normal simple game since it demonstrates most clearly the characteristics of the operation of a digital computer.

Before explaining the part of the programme of operations which is displayed it is necessary to mention briefly those parts of the machine which are used in it :-

Main Store. -In this unit the configuration of the heaps at any moment in the process is 'remembered' or stored.

Column Counter. -This unit is used to store the number of the column which we are examining.

Heap Counter. -This unit stores the number of the heap that we are operating on.

Arithmetic Unit. -This is used to decide whether the sum of a column is odd or even.

Heap Selected Memory. -This is operated when we first modify a heap and tells us that we must always return to that heap for any further modifications.

Modifying Number Generator. -This unit is controlled by the column counter and generates a number of the form 01111 — — —. In practice only three numbers are necessary. When we are examining column 2 '011' is generated, '01' for column 1 and '0' for column 0.

 

We can now examine the programme that is displayed.

 

INSTRUCTIONS

 

 

Each instruction is illuminated in its turn starting at number 1. The machine always counts onto the following instruction unless it is specified that it should transfer control to some other number. On the actual display arrows are illuminated to give a further indication of transfer of control.

The operation of the machine is best explained by choosing the 7, 1, 6, 4 combination and working throughout the process performed by the machine in making the correct move.

Instruction 1.

At the beginning of a move the number 2 is always sent to the column counter so that column 2 is caused to be examined by this instruction. The sum of column 2 is in this example 3 which is odd and therefore control counts on one to instruction 2.

Instruction 2.

So that the machine may possess the human quality of being able to choose the heap to be modified, a number is sent from a crude type of random number generator to the heap counter at the beginning of the game. Let us assume that the number generated is 1. Then the digit in heap 1 and column 2 is inspected and is found to be 0. Therefore control goes to instruction 3.

Instruction 3.

One is added to the heap counter so that it now contains the address of heap 2. Control is always transferred from this instruction back to instruction 2.

Instruction 2.

The digit in column 2 and heap 2 is examined. This is a 1 and so control is stepped to instruction 4. (If this digit had been a 0 control would again have been transferred to instruction 3 and then back to instruction 2).

Instruction 4.

The heap selected memory is examined. A heap has not previously been selected and therefore control goes to instruction 5.

Instruction 5.

The heap selected memory is operated so that when later modifications are required this heap will be re-modified. Control then goes to instruction 6.

Instruction 6.

The number 110 in heap 2 is modified to 011. Control then goes to instruction 7.

Instruction 7.

One is deducted from the column counter and the address of column 1 therefore appears in the column counter. Control then goes back to instruction 1.

Instruction 1.

The sum of column 1 is 2 which is even and control is therefore stepped on to instruction 7.

instruction 7.

One is deducted from the column counter leaving the address of column 0 in this counter. Control is then transferred to instruction 1.

Instruction 1.

The sum of column 0 is three which is odd. Control counts on one to instruction 2.

Instruction 2.

The digit in heap 2 and column 0 is 1. Control is therefore stepped on to instruction 4.

Instruction 4.

The heap selected memory has already been operated and heap 2 is the heap which has already been modified. Control is stepped on to instruction 6.

Instruction 6.

The number in heap 2 is again modified, 010 being inserted in place of 011. Control then counts on to instruction 7.

Instruction 7.

One is deducted from the column counter. This is a two digit binary counter and it will therefore only represent the binary numbers 00, 01, 10, 11 which in decimal form are 0, 1, 2, 3. Thus when one is subtracted from the counter which before this instruction was set to 0 the number 11 will be produced. This is not the address of a column as there are only three column addresses viz. :—00, 01 and 10. Thus the number 11 in the column counter is used to indicate the end of the programme and control counts on one to the stop instruction.

Instruction 8.

STOP.

 

The above list of displayed instructions deals only with the move made by a machine when it is confronted with an "unsafe" combination. Provision is made for a further instruction to be called into operation when the machine is confronted with a "safe" combination. The above instructions are obeyed as usual but instruction 8 will be reached without the machine modifying heap. In this case an instruction is called in which causes 1 to be taken from a random heap. This instruction is not included in the display.

 

 

 

 

 

 

 

 

 

DEFINITION OF TERMS USED

CALCULATING MACHINE.

Correctly, any machine used for the purpose of calculating. In this booklet a machine in which every operation is set up individually by an operator.

 

COMPUTER.

Any large machine used to carry out calculations automatically.

 

AUTOMATIC COMPUTER.

A short phrase meaning automatic sequence controlled digital computer.

A computer in which decisions can be made automatically. The machine can exhibit the appearance of 'thinking.'

 

SEQUENCE CONTROL.

Method whereby a computer may be instructed to carry out a given sequence of operations automatically.

 

AUTOMATIC SEQUENCE CONTROL.

Method whereby an automatic computer may be instructed to carry out a given sequence of operations in an order defined by the results of the calculation as it progresses.

 

DIGITAL.

The adjective 'digital' is applied to automatic computers to differentiate them from other types of computers such as differential analysers. It means that every digit of a number is represented separately, so that the accuracy with which one can represent a number is limited only by the number of separate digit positions available in a machine.

LOGIC, LOGICAL.

These refer to a process of formal logic. Just as a complex decision can be synthesised from a number of simple two-way decisions, so 'logical' thinking can be synthesised from simple logic.' In this simple logic every statement is looked upon as being either true or false with no intermediate conditions.

Basically we recognise three relationships from which all our complex decisions can be produced.

 

AND A statement (c) is true if, and only if two other statements (A) and (B) are both true. This is written as

C if A & B

 

OR A statement (c) is true if either, or both statements (A) and (B) are true. This can be written as

C if A OR B

 

NOT A statement (c) is true if a second statement (A) is not true. This can be written as

C if NOT A

 

BINARY.

It is convenient, in electronic digital computers to use circuits in which the valve has only two stable states—off or on, not conducting or conducting—and these so serve to indicate the digits 0 and 1. For all numbers above 1 therefore we have to employ a system which enables us to express them in terms of the digits 0 and 1. This is the binary system, and it compares with the decimal system in the following way.

In the decimal system of numbers we are able to represent any number possible by the combination of ten digits 0 — 9. Up to 9 therefore we need only use one digit to represent any particular number. To signify 10, we have to use two digits, in which the one is given ten times its unit value by being placed immediately to the left in the 'tens' column. To signify 100 or ten tens we have to use three digits and the 1 is placed in the 'hundreds' column. In both 10 and 100 the Os are used to show in which column the 1 is placed. Therefore the number 321 represents three hundred plus twenty plus one.

In the binary system of numbers we have to represent any possible number by the combination of only two digits, 0 and 1. Therefore we can use a single digit to represent the numbers 0 and 1, but we require two digits to represent 2. For 2 we write 10 in which the 1 is given twice its unit value by being placed immediately to the left in the 'two's' column; for 3 we write 11 which corresponds to 2 + 1 in the decimal system. To represent 4 in the binary system we must use three digits and write 100, the 1 being placed in the two twos or 'fours' column. To write 8 we must use four digits and write 1000, and so on. Notice here that as the value of the digits in each column of the decimal system is ten times the value of the digits in the next column to the right, so the value of the digits in each column of the binary system is twice the value of the digits in the next column to the right. Thus, instead of the familiar units, tens, hundreds, thousands columns, we have columns of one, two, four, eight, sixteen, thirty-two and so on. For example in the binary system :


256 128 64 32 16 8 4 2 1
11 =




1 0 1 1 = 8+ 2+1
22 =



1 0 1 1 0 = 16+ 4+2
33 =


1 0 0 0 0 1 = 32+ 1
321 = 1 0 1 0 0 0 0 0 1 = 256+64+1

In the addition of the binary numbers it must be remembered that

1 compared with the decimal system 1
+1
+1
---
---
10
2

and in subtraction

10 compared with the decimal system 2
--1
--1
---
---
1
1

 

 

 

 

 


 

[back to Part 1]  
[back to Part 1 Introduction]  
[back to Guide contents page]