Fullscreen HTML5Med Res (??MB)HTML4

Part One by Dr Hugo Holden Play your own game of Noughts × Crosses This Noughts & Crosses-playing Computer (also known as Tic-Tac-Toe) has no processor, clock signals, registers or latches. It merely uses logic gates and a ROM that behaves as a complex array of gates. The user interface is simple but elegant: plastic chips printed with Xs and Os are placed in one of nine recesses on the game board and the Computer signals its move by lighting LEDs on the appropriate spot. I n this type of system, the only computation delay is the propagation delay of the gates or logic devices. Since this Computer responds to static logic conditions, it can never get confused or out of step with itself, or lock up. While speed is not important for this application, a low current draw is. Current consumption increases with clocking frequency in clocked systems. This makes a CMOS-based static computer extremely attractive for battery operation and low power consumption. The current consumption from the 9V DC power source varies between 75mA and 90mA, most of which is for lighting the LEDs. This design does include an oscillator, but it is not used for any computation. Instead, it behaves like a random number generator (RNG) using a ‘spinning wheel’ technique described below. Before tackling this design problem, I decided it would be good to consider how two people play the game. The person who starts the game 80 Silicon Chip first has a significant advantage over the other player, so alternating which player starts first is required to average that bias out over numerous games. That means the machine needs to be able to make the first move, and it also needs to allow the human player to start first. A predictable player might start the game the same way every time, for example, starting on the central square to gain maximum advantage. But that sort of predictable behaviour soon gets very dull, so the Computer should vary its opening strategy when it is the first player. When a human wins the game, they likely announce it with great enthusiasm, so the Computer needs a way of alerting the human player when it wins. Finally, two humans playing each other would be imperfect to the extent that sooner or later, one might make an error of judgement. This would allow the other human, who didn’t make any errors, not just to prevent the other Australia's electronics magazine human from winning (causing a draw) but to beat the other player. A proper and complete Noughts & Crosses machine would not only be unbeatable by the human player, but it should be able to win against the human at every opportunity. This requires the analysis of every possible mistake the human could make during gameplay. In light of the above features, I decided that the way to design the machine would be to initially create a two-player board game. Each player could place a disc, with an X or an O label on it, in the player area. This board would work fine even with no electric power available, and two players could enjoy the game together as usual. However, if one of the human players ‘goes missing’ and the game is powered, the machine steps in to replace one human player. It then becomes a human vs machine scenario. The machine must be able to perform the functions that a ‘flawless’ siliconchip.com.au human player would possess: never make any mistakes, never be beaten, but also win when given the opportunity. The game is configured as a player board, with X and O player pieces, but the machine only has a ‘brain’ and not eyes and arms. So the machine asks the human player to place the machine’s discs on the board by lighting the LED where the machine wants its disc placed. Note that in this design, the machine always plays as O and the human as X. The board can sense the presence of an X or an O disc on the player board. The computer ‘knows’ where on the board each is, and it ‘knows’ when it is the machine’s or the human’s turn to move. When it is the machine’s turn to make a move, the move is computed in under 200ns. After analysing the board pattern of Xs and Os, it lights LEDs on the board where it wants its O piece placed. The maximum number of X player pieces that can be applied to the player board when X starts first is five, limiting the number of O discs that can be placed to four. And that the maximum number of O discs when O starts first is limited to five, thereby limiting the number of X discs to four. This means there is either an X disc or an O disc left over, depending on whether the human (X) or the machine (O) started the game. Therefore, an extra space is provided to store the unused disc. This space also acts as a bipolar electrical switch to configure the computer circuitry for who starts first. This is not only convenient but it also avoids the need for any mechanical switches. If X (human) is to start the game first, an O disc is placed in the spare space, but if O is to start first, an X disc is placed in the extra space. This instruction is engraved onto the player board surface along with the fact that the human plays the X pieces and the machine plays the O pieces. When the game is initially powered, with no discs placed anywhere on the board, all the LEDs are lit. This represents the ‘start randomiser’ function. The LEDs on the board are actually rapidly lighting up in sequence, one at a time. This also serves as the LED test function, similar to how it was once customary to briefly light all lamps on an instrument at switch-on. siliconchip.com.au If an X disc is placed in the spare space (meaning the machine starts first), the ‘spinning wheel’ stops and locks in the first move for the Computer. The LEDs that remain lit show the random position for O’s first move. When the game’s lid (top hinged cover) is closed, it safely stores all the playing pieces (discs) inside, so they do not get lost or separated from the game. The prototype game is powered from a 9V plugpack, but since the current consumption is low, it could be powered from a 9V battery or battery pack. You can watch a short video of the machine in operation at https://youtu. be/IE9a5ZJZCgE Circuit design I was inspired by the fact that Dick Smith built a noughts & crosses machine from parts from a telephone exchange in 1958. Most likely, those parts were vintage at the time; most exchange spare parts then dated to the 1930s. I decided it should be possible to do something similar using logic gates. I’m very fond of 74-series logic gates and commonly use 74xxx (TTL) or 74LSxxx (low-power schottky logic) types. There are also CMOS versions like the 74HCTxxx series. These perform the same logic functions with lower power consumption, so I chose them for this project. I also used blue LEDs as they are very energy efficient. The circuitry for the Computer is spread across two PCBs, a ‘game board’ with all the user interface parts (Hall Effect sensors, LEDs etc) and a ‘compute board’ which has all the control circuitry. To analyse the gameplay patterns and make the correct responding move, I am using an EPROM or EEPROM. These need 18 address lines to process the player board logic. The circuit uses ‘parity’ information from the playing board to control the Computer’s action, depending on who starts first. The AT27C020 from Microchip is a suitable EPROM that comes in PLCC The underside of the Noughts & Crosses Computer has a clear acrylic lid which lets you peer through and see the two main PCBs. Australia's electronics magazine January 2023  81 82 Silicon Chip Australia's electronics magazine siliconchip.com.au Fig.1: the game board circuit is large but quite simple as it consists of repeating patterns. The nine Hall Effect sensors under the game board (HS1-HS9) each have four associated LEDs with current-limiting resistors. A pair of op amps are also assigned to each of the ten Hall Effect sensors, acting as window comparators to detect whether an X or O piece is present (or neither). siliconchip.com.au Australia's electronics magazine January 2023  83 or DIL packages. The compatible Winbond W27C020 EEPROM is readily available and low in cost. I used a similar 27C020 UV-erase EPROM in my prototype as I had one on hand, along with the required programming equipment. Fun with (weak) magnets Wanting to avoid mechanical switches and not having a microcontroller to support a touchscreen interface, I decided to use ferrite magnets from Jaycar embedded in the player pieces, along with ratiometric (analog) Hall Effect sensors for user input. The ferrite magnets (Jaycar Cat LM1616) come in a packet of 12, and I used 10, five for the Xs and five for the Os. I cut a 14.5mm diameter, 4.5mm deep hole into the bottom of each 25mm diameter, 10mm thick plastic disc. I then glued the magnets into them with 24-hour epoxy resin. I deliberately did not use powerful neodymium magnets as their magnetic fields would be too strong and could interfere with nearby pieces. They also have a habit of jumping to each other or the nearest magnetic object and magnetising it, and are good at accidentally erasing magnetic media. While I used weak magnets, their flux field is above what the Hall Effect sensors require. Fig.1 is the circuit diagram for the game board. The 3×3 grid of Hall Effect sensors labelled HS1-HS9 and the four LEDs associated with each form the game board. The tenth Hall Effect sensor, HS10, controls which player starts first, as described above. Six LM324 quad op amps (a total of 24 individual amplifiers, four unused) process the outputs of the Hall Effect sensors. With no applied magnetic field, the DC output of each Hall Effect device sits within 70mV of 2.5V. The X and O player pieces have magnets glued inside them in opposite orientations. Placing an O disc causes the output from the Hall sensor to go low (below 2V), while placing an X disc on the sensor causes the output to go high (above 3V). The op amps are used as comparators to produce a logic 1 (high level) at Data X or O when an X or O player piece is placed on the board respectively. LM324s are handy for this job because their output voltage swing, when powered from 5V, is a perfect match for TTL logic levels. The general arrangement for each sensor is shown in Fig.2; this is duplicated 10 times on the game board. The 2kW/1kW/2kW resistive string across the 5V supply generates 3V and 2V reference levels. Two of the LM324 op amps are used as a window comparator. The output of one goes high when the Hall Effect sensor is producing more than 3V and the other’s output goes high when the sensor produces less than 2V. As shown in Fig.3, four LEDs are arranged around each sensor for two Fig.2: this shows a pair of Hall Effect sensors as in Fig.1 in isolation. Two are shown as they share a single quad op amp. Whether the DATA X or DATA O line goes high when a magnet is placed near the sensor depends on that magnet’s orientation and thus the magnetic field’s polarity. The 100nF bypass capacitors were unnecessary in the prototype, so they are not shown in Fig.1. 84 Silicon Chip Australia's electronics magazine reasons. One is that the resulting symmetry gives a pleasing appearance, and the other is redundancy. If one LED fails (which can happen), the game can still function normally. Each LED in the group of 4 has its anode connected to +5V with a separate cathode resistor. The 1.6kW current-limiting resistors result in around 1mA through each when they are on, but being blue types, they are pretty bright at this low current level. The manufacturers of the Hall Effect devices recommended bypass capacitors across their supply pins, so I added these as surface-mount ceramic types between the solder pads. Still, the devices appeared to work fine without them, probably because this Computer is static, so there are no switching transients on the power rails. The game board connects to the compute board via a 40-way SIL connector (socket on the game board and header on the compute board), avoiding a large mass of wires. Hall Effect options Several different versions of the Hall Effect sensor are ‘available’. I put that in quotes because, as is typical these days, most of them are out of stock. The A1 version is the most sensitive and that is what I used. Unfortunately, it is not in stock anywhere at the time of writing this, although hopefully, that will change shortly after publication. Fig.3: the four LEDs are arranged around the periphery of each ‘well’ on the game board to produce a pleasing symmetry. Each has its own currentlimiting resistor that sets the LED current to around 1mA. That results in the blue LEDs being quite bright without using much power, even if all 36 are lit. siliconchip.com.au The A2 version is easier to get, but has half the sensitivity of the A1 version. Luckily, it’s pretty easy to compensate for this by changing the single 1kW resistor in the 2kW/1kW/2kW string to 510W. That will make the window comparator thresholds 2.25V and 2.75V instead of 2V and 3V, compensating for the reduced output swing from the Hall Effect sensors. Compute board Fig.5 is the circuit of the compute board that uses all through-hole components. No electrolytic capacitors are used in this design, only film types; this makes the circuitry long-lasting. While not shown in that diagram, there are test points for all the EEPROM address lines (A0 to A17) on the board. They were handy for confirming during development that the game board was working correctly. The player board must recognise any possible pattern or combination of human X and machine O player pieces. It must distinguish, at each of the nine locations, if an X is placed there, an O placed there, or no piece at all is placed there. To convert this information into a binary format suited to computer evaluation, a different piece placed at each location generates a binary number, as shown by the blue and black numbers in Fig.4. These values are summed to produce a single 18-bit number representing the state of the board at any given time, which is used as the EEPROM address to look up the next move. For example, if an O piece was placed in the centre (square 5), this generates a decimal value of 8192. Then if an X piece is placed on the board at location 07, this generates decimal value 64. Therefore, for this simple state of two pieces on the board, the address produced is 64 + 8192 = 8256. It is at that location in the EEPROM where O’s next move is stored; in other words, the EEPROM produces a value (by reading the memory at that address) to light the appropriate LED where the machine’s next O piece is to be placed. No player pieces being present on the board generates an address of zero, and the EEPROM has a value of 255 (0xFF hexadecimal, 11111111 binary) stored at that location. The lower four bits all being one means that there is no output from 74HCT42 decoder IC2, as it is an invalid code, so no LEDs are lit by that decoder in that state. Instead, this value triggers the initial move randomisation process. After this, if an X player piece is placed on the spare space, a randomly selected square will remain lit for the first O piece to be placed, corresponding to the count that IC7 stopped on and the four-bit value presented to IC6. When pieces are on the board and it is the machine’s turn to make a move, the game’s electronics go into ‘compute mode’. The outputs of the EEPROM are enabled by the COMPUTE control line going low, which connects to pin 22 of IC1. The EEPROM’s outputs are activated, resulting in the appropriate LEDs lighting to show where the machine wants its piece placed. The rest of the time, when the COMPUTE control line is high, the EEPROM outputs are tri-stated (open The Noughts & Crosses Computer uses a set of 10 magnetic pieces to play the game, with one piece determing which player goes first. Fig.4: each possible playing position is assigned a different power-of-two value depending on whether an X or an O is placed there. With 18 possible values, those numbers can be used to address a 218 = 256KB EPROM or EEPROM. The numbers stored at those addresses tell the machine what move to make next (1-9 to place a token in a given square or 0/255 for no move). siliconchip.com.au Australia's electronics magazine 85 circuit) and pulled up by four 10kW resistors. This means that the BCD to decimal decoder, IC2 (74HCT42), is presented with all ones (due to the pull-ups), so no LEDs are lit. 86 Silicon Chip The start randomiser Imagine a spinning wheel with the numbers 1 to 9 on it. It’s spinning so fast that it’s just a blur. If you throw a dart at it or stop it abruptly with a Australia's electronics magazine brake, one of the numbers would be selected in an apparently random manner. A similar task falls to IC7, a 74HCT161 counter. It is clocked at siliconchip.com.au Fig.5: the compute board contains the logic that decides which move to make next and whether the machine player has won. Each section described in the text is highlighted and labelled in a different colour to aid in the understanding of the overall circuit. All connections between the circuits of Fig.1 & Fig.5 are made via 40-pin SIL headers CON1 & CON2. around 3kHz by an oscillator formed by IC3a with a 5.1kW feedback resistor and 100nF capacitor. When IC7 reaches a count value of nine, output pin 11 of IC3d goes low, which loads siliconchip.com.au the counter with the value of one, so on the next clock pulse, the counter resets to one. When an X piece is placed on the spare space on the board (signifying Australia's electronics magazine machine is to start first), the oscillator output at pin 3 of IC3 is inhibited. Therefore, a count between 1 and 9 remains, lighting the LEDs on that square on the board. January 2023  87 Notice how I assigned the EEPROM outputs shown in Fig.4 values 1 to 9, not 0 to 8. This is because the O-start randomiser is generated by IC7, a 74HCT161 binary counter which needs to make nine counts, from 1 to 9, and cyclically reset to 1. But it also needs another unique state of zero, when it is reset and does not light any LEDs. The four-bit output of IC7 (Q0-Q4) goes to 4-to-10-line decoder IC6 and it, in turn, lights the appropriate LEDs via diodes D11-D19, so it doesn’t conflict with IC2’s control of the LEDs. If IC6 is presented with an input value of 0, its output lines 1 to 10 remain high, and no LEDs are lit by it. One might wonder why I did not use the count enable pins PE & TE on IC7 to inhibit its counting, rather than stopping the clock. The reason is that these inputs should not be toggled when the clock pulse is low, and there is no synchronisation between the moment when the clock is stopped by the human placing the X on the spare space and the state of the clock pulse at that moment. Fig.6: this demonstrates how the same board state can be achieved by two different games, one of which starts with the human player (X1, at top) and the other starts with the machine player (O1, at bottom). The numbers indicate the sequence of the moves, while the Xs and Os show which player places a token in which square. 88 Silicon Chip While the particular LEDs lit by the output of the randomiser, when it has stopped, remain on for the remainder of the game, the first O piece is placed over them, so they are not visible. If the human player (X) starts first, an O player piece is placed on the spare space. This causes pin 8 of IC3 to go low, clearing the 74HCT161 counter to zero, so the randomiser lights no LEDs. More LEDs are only lit after the first human X piece is placed, to satisfy the machine’s next move. Game sequencer using parity The Computer only should go into ‘compute mode’ when it is the machine’s turn to make a move (place an O piece). Data patterns generated by the encoder board, just after a selected O has been placed, have no meaning to the Computer because the human player has not placed their next X piece yet. The question of ‘when to let the computer compute’ has two answers, depending on who starts the game first. In the case of the machine starting first, there is initially the one O piece on the board (selected initially by the randomiser), then an X is placed by the human. Now there are two pieces on the board, an even number, and it is time for the machine’s next move. After the machine’s move, the total number of pieces goes to three, an odd number, and it should not act. However, if the human starts first and places their X piece, one is an odd number; in this case, it is time to compute to determine the machine’s move. Once the O is placed, the number of pieces becomes even, and now the Computer waits because it is X’s move again. X plays again, and the number goes odd, putting the Computer into compute mode. I realised that I could solve this problem using a parity IC, with a data selector on its two outputs, to select either the odd or even outputs of the parity IC to control the COMPUTE line. Nine sections from three quad 2-input OR gates (IC13, IC15 & IC16) combine the X and O lines from the game board into nine ‘piece present’ signals that then go into the parity chip, IC9 (74HCT280). Its EVEN and ODD outputs go to quad 2-input NAND gate IC5, along with the HS10x and HS10o signals that indicate which player started first. This allows IC5 to generate the Australia's electronics magazine The playing pieces only use ‘weak’ magnets. COMPUTE signal, which comes from the pin 6 output of IC5. To summarise, it depends on whether an even or odd number of pieces are on the board, and who started first. Game state ambiguity Note that in the case that O (the machine) starts first and no pieces are on the board, the COMPUTE line is low, enabling computation. However, with no pieces on the board, all the address lines are zero, and as mentioned earlier, the data at address 0 in the EEPROM is hexadecimal 0xFF. When the 74HCT42 is presented with all four bits high, it will not light any board LEDs. Something to consider is that since the ROM is programmed only to produce valid output values with valid input values that correspond to an achievable pattern of player pieces on the board, why is it necessary to have the game sequencer circuitry at all? Invalid addresses/states would/could result in an output of 0xFF and therefore, no LEDs would be lit anyway. Indeed, you would not need the sequencer circuitry if the game were designed for one of the players (human or machine) to always start first. Fig.6 shows two possible identical patterns that could be achieved through different game sequences. Therefore, these generate the same address for the EEPROM. In one case, X started first, while in the other case, O started first. On the next move, the 5th piece placed could be an X or an O, depending on who started the game. This is why the game sequencer with the parity IC was required, as it gives a different state for the COMPUTE line in these two cases, despite the EEPROM address being identical. Game sounds When the machine wins against the human player, it sounds a beep. There is an oscillator to drive a piezo buzzer in the circuit (based around 555 timer siliconchip.com.au IC4). However, in my prototype, I used a beeper with an inbuilt oscillator, element14 Cat 107-2397, so I bypassed the oscillator. No beep functions are assigned to the Human player because the human can make a sound themselves if they want. They might, especially when the machine not only prevents them from winning but it insults them further by beating them with the slightest error or lack of attention. Since the human can never beat the machine, an automatic announcement for the human player winning is not required. Therefore, it is only necessary to examine the O piece data from the game board (not the X data) for the eight possible configurations of O alignments that indicate a win. Parts List – Noughts & Crosses Computer In the second and final instalment next month, I’ll explain the gameplay strategy and how I generated the gameplay data for the EEPROM. I will then go over the PCB assembly process, case construction and putting it all together into a working game. SC 1 set of parts to make the enclosure (see below) 1 double-sided PCB coded 08111221, 138 × 166mm (‘game board’) 1 double-sided PCB coded 08111222, 138 × 124mm (‘compute board’) 1 40-pin header socket, 2.54mm pitch (CON1) 1 40-pin header, 2.54mm pitch (CON2) 1 piezo buzzer or sounder, 7.5mm lead pitch 1 32-pin DIL IC socket (optional; for IC1) 3 16-pin DIL IC sockets (optional; for IC2, IC6 & IC7) 16 14-pin DIL IC sockets (optional, for IC3, IC5, IC8-13, IC15, IC16 & IC21-26) 1 8-pin DIL IC socket (optional; for IC4) 4 10mm M3 tapped spacers 8 M3 × 6mm panhead machine screws 1 100mm length of 0.7mm diameter tinned copper wire or bell wire Semiconductors 1 W27C020 high-speed, low-power 256KB EEPROM or equivalent, DIP-32, programmed with 0811122A.bin (IC1) 2 74HCT42 BCD-to-decimal decoders, DIP-16 (IC2, IC6) 2 74HCT132 quad 2-input NAND gates, DIP-14 (IC3, IC5) 1 555 timer, DIP-8 (IC4) 1 74HCT161 4-bit presettable counter, DIP-16 (IC7) 1 74HCT30 single 8-input NAND gate, DIP-14 (IC8) 1 74HCT280 9-bit parity generator, DIP-14 (IC9) 3 74HCT10 triple 3-input NAND gates, DIP-14 (IC10-IC12) 3 74HCT32 quad 2-input OR gates, DIP-14 (IC13, IC15, IC16) 6 LM324 quad single-supply op amps, DIP-14 (IC21-IC26) 10 DRV5055A1QLPG linear hall-effect sensors, TO-92 (HS1-HS10) 1 7805 or LM2940CT-5 (see text) 5V 1A linear regulator (REG1) 1 BS270 or 2N7000 N-channel Mosfet, TO-92 (Q1) 36 blue 3mm LEDs (LED1-LED36) [Jaycar ZD0134] 1 1N5819 40V 1A schottky diode (D1) 19 1N4148 75V 250mA small signal diodes (D2-D20) Capacitors 2 1.5μF 50V MKT or multi-layer ceramic 3 1μF 50V MKT or multi-layer ceramic 3 100nF 50V MKT or multi-layer ceramic 1 10nF 63V MKT Resistors (all 1/4W 1% axial) 1 470kW 6 10kW 2 5.1kW 36 1.6kW 2 2kW 2 1kW Enclosure 1 machined and engraved lid made from 10mm-thick acrylic, 160 × 200mm 1 machined and engraved top panel (10mm-thick acrylic), 160 × 200mm 1 160 × 200mm sheet of 3mm thick smoked translucent acrylic (for base) 2 200 × 40mm sheets of 10mm thick acrylic (side panels) 2 140 × 40mm sheets of 10mm thick acrylic (front and rear panels) 1 150mm hinge 2 small lid latches/clasps 4 screw-on rubber feet 20 10mm-long countersunk hex socket cap head 4-40 UNC machine screws (for attaching the base & top panel) 10 10mm-long hex head 4-40 UNC machine screws (for clasps & feet) 8 10mm-long countersunk hex socket cap head M2 machine screws (for attaching hinge) 8 10mm-long, 4mm diameter M2-tapped metal inserts (for hinge) 4 4-40UNC hex nuts (for attaching feet) 1 chassis-mount barrel socket OR 1 9V battery holder OR 1 6 x AAA cell holder (CON3) 1 200mm length of light-duty figure-8 wire Playing pieces 10 25mm diameter, 10mm thick black plastic discs 10 weak ferrite magnets [Jaycar LM1616] siliconchip.com.au Australia's electronics magazine Power supply options I was unsure whether the circuit current draw might exceed 100mA, so I built it with a 7805 regulator. So it varies in the range of 75 to 90mA. I am running mine from a 9V 0.5A-rated Jaycar plugpack. As it turns out, it would have been OK with a smaller TO-92 package 78L05 regulator. The current briefly peaks over 100mA when the piezo beeper sounds, but the 78L05 should be able to handle that short-term demand. Due to its low power consumption, the game can be powered by a 9V alkaline battery with about a 500mAh capacity or a 9V Li-ion battery with a 1200mAh capacity. However, there is plenty of room inside the case for six AAA cells in a holder, which would significantly increase the running time over a standard 9V battery. For battery operation, it would be wise to leave the 1N5819 diode (D1) in circuit (to prevent reverse polarity mishaps). A 5V low-dropout (LDO) regulator would be better than the 7805 to get the most out of the battery life. For example, you could use an LM2940CT-5.0, which is pin-compatible and has a dropout voltage of just 110mV at 100mA, compared to around 1.5V for the 7805. Next month January 2023  89