Fullscreen HTML5Med Res (??MB)HTML4

Part Two by Dr Hugo Holden Play your own game of Noughts × Crosses This clever game is built using just discrete logic ICs and an EPROM or EEPROM chip that contains the gameplay data. The first article last month described how the design evolved and how the circuitry works. In this article, we’ll investigate how the gameplay data was generated and then explain how to build it. T he circuit relies on a ‘database’ of moves based on the present state of the playing board and which player started first. Having that information, it performs a ‘look up’ of the EEPROM data to get a number. That number tells the game on which tile to make its next move. So we need the correct data in the EEPROM chip for the machine to play the game correctly and always win or draw, depending on the skill of the human player. How do we go about generating that data? Gameplay decisions Two of my early questions were how many machine responses are required for a game where the human starts first and where the machine starts first. I began by examining the human (X) starting case, ignoring board symmetry and mirror and rotational images. The game has nine different starting possibilities. Let’s say X starts in square 1. Then O has eight remaining squares to choose from. We could limit the response here to taking the central square if X had not taken it initially or, 76 Silicon Chip for the case where X takes the centre square initially, O can take the same initial corner square. The game sequence then depends very much on X’s second move. O’s first response could be called a ‘general start’ because it can be stereotyped as one of two possible squares. After that, we can sort the game sequence into groups of solutions of the form X1,2 and X1,3 through to X1,9, where the first number represents X’s initial move location, and the second number represents X’s second move after the machine’s first response. In the example above, if X’s first move is square 1 (a corner square), there is no game sequence of X1,5 because O’s first response is to take the centre square, so it is no longer an option for X. After O’s initial response, seven squares remain as a choice for X. This means that for each game start-up sequence, seven board patterns occur initially. At this point, it is O’s turn to choose next. Analysis at this point shows that to complete the game, nine Australia's electronics magazine responses are required for each of the initial seven board patterns, to allow for all of the mistakes X could make choosing a square. The nine starting states and seven early board patterns require 63 charts (9 × 7). Each of these 63 charts contains nine data points (or machine responses) to continue the game. The number of responses required by the machine could theoretically be in the order of 569 initial responses in total (9 × 63 + 2). However, once the game has begun, duplicate patterns of Xs and Os appear via different starting sequences. They occur early in the game where two Xs and the one O end up in the same locations; then, the entire group of 9 responses are duplicated. Later in the game, board pattern duplications also occur for the final moves. The required number of computer responses after duplications were deleted for the ‘X starts first’ case turns out to be 285. An example chart is shown in Fig.7, one of 63 supportive charts in the ‘X starts first’ case. I made these by hand siliconchip.com.au Fig.7: one of the many charts I created to calculate the data to load into the EEPROM. They consider every possible move and countermove, and determine which moves are required for the machine to always win or at least draw. siliconchip.com.au Australia's electronics magazine February 2023  77 to examine every possible human move and select appropriate machine responses. The numbers in cyan are the decimal address generated by the game board pattern of X and O playing pieces on the board. I converted these decimal numbers into hexadecimal numbers to program the EEPROM. The numbers in red are the byte values programmed into the EEPROM at those address locations. When the human X starts first, the second player, whether machine or human playing O, is ‘pushed around’ by the playing strategy of X. Many of the responses in this case by the machine O are to prevent being beaten by blocking a winning human move. As mentioned earlier, the starting player has a significant advantage. Consider the human X starting at position 7 (in the chart example above) and making their second move onto square 4. The chart (the upper one and its pathway) is labelled X7,4. Although the human could make their next move differently, onto positions 1, 2, 3, 6, 8 or 9, these are all accounted for in the other X7 charts. X’s initial move generates the decimal address 64. It is then O’s turn, so the computer activates, and it takes the central square. Then X plays square 4 as its second move (in this example of the sequence X7,4). This generates the address 8264 decimal and the machine, in response, takes square 1 because “01” is programmed at that address in the EEPROM. Ignoring the general start moves, there are nine responses from the sequence X7,4, as there are for the sequence X7,1. As can be seen from the charts, there are many opportunities for the human X player to make a mistake where the machine wins, and only one pathway to a draw with the machine. If the human does make a mistake, the machine takes the appropriate square to win. Therefore, most of the data points allow for the many variations of mistakes that the human player can make, so that the machine (which never makes an error) can take advantage of them. In the ‘X starts first case’, there were 28 duplicate charts out of 63, saving 252 responses and leaving just 285. I found that duplications could be increased by settling on a similar gameplay style. Similar data duplications appear later in gameplay for the final responses inside the chart, which match the results in other charts. This further reduces the required number of machine responses. This occurs because game board patterns converge on the same result via different initial playing sequences. Machine starts first When the machine (O) starts first, more charts (72) are required with many more unique machine responses. The number of responses is a little affected by the playing strategy. By starting first, the machine has the advantage and can largely dictate the course of the game, even setting traps where if X makes a poor initial move, they can quickly be in a situation with no way to avoid losing. The game here has been optimised to catch the human out at every opportunity when they make a mistake. Every possible error by the X player has been analysed and responded to. The best the human player can hope for is a draw. Despite that, the same basic principle and strategies apply. It’s just that there are more possibilities, mainly because the machine player chooses a random initial move. There are not as many whole chart duplicates as in the ‘X starts first’; roughly half the number at 15 duplicates. Still, this saves over 100 required machine responses. The total number of machine responses for ‘O starts first’ with my chosen game strategy turned out to be 560, nearly twice the number for ‘X starts first’ (285). Therefore, the total number of unique programmed responses required to ensure both scenarios are supported is 845 with the gameplay strategy used in this design. Case design The two stacked PCBs are somewhat visible through the ‘smoked’ translucent acrylic base. 78 Silicon Chip Australia's electronics magazine Noughts & crosses is such an ancient game and I could imagine people playing it hundreds of years ago with wooden blocks with Xs and Os on them. It’s also commonly played with pen & paper. The problem with board games that use player pieces is that the pieces tend to get lost over time. I decided I wanted a compact game with a quality look, like an elegant product from the 1920s or 1930s, made siliconchip.com.au Fitting the LEDs Getting the LED positions correct is critical. This can be done by feeding the LEDs into their holes and using tape so that they don’t fall out, then temporarily attaching the game board to the top panel. With a game piece or disc in each recess, push the LEDs up so they touch the disc then solder their leads. This ensures that the LED lenses will not prevent the game pieces being placed in their recesses properly. Fig.8: the top side of the game board carries just the 36 blue LEDs and 10 Hall Effect sensors. What is not shown here is that the sensors are spaced about 3.2mm above the top surface of the PCB. I glued phenolic spacers under the TO-92 packages to achieve that, but there are other methods. to last. Popular materials then were plastics such as Bakelite. These sorts of materials are harder to get nowadays, so I decided to build it from 10mm-thick gloss black acrylic panels with white paint-filled engraved markings. I decided on the hinged lid so that the player pieces could be stored inside the game, to reduce the chances of them getting lost. As noted previously, I wanted the game to work without power for two human players. Like some video games, you can choose to play a friend, or the machine if you are on your own. 10mm-thick acrylic has one advantage in that it is relatively easy to tap a coarse thread into it. A good-sized screw for this application is 4-40 UNC. siliconchip.com.au So I tapped long threads, approximately 15mm, into the frame to secure the top & bottom panels. For the initial machine, I used a lightly-tinted 6mm thick see-through bottom panel, so the internal electronics are visible to the observer. The unit can easily be made from any colour combination of 10mm-thick acrylic panels. It could also be made from several other plastic types with variations such as mother of pearl or tortoiseshell patterning. A local plastics company (Sunquest Industries) routed and engraved the acrylic panels for me and added pilot holes. I enlarged and tapped all the required holes with the 4-40 UNC threads. To fit the hinge to the lid, I machined Australia's electronics magazine some 10mm-long, 4mm diameter brass inserts with M2-tapped holes. This is because small-diameter, fine thread pitch screws do not do very well directly into acrylic. You could use pre-made threaded inserts designed for plastic for this task. I drew the PCB designs as images and sent the resulting JPG files to Storm Circuit Technology based in Shenzhen, China. There, Mr Kim Chan converted my images to Gerber files and produced quality PCBs at short notice. I found their service to be excellent. PCB assembly Start by building the two PCBs. The 138 × 166mm game board is coded 08111221, and its overlay diagram is February 2023  79 Fig.9: the resistors, capacitor, ICs, socket strip and wire links are fitted on the underside of the game board. There are five wire links; they can be made using tinned copper wire or component lead off-cuts (if they are long enough) as there is nothing conductive underneath, assuming your board has a solder mask. You might need to change the 1kW resistor value if you aren’t using the A1 version of the Hall Effect sensors. shown in Figs.8 & 9, while the 138 × 124mm compute board is coded 08111222 and is shown in Fig.10. It’s best to start by fitting the components on the underside of the game board, installing the lowest-profile components first (the five wire links and 39 resistors), then the ICs, then the rest. The ICs are all the same type but make sure they are orientated correctly. Nothing else on this side is polarised. Remember to change the 1kW resistor to 510W if you are using the less sensitive (A2) Hall Effect sensors. Now flip it over and solder the 36 blue LEDs with the cathodes (flattened sides in the lenses) facing as shown in Fig.8. EPROM vs EEPROM The only difference between an EPROM and an EEPROM is just how the contents are erased; an EPROM uses UV light through a window on the top of the chip, while an EEPROM is erased by the application of a specific set of electrical signals (“electrically erased”, hence the EE in EEPROM). The data is programmed into both chip types by electric signals, similar to flash memory, a later technology. 80 Silicon Chip Australia's electronics magazine Next, install the Hall Effect sensors with their flat faces away from the PCB and their rounded sides against its surface, bent over as shown. I glued 3.2mm (1/8in) tall phenolic spacers under the bodies of the Hall devices to make sure that they sat at the right height, but they are not definitely required. You could just bend the leads to achieve a 3.2mm gap between the devices and the PCB surface. Assembly of the compute board is straightforward. Start by fitting all the small 1N4148 diodes with the cathode stripes facing as shown in Fig.10, then the resistors, then the larger 1N5819 diode, D1. The next job is to solder all the ICs. You’ll probably want to socket IC1 in siliconchip.com.au Some of the critical items in the parts list can be found on eBay, for example: Hinge screws: siliconchip.au/link/abj3 UNC 4-40 screws for case: siliconchip.au/link/abj4 150mm-long hinge: siliconchip.au/link/abj5 Latches: siliconchip.au/link/abj6 Fig.10: be careful with the orientations of the diodes and ICs when assembling this board as they vary. Also keep in mind that there are different ICs in very similar packages. Once it’s up and running, if something goes wrong, you can probe the test pin points at lower left to get a clue about what it’s doing. They correspond to the EPROM/EEPROM address lines. case it ever needs to be reprogrammed or replaced, but the others don’t need sockets. Take care installing them because there are several different types with the same number of pins, and the orientations vary, with pin 1 being at the top in some cases, and at the bottom in others. Next, bend the leads of REG1 to fit the PCB pads, attach it using a short machine screw and nut, then solder and trim the leads. Follow with header CON2, Mosfet Q1, then the capacitors (all of which are non-polarised) and finally, the piezo buzzer. You can now solder the positive supply wire from your battery or DC socket to the +9V pad next to REG1 via the power switch. Connect the negative supply lead to the pad marked GND. Ensure the supply wiring polarity is correct as there is no reverse protection on the board. The boards can then be plugged together and power applied temporarily to test their function. You can do this by waving the weak magnets over the Hall Effect sensors (especially HS10) with both polarities and checking that the LEDs respond as expected. siliconchip.com.au If it doesn’t work, switch off the power and check for faults like bad solder joints or incorrectly fitted components. If it does, join the two boards using four tapped spacers and eight short machine screws using the predrilled mounting holes. Making the case panels The case is assembled from machined acrylic (MPPA) panels, mainly 10mm-thick black acrylic with some 6mm thick translucent acrylic (the underside panel only). The first step is to prepare these panels. Realistically, you need a CNC mill to make these panels. As I don’t have one, I contacted a local sign-maker, Sunquest Industries. I have used them for some tricky jobs in the past (www. sunquest.com.au). They did a great job making the pieces for me and could likely repeat the job for anyone who wants to build an identical case. Early Noughts & Crosses playing machines This design was inspired by Dick Smith’s challenge in the October 2021 issue (page 13) to design an innovative Noughts & Crosses playing machine. His challenge was based on his creation of a similar electromechanical machine when he was 14 years old (in 1958) that apparently was unbeatable. That was possibly inspired by a machine called “Relay Moe”. Its design was published in the December 1956 issue of Radio-Electronics magazine (also mentioned in Life magazine, March 19, 1956). “Moe” had four playing strategies, but none of them completely precluded the human from beating it. According to the article in Radio-Electronics on Moe, Bell Labs built a similar machine at an earlier date, but that’s all the information they provide on that subject. Another one we found reference to was built by RCA in 1955, the ASTRC-1 – see siliconchip.au/link/abfh Interestingly, both machines depended on timing systems, unlike my design presented here. Australia's electronics magazine February 2023  81 Fig.11: the top panel of the case is somewhat tricky to machine as you need to accurately cut ten recesses in both the top and bottom surfaces, with the underside recesses having smaller recesses within them. Don’t drill too far, or you might break through! You need an end mill for this job, ideally on a CNC mill; a regular drill bit won’t do. 82 Silicon Chip Australia's electronics magazine siliconchip.com.au The most complex panel is the top one, with ten recesses for the player pieces. There are also numerous holes in these recesses for the LEDs to shine through, and recesses on its bottom surface for the Hall Effect devices and the LEDs. Fig.11 shows the drilling details for this panel except for the LED and mounting holes, which have been left off for clarity. Fig.11 also shows the labels on the top panel, which were made by engraving the panel and then filling the recesses with white paint. However, you could attach adhesive labels if you prefer. Fig.12 shows the locations of the LEDs and mounting holes in this panel. Note that some are drilled through while others are drilled partway and tapped. it’s best to use the game board as a template to mark the mounting hole positions to ensure they are accurate. Once you’ve prepared that panel, which is a large portion of the work, move onto the lid, shown in Figs.13 & 14. It has recesses on its underside to allow the pieces to remain on the player board with the lid closed, and optional labelling on the top side. The top edges of the lid were chamfered in my version, which is nice to do but not absolutely required. The details of the side and bottom panels are shown in Figs.15 & 16. The side panels need to be cut to size from 10mm-thick acrylic and one recess made, for either a DC socket or power switch if using a battery. The translucent bottom panel needs ten holes drilled for the screws that hold the case together. Once you’ve drilled all the holes in the top and bottom panels, countersink the ten 3mm holes in each panel and check that the CSK UNC machine screws can be inserted flush with both panels. The tapped holes for attaching the hinges and latches that hold the lid closed are not shown in those figures. That’s because they are best marked and drilled after the case has been assembled, to ensure they are placed accurately. Similarly, the holes in the side panels for the screws that go into the top and bottom panels are not shown as they are made using the top and bottom panels as templates. Making the game pieces The game pieces are made from siliconchip.com.au Fig.12: here are the locations of the holes to drill right through or tap in the top panel, which weren’t shown in Fig.11. There are 36 holes for the LEDs, 10 for the screws that hold the case together and nine to partially drill and then tap on the underside. The complete case without its lid. Note the LED lenses poking through the four holes in each 20mm diameter recess, and the recessed power socket at the front. Australia's electronics magazine February 2023  83 Figs.13 & 14: the lid is a bit simpler to make than the top panel. It just has some artwork on the top and ten circular recesses on the underside, so the game pieces are held inside when the lid is closed. 20mm diameter, 10mm thick pieces of black acrylic with Os and Xs engraved in the top surface and filled with paint. They could be laser-cut or milled from a sheet of 10mm-thick acrylic. It might be possible to make them by hand (eg, using a 20mm hole saw), but that would probably be quite difficult. Once they have been made, drill a recess into the back of each piece deep enough to hold the weak magnets. Glue the magnets in with epoxy, ensuring they are orientated correctly – they need to be reversed on the X pieces compared to the O pieces. To determine the correct orientation, power the unit up and hold a magnet over HS10. If one set of four LEDs lights up, that is the orientation for an X piece; with the X piece held above the magnet, slide the magnet into the recess. If no LEDs light, it is the orientation for an O piece. When you glue the magnets into the pieces, ensure the epoxy surface sits level with the rear of the piece. If it protrudes, the pieces will not fit fully into the recesses, and the lid won’t be able to close. Assembling the case Place the side panels tightly together, place the top panel on top and mark the locations of the holes for 84 Silicon Chip Australia's electronics magazine the ten screws that hold them together. Drill and tap these holes with 4-40 UNC threads. The next job is to mount the PCBs to the rear of the front panel. Screw 4-40 UNC threaded standoffs into the tapped holes on the rear of the front panel, through the game board and some small washers (to act as spacers, giving space for the solder joints on the game board). These are the sort used in computers, available from Jaycar stores. These allow the compute board to be mounted on top of the game board. When installing the game board, ensure that the LEDs all go into their holes (adjust them if necessary). The Hall Effect sensors should slot into their recesses. The standoffs should give enough clearance between the PCB and the front panel so that the solder joints don’t interfere with fitment. You can then attach the four side panels to the top panel, ensuring they fit tightly together, then flip the assembly over, place the rear panel over the opening and mark the ten screw holes like you did for the front panel. siliconchip.com.au Figs.15 & 16: the sides of the case are four rectangles of 10mm thick acrylic with one recess for the DC socket or switch. The bottom panel is a 6mm sheet of translucent acrylic with ten holes drilled through for screws. If you use transparent or translucent acrylic, you’ll be able to see part of the circuit boards inside. Not shown on the bottom panel are holes for mounting feet; we recommend you add them, see the photo. Remove the side panels, then drill and tap those holes for 4-40 UNC. Mark positions for mounting holes for four feet on the base, drill those holes and attach the feet. Mount the DC socket or power switch in the recess in the side panel, then reattach the side panels to the top panel and wire it up. If using a battery, mount that inside the case and wire it up. After checking that it powers up, attach the base. That just leaves the lid. Place the ten pieces in the recesses on the top panel and then lower the lid down on top. It should fit flush – if it doesn’t, figure out why and fix it. Next, hold the hinge centred on the rear of the case so it sits exactly over the seam between the lid and top panel and is centred horizontally. Use tape to hold it in place if necessary and mark out the screw holes (masking tape is best as it doesn’t leave much residue). If in doubt, see the photo to show how it should mount. Similarly, hold the clasps to the front, equidistant from the edges and with the holes halfway between the top and bottom edges of the lid. Mark out siliconchip.com.au the holes in the lid and the front panel. Remove the hinge and clasps, drill the holes to an appropriate depth for the screws and tap the holes. As mentioned earlier, the screws for the hinge are probably too small for you to tap the plastic directly (the screws will pull out and destroy the threads). So instead, drill those holes larger and glue in threaded inserts with epoxy, with threads to suit the hinge screws. You can then attach the hinges and clasps, and the assembly is complete. Conclusion This project is an excellent demonstration of how digital logic can be used to solve a relatively complicated problem. Of course, it could be done with a microcontroller or an FPGA, but this way, you can see exactly how it works. Creating the case from scratch is a considerable amount of work, but I think readers will agree that the result is elegant and suits the game well. The final result is great fun for kids to play with, or as a conversation piece for adults. SC Australia's electronics magazine The lid and one of each of the type of playing pieces. February 2023  85