Celebrate Halloween with Creepy Computer Games in R

Halloween is upon us once more and who ever said that data science can’t be scare. This article translates the Gravedigger game from the 1983 Creepy Computer Games book to celebrate Halloween.  This article is part of my series on gaming with the R language.

In the 1980s I spent my time writing code on my 8-bit ZX81 and Atari computers. I learnt everything I know about programming from copying and modifying printed code listings from books with computer games. The games in these books are mostly simple text-based games, but the authors gave them enticing names, often imaginatively illustrated to visualise the virtual world they represent. A line and a dot become a game of tennis, and a computer that was able to play Tic Tac Toe seemed like your machine had come alive.

Creepy Computer Games in R

The old books by Usborne publishing are unique because it contains several versions of each program to ensure compatibility with some of the many dialects of the BASIC language. I first entered this code into the atari800 emulator to test what it does, after which I converted it to the R language.

Let’s step into the creepy world of computer games as imagined by Usborne Publishing.

Reynold, Colin and McCaig, Rob, Creepy Computer Games (Usborne, London).

Reynold, Colin and McCaig, Rob, Creepy Computer Games (Usborne, London).

Gravedigger

Gravedigger by Alan Ramsey is a typical example of the games listed in the books of the early days of home computing. You can download the original book for free from the publisher ‘s Google drive. The Gravedigger listing starts on page 10. The lyrical description of the game provides the instructions:

It’s dark and windy—not the kind of night to be lost in a graveyard, but that’s where you are. You have until midnight to find your way out. Skeletons lurk in the shadows waiting to scare you to death should you come to close. You can dig holes to help keep them away but digging is tiring work and you cannot manage more than five in one game.  You have to be careful not to fall down the holes you have dug. Grave stones (marked +) and  the walls of the graveyard (marked :) block your way. The holes you digs are marked O, you are * and the skeletons are X. See if you can escape.

Gravedigger code snippet

Partial page of the Gravedigger game in BASIC.

I translated the BASIC code as close to the original as possible. This game is not pretty code, but it works. Some of the variable names have been changed because, in BASIC, single variables and vectors can have the same name and names of character vectors end in $. A future version of this game could use graphics as I did in the Tic Tac Toe game.

The game is quite tricky, and I have only managed to escape the graveyard once. It looks like the likelihood of success very much depends on the random distribution of the graves. Perhaps we need some machine learning to optimise strategy.

You can view the code below, or download it from GitHub. I leave it up to you to deconstruct the program and safely work your way through the graveyard.

Happy Halloween!

Gravedigger screenshot (Emacs).

Gravedigger screenshot (Emacs).

Laser Beams and Elliptical Billiards: Euler Problem 144

Euler problem 144 has been one of the most fun to solve. The underlying problem is the pathway of the reflection of a laser inside an ellipse-shaped mirror. Before I delve into this problem, I like to share this delightful video from Numberphile in which Alex Bellos demonstrates an elliptical billiards table. The billiards problem is mathematically equivalent to the laser problem. The reflection rule optics is the same as the bouncing rule in mechanics, but instead of using light, we use a billiard ball.

This article outlines my solution to Euler problem 104 and simulates the elliptical pool table in the R language. You can find the code on the GitHub repository for this website.

Euler Problem 144 Definition

In laser physics, a “white cell” is a mirror system that acts as a delay line for the laser beam. The beam enters the cell, bounces around on the mirrors, and eventually works its way back out.

The specific white cell we will be considering is an ellipse with the equation 4x^2 + y^2= 100. The section corresponding to -0.01 \leq \times \leq +0.01 at the top is missing, allowing the light to enter and exit through the hole.

Euler Problem 144

The light beam in this problem starts at the point (0.0,10.1) just outside the white cell, and the beam first impacts the mirror at (1.4,-9.6). Each time the laser beam hits the surface of the ellipse, it follows the usual law of reflection “angle of incidence equals the angle of reflection.” That is, both the incident and reflected beams make the same angle with the normal line at the point of incidence. In the figure on the left, the red line shows the first two points of contact between the laser beam and the wall of the white cell; the blue line shows the line tangent to the ellipse at the point of incidence of the first bounce. The slope m of the tangent line at any point (x,y) of the given ellipse is m = -4x/y. The normal line is perpendicular to this tangent line at the point of incidence.

How many times does the beam hit the internal surface of the white cell before exiting?

Proposed Solution to Euler Problem 144

The first step was to rewrite the equation to use functions to generalise the problem. The general Cartesian equation for an ellipse is:

\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1, a < b

The length of the axes for this problem is a =5 and b = 10. While the Project Euler description gives the formula for the slope of the tangent to the ellipse, I have generalised the code to reuse it for the elliptical billiards table. The slope of the tangent to an ellipse at point (x,y) is:

m=-\frac{b^2x}{a^2y}

This first code snippet defines functions to draw an ellipse and calculate the bouncing angle. The last part of the code bounces the laser inside the cell until it exits through the top.

I sourced the formula to find the intersection between a line and an ellipse from Ambrsoft. The equation has two possible solutions, one of which is the same as the original point.

The result of this code is a pretty image of all the laser beams that have bounced around the mirror, which looks like the evil Eye of Sauron in Lord of the Rings.

Graphical solution to Euler problem 144

Graphical solution to Euler problem 144.

Elliptical Pool Table

We can use the solution to Euler problem 144 to play billiards on an elliptical billiards table. To close the article, we return to the elliptical pool table demonstrated by Alex Bellos. This code draws the pool table to the dimensions mentioned in the video. We know that the table has an eccentricity of e = 0.43 and a long axis of a = 130 cm. The code defines the short axis (b) and the distance of the focal points from the centre.

The code selects a random starting point and angle of the shot. The code first determines whether the line passes through the pocket. If this is not the case, the algorithm then finds the place where the ball hits and keeps bouncing it until it falls into the pocket or the ball bounces 100 times.

Elliptical billiard tables have four possible outcomes. Any ball the pass through a focal point will fall into the pocket, ending the simulation. Any ball that passes outside the focal points will bounce around, and the combined trajectories form an ellipse. When the ball moves between the foci, the result is a hyperbola. Lastly, there are some unique circumstances which result in a regular polygon.

If simulations are not enough for you, then head over to the Instructables website to find out how you can construct an elliptical billiards table. There is even a patent for an elliptical pocket billiard table, with the pockets at the edge.

Elliptical billiards: Three simulations.

Elliptical billiards: Three simulations.

 

Tic Tac Toe Minimax Algorithm | Winner , Winner Chicken Dinner

In two previous posts, I presented code to teach R to play the trivial game of Tic Tac Toe. I thought this was an unbeatable algorithm. Alas, a comment from Alberto shattered my pride as he was able to beat my code.

The reason for the demise of my code was that I didn’t implement a full minimax algorithm, but instead looked only two moves ahead. I thought the common strategy rules (start in the centre and occupy the corners) would make the program unbeatable. When I simulated the game by instructing the computer to play against itself, Alberto’s strategy never arose because the code forces the centre field. Alberto’s code shows that you need to look at least three moves ahead for a perfect game. Alberto has been so kind to share his code and permission to publish it.

Alberto recreated two functions, for completeness I have added the complete working code that merges his improvements with my earlier work. The first two functions are identical to the previous post. These functions draw the game board and process the human player’s move by waiting for a mouse click.

Alberto rewrote the functions that analyse the board and determine the move of the computer. The ganador (Spanish for winning) function assesses the board condition by assigning -10 or + 10 for a winning game and 0 for any other situation.

Tic Tac Toe Minimax

The next function is the Tic Tac Toe minimax algorithm. If the computer starts then the first move (9!= 362880 options to assess) takes a little while. The commented lines can be used to force a corner and make the games faster by forcing a random corner.

The minimax function returns a list with the move and its valuation through the ganador function. The function works recursively until it has filled the board and retains the best scoring move using the minimax method. To avoid the computer always playing the same move in the same situation random variables are added.

This final function stitches everything together and lets you play the game. Simply paste all functions in your R console and run them to play a game. The tic.tac.toe function can take two parameters, “human” and/or “computer”. The order of the parameters determines who starts the game.

This is my last word on Tic Tac Toe but now that the minimax conundrum is solved I could start working on other similar games such as Connect Four, Draughts or even the royal game of Chess. You can download the latest version of this code on GitHub.

 

R-Cade Games: Simulating the Legendary Game of Pong

Pong is one of the earliest arcade games on the market, first released in 1972. From the day I first saw this miracle box, I wanted to know more about computers.

I learnt how to write code from the 1983 book Dr. C. Wacko’s Miracle Guide to Designing and Programming your own Atari Computer Arcade Games. This book explains in a very clear and humorous way how to write computer games in Atari basic. I devoured this book and spent many hours developing silly games. This article is an ode to Dr Wacko, a computer geek’s midlife-crisis and an attempt to replicate the software I developed thirty years ago.

Dr. C. Wacko's miracle guide to designing and programming your own Atari computer arcade games

I showed in a previous post that R can be used for board games or play a game of elliptical pool. The question is whether we create arcade games in R. My challenge is to recreate the look and feel of 1980s arcade games, or R-Cade games, using R? The code shown below simulates the legendary game of pong.

Playing Pong in R

The code is based on the Wacko’s Boing Program in the above-mentioned book. The R code is fully commented and speaks for itself. Please note that the animation is very clunky when you run it in RStudio. Only the native R Terminal displays the animation correctly.

Perhaps somebody can help me perfect this little ditty. I love to know how to read real-time USB input to control the game, so we get a step closer to the first R-Cade game.

The Pong Code

You can view the code below or download the latest version from GitHub.

 

Tic Tac Toe War Games: The Intelligent Minimax Algorithm

I have been wasting my time productively by writing games such as the classic Pong in the R language. In a previous post, I shared how to build a randomised Tic Tac Toe simulation. The computer plays against itself playing at random positions. In this post, I will share how to teach the computer to play the game strategically.

I love the 1983 classic movie War Games. In this film, a computer plays Tic Tac Toe against itself to learn that it cannot win the game to prevent a nuclear war.

Back in those days, I devoured the incredible book Writing Strategy Games on your Atari by John White which contains an algorithm to play Tic Tac Toe War Games. This article is my attempt to relive the eighties using R.

You can view the code below or download it from GitHub.

Drawing the Board

A previous post describes the function that draws the Tic Tac Toe board. For completeness, the code is replicated below. The game board is a vector of length nine consisting of either -1 (X), 0 (empty field) or 1 (O). The vector indices correspond with locations on the game board:

1 2 3
4 5 6
7 8 9

Human Players

This second code snippet lets a human player move by clicking anywhere on the graphic display using the locator function. The click location is converted to a number to denote the position on the board. The entered field is only accepted if it has not yet been used (the empty variable contains the available fields).

Evaluate the Game

This code snippet defines the eval.game function which assesses the current board and assigns a score. Zero means no outcome, -6 indicates that the X player has won and +6 implies that the O player has won.

Computer Moves

The computer uses a modified Minimax Algorithm to determine its next move. This article from the Never Stop Building blog and the video below explain this method in great detail.

The next function determines the computer’s move. I have not used a brute-force minimax algorithm to save running time. I struggled to build a fully recursive minimax function. Perhaps somebody can help me with this. This code looks only two steps deep and contains a strategic rule to maximise the score.

The first line stores the value of the players move, the second remainder of the matrix holds the evaluations of all the opponent’s moves. The code adds a randomised variable, based on the strategic value of a field. The centre has the highest value because it is part of four winning lines. Corners have three winning lines and the rest only two winning lines.

This logic means that the computer will, all things being equal, favour the centre over the corners and favour the other fields least. The randomised variables in the code ensure that the computer does not always pick the same field in a similar situation.

This last code snippet enables computers and humans play each other or themselves. The players vector contains the identity of the two players so that a human can play a computer or vice versa. The human player moves by clicking on the screen. The loop keeps running until the board is full or a winner has been identified. A previous Tic Tac Toe post explains the draw.board function.

You can play the computer by running all functions and then entering tic.tac.toe() I am pretty confident this simplified minimax algorithm is unbeatable—why don’t you try to win and let me know when you do.

Tic Tac Toe War Games

Now that this problem is solved, I can finally recreate the epic scene from the WarGames movie. The Tic Tac Toe War Games code uses the functions explained above and the animation package. Unfortunately, there are not many opportunities to create sound in R.

Tic Tac Toe War Games

Random Tic Tac Toe Simulation

Tic Tac Toe might be a futile children’s game but it can also teach us about artificial intelligence. Tic Tac Toe, or Noughts and Crosses, is a zero-sum game with perfect information. Both players know exactly what the other did and when nobody makes a mistake, the game will always end in a draw. Tic Tac Toe is a simple game but also the much more complex game of chess is a zero-sum game with perfect information. In this two-part post, I will build an unbeatable Tic Tac Toe Simulation. This first part deals with the mechanics of the game. The second post will present an algorithm for a perfect game.

Tic Tac Toe Simulation — Random Moves

Tic Tac Toe Simulation — Random Moves.

Drawing the Board

This first code snippet draws the Tic Tac Toe simulation board. The variable xo holds the identity of the pieces and the vector board holds the current game. Player X is denoted with -1 and player O with +1. The first part of the function draws the board and the naughts and crosses. The second part of the code check for three in a row and draws the corresponding line.

Random Tic Tac Toe

The second part of the code generates ten random games and creates and animated GIF-file. The code adds random moves until one of the players wins (winner <> 0) or the board is full (no zeroes in the game vector). The eval.winner function checks for three in a row and declares a winner when found.

There are 255,168 possible legal games in Tic Tac Toe, 46,080 of which end in a draw. This implies that these randomised games result in a draw 18% of the time.

Download the latest version of this code on GitHub.

Tic Tac Toe Simulation

In a future post, I will outline how to program the computer to play against itself, just like in the 1983 movie War Games.