In the footsteps of Jacques Arsac – about game programming
The old book “Programming Games and Puzzles” has probably come across to many of us. Published in 1985, these days it looks archaic and it’s difficult to encourage anyone to program the games included in it. It's a pity 🙂
Let's try to refresh this material a little! Let's take a little look at the examples from the book – and talk about the possible implementation of such games – in the form of tasks, HTML pages – or in the form of an HTTP server – so that the curious can even try to write code and play against the online “evil genius” (well, this is an exaggeration ).
Story
Jacques Arsac – a professor and programming teacher from France, from a time when computers were large and their capabilities were very modest 🙂 He left a significant legacy in the form of a dozen or two books – but only one, mentioned above, has been translated into Russian. By the way, from its French name we learn that casse-tete (brass knuckles) is a puzzle.
Arsak advocates for teaching programming through writing games. He complains: teenagers learn programming in schools and universities – but they don’t know what to program!
Surprisingly, 40 years have passed and the situation in this sense has not changed much, has it? During the courses, children diligently copy some mysterious instructions, mothers enthusiastically look at (or even show their friends) something similar to a 3-dimensional game (or video with a robot) and pay money. Outside of the courses, creativity completely disappears from the child’s head 🙂
Arsak does not offer ready-made programs – he simply describes game ideas and that’s it. Program in whatever language you want. All these games have very simple graphics, without real time. Nowadays it is not so easy to captivate a schoolchild with such crafts. At the same time, they are good because they often really give good exercise to the mind in terms of programming. It is also possible that they are developing abilities in game design (not graphically, but in the sense of gameplay – if you have played or read reviews of the recent game “Troubles” – you understand that this is always relevant).
Thus, this book was not a manual on computer graphics (like, for example, “Secrets of Game Programming” – Andre Lamothe – from it friends diligently copied the code for a 3D labyrinth – iconic then and almost of little use now) and other technical means. Here there is more about ideas, logic, strategies, etc. – these things don't become outdated so quickly.
Problem
I always wanted to “slip” similar material and ideas to modern students. The question is how to do this. Below I will show examples of my attempts; in short, they can be grouped as follows:
games turned into programming tasks
pastebin for creating simple games
games in which you need to write a program to beat the server
games in which you need to write a program to beat someone else's program
Basically, I implemented these attempts at different times on my website – simply because there was already a small audience there so that there would be someone to try – and most of them are still available now.
Briefly about the book by J. Arsac
I’ll tell you a little about examples from the book in case you haven’t read it. Not all material may seem exciting. For example, some attention is paid specifically to puzzles – but programming the solution of cryptarithms has never been very interesting to me. Or the Towers of Hanoi – when I understood the principle – I don’t want to write code for them.
At the same time, there are a number of well-known games – both without strategy and with simple strategy – and there are also original ones. The author's unique sense of humor is also pleasing. As an example, consider one of the first games:
Escape from a collapsing castle
Red Tony enters a dark room. Despite the rumble of the motorcycle, the uniform snoring is clearly perceived. He turns on the headlight and discovers the beautiful Julie serenely sleeping… Julie suddenly wakes up… exclaims: “Let's run away from here quickly… everything is about to explode.” Tony gets on his motorcycle… zigzags through the wreckage. Pieces of burning beams fall, threatening to crush them at any moment.
O - - - - - - - - - - -
- - - - X - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - X X - - - X X -
- - - - - - - - - - - -
- - - - - - - X - - - -
- - - - - - - - - - - TTony and Julie start on a motorcycle from the lower right corner (letter T) – and the exit from the dungeon is in the upper left (letter O) – at each step you can move horizontally or vertically by 1 position. After each move, several fragments of the ceiling collapse – they add obstacles (letters X) – and if they fall on the cell where our heroes are currently located, the game ends immediately.
I will mention several other games given by Monsieur Arsac below among the examples – unlike the epic with Tony, you can play them in one form or another:
And I won’t mention some – because I forgot – but they are present on the site (for example, this is the case with Connect-Four). To summarize, I would recommend not to be lazy and download and leaf through the book. Despite the not very successful (it seems) translation and fragments that may turn out to be outdated or not very interesting to you personally, there are still a lot of interesting game ideas there.
Games turned into challenges
About 10 years ago, I began to create my own website with tasks (I already talked a little – now it’s open source) – and of course I wanted, in addition to exercises on finding the maximum or types of sorting, to add something like games from Arsak’s book.
One of the first attempts was “Pedestrian crossing”: the player stands in front of an 8-lane highway along which cars are rushing (faster on each subsequent lane). The player moves vertically – he can return to the previous lane, step onto the next one, or remain in place. The goal, of course, is to be on the wrong side of the road. It looks like this:
Here the player is indicated by the symbol @ – you see, he has already walked half the road – but at the moment if he steps further, onto the 6th lane or remains on the 5th, he will be crushed by approaching cars (symbols $) – the only chance to stay alive is to retreat to the 4th lane. On the task page you can play this game right now in a simple Javascript implementation. Keys Q, A, Z are used for driving in lanes. https://www.codeabbey.com/index/task_view/crossing-the-road
To “turn” the game into a task, I came up with the idea of generating the initial position of the cars and asking the user to write a program that determines in what minimum number of moves it is possible to cross the road.
The task is not very difficult, but having implemented it, I felt that this was still “not right” – it turned into an exercise in “breadth-first search” for positions arising in the game.
This class also includes “space” physical simulation games – for example, the classic “Soft Landing” – which was played on programmable calculators. It is also available on the website (called Safe Landing).
Challenge games
The next idea was to create tasks in which the result is not just checked for correctness, but can be worse or better. It turned out that users write programs trying to solve a problem better than others. And here some types of games designed for 1 participant were a good fit, for example, “Colored Cubes” – you probably know it – on a square field dotted with multi-colored squares, you need to click and remove adjacent sets of same-color squares, trying to score more points (for large sets, the bonus is awarded in proportion to the square of the number ).
If the field is large enough, there seems to be no hope of an exact algorithmic solution. It turns out that at the top of the table will be either the one who wrote the more ingenious logic – or the one who has more time to calculate the input data (they are always unchanged). Here on the task page there is also an interactive implementation from which you can understand the principle. https://www.codeabbey.com/index/task_view/color-cubes-advanced
Unfortunately, only games “for one” (or those that can be reduced to them) are suitable for such an implementation. So I started thinking further.
The HTTP server is playing against you
I wanted to implement full-fledged games for 2 players. But the original principle of the site was that problems can be solved in any language. How can I write a “second player” that can be connected to the program in any language? And how to check what they played there?
Let the code of the “second player” live on the server, play over HTTP and report the result of the game in encrypted form. The programmer will also learn how to send requests in his favorite language! In this spirit, several famous and not so classic games were implemented: Nim, Fox and Geese, Spies (also Fox Hunt), Wumpus and others. As an example, let's look at the game “Shadok and Gibi” – an idea from the same book by Arsak.
On the planet Shadokov, missile testing continues, constantly ending in failure. The great sorcerer said that there are not enough transistors in the security system. Transistors are mined on the planet Gibi – they grow there like flowers. And so Shadok climbed into the garden with transistors with the goal of collecting 100 pieces. Gibis are very smart thanks to their hats – they guessed what was going on and decided to have fun. Every time Shadok goes to some flower with transistors, they rush there with the goal of picking the transistors before him.
This slightly crazy story was invented by the author based on the French animated series about the Shadoks – you can Google it, although it’s difficult to understand anything there. Well, here’s the game – a rectangular field, the flowers are marked with numbers showing how many transistors grow on them. Gibi are indicated by letters g and Shadok is a letter SFor example:
- - 7 2 - - - - - - - - - - - - - - - - - - - -
- - - g g - - 1 - - - - - g - - - - 8 - - - - -
- - - - - - - - - - - - - - - - - - - 5 - - - -
- 2 - - - - - - - - g 5 - - - - - 7 - - - - - -
- - - - - - - - 1 - - 4 9 - - 7 - - - - - - - -
- - - - - - - 4 - - - - 8 - - - - - 2 - - - - -
- - - - - 5 - - 1 - - - - 6 g - - - - - - - - -
g - - - - - - - - - - - - 2 - g - - 7 - - - - -
- - - g - - S - - - - - 2 - - - - - g - g - - -
- - - g - - - - - - - - g - - - - - - - - - - g
- - - - - - - - - - 4 - - - - - - - - - - - - g
- - - g - - - - - - - - - - - - - 7 g - - - - -
- - - - - - - - - - - - - - - - - - - - 8 - - -
- - - - - g g - - g - - - - - - - - - 5 - - g 4
8 - 9 - - - - g - - g - - - - - - - - - - - - -
- - g - - - - - - - - - - 1 - - - - - g 6 - 5 4The goal is to collect 100 transistors in 40 moves or less. You can write a program to play against the server “manually” to begin with. However, to prevent the task from being completed in this way, a time limit has been set – you need to win in 60 seconds (from the start of a new game).
These games with a server have the inconvenience that you first need to learn how to send HTTP requests – however, once you figure this out, the code can be reused in other games. As a bonus, as the program “fights” with the server, you can visualize the progress of the game – and this can be simply fascinating: for example, I noticed that one of the top users restarts the game many times in a row – and asked what was happening – he explained:
My solution for #251 includes a colored representation of the board after every move, and I quite enjoy seeing the spies (they are red, but that's purely coincidental 🙂 appearing during the game.
My solution to problem 251 (Spies) contains a color display of the playing field after each turn – and I really like to see how more and more spies are gradually discovered (they are displayed in red – but this is pure coincidence) – as the game progresses.
On the pages of these tasks there are no “interactives” like on the previous ones – so for those interested, just let there be a link to their general list – the first one in it is not so much a game as an exercise (Say 100) – purely to understand sending requests.
Games against someone else's code
Games with an HTTP server have two disadvantages:
firstly, you need to figure out how to send requests – it’s not very difficult, and there are examples – but still this is a step that needs to be overcome
the programmer can see the progress of the game and for some games this will make it too easy to guess the strategy.
The way to avoid these complications is to make the user's code play against the code of… someone else. For example, mine. Unfortunately, this approach means that it will no longer be possible to write code in an arbitrary language. In general, it was not clear in what language to do this and how – the site initially did not have an additional sandbox server to run the code.
At the same time, there were already tasks for Brainfac and Assembler-4004. Simple interpreters were written for them in PHP and Python – when a task was sent to the site, the interpreter executed the code and the output could be checked.
I decided to try the same path – initially I added the Scheme interpreter – with it, for example, the games Hamurabi (an economic simulator) and Maze Mapping Robot (you need to write code for a robot that will crawl the entire maze and print out its structure) appeared. Before we go any further, let's look at Hamurabi – it's a very ancient computer game in which you are the king (Hammurabi) – and you have three types of resources: people, land and grain. Grain is needed to sow the land and feed people. People are needed to cultivate the land – then more grain will grow. For grain you can buy land, etc.
Your task is to rule for 10 years and try to increase your wealth and not starve the people. On the task page there is again an interactive implementation where you can practice manually: https://www.codeabbey.com/index/task_view/hamurabi
Naturally, all this comes down to the fact that Scheme, although it is an interesting language in its own way (a simplified version of LISP), is difficult to write something large-scale in it because you are not used to it. The solution for Hamurabi may only contain a couple of lines – but I spent about three days working on the labyrinth mechanics for the robot.
Therefore, the next steps of this experiment were the implementation of BASIC (our own implementation in PHP, a little on steroids, posted on GitHub) – for example, it was proposed to use it to write a simulator for launching a spacecraft into low-Earth orbit. But still, Basic is a perversion in our times, so the third attempt was the introduction of Lua. At the same time, I compiled it into JavaScript, which made it possible to run it in a browser page – thanks to which the user can test his code on a prepared interactive widget before sending it. In particular, this is how the game with repelling an alien attack was made (I briefly mentioned it in the post) – you need to write code for the “tracking system” of a cannon firing at alien ships.
PasteBin for games
At this point, an idea unrelated to the tasks arose. Since I already had a Lua interpreter working with browser-based JavaScript, I can implement the ability to create my own simple games – with rendering on canvas and a simple response to clicks/tap on the screen.
Of course, it is necessary for the user to be able to save and access their “games”. This was easy to do by analogy with PasteBin or rather JsFiddle.
Moreover, based on such a thing, it turned out to be possible to write something like a series of small lessons.
However, this idea has not yet been fully thought out, although it is already suitable for use. In particular, in a couple of places such “games” are built into the page instead of JavaScript “interactives”.
For those who want to touch it with their hands, here is a demo (the “zero” one from the unfinished series of tutorials on this feature).
Of course, in the era of Roblox and similar things, it will not be so easy to surprise someone with simple games on Canvas. Nevertheless, it can certainly be used in the educational process, etc.
To the question why Lua and not Python – mainly because Python is much larger and I did not find a compact implementation in JS (although I tried Brython).
Games against each other – Arena
Those who remember Robot Battles or various Google AI Challenges probably don’t need to explain the idea. In the previous section, we talked about the situation when a programmer writes code to “outplay” a decision made, for example, by the author of a site. But you can make it so that programmers compete in pairs against each other!
With some effort, I attempted to implement something similar on my site. The game was again found in Arsak – it is very simple:
Players take turns rolling one die. The amount of points per turn accumulates until the player decides to pass the turn to the opponent (in this case, the amount is added to the player’s current points) – or until he throws a one (in this case, the amount per turn is lost).
The site allows you to “run” your decision against the decision of another player. This is what the current table of results of games against each other looks like:
The page of the task itself (there is also a JS implementation there to try live) https://www.codeabbey.com/index/task_view/dice-black-jack
Unfortunately, things haven’t gone much further in this direction yet. I would like to solve two problems:
Unlike one-time events (like the Google AI Challenge), I want such a “competition” to continue constantly, for which each new decision needs to be forced to periodically “fight” with the others, recalculate the results table and a lot more to think about (for example, what happens when someone -the solution is rebooted)
all this will look much more interesting if you add visualization – for this you need, for example, to upload the game log back to the web interface – in general terms it’s clear – but as usual there is a lot of fog in the details
Conclusion
Although most of the ideas that I described above did not turn out to be too popular (at least not yet) – the work itself in this direction is gradually bringing new ideas. In particular, with the advent of the site’s own sandbox server (due to the fact that a third-party one was broken), it became possible to run custom code in several popular languages.
Recently, this feature was experimentally used in a problem where you need to checkmate with a king and a rook – playing against a script trying to escape with a lone king.
By the way, with this task, I myself (once again) felt how interesting it was to program the game logic. The fact is that in such tasks, writing code for each of the two sides is an unequal task. It's easier to run away as a lone king. Therefore, having created a problem on the site, I set out to solve it together with other users. It turned out that she has about 3 approaches:
you can use the “El Ajedrecista” algorithm – which was used in the first electromechanical machine more than 100 years ago (or a similar “geometric” approach)
you can build endgame tables (this is similar to dynamic programming) – for each position we determine the winning position and can indicate other positions from which we get into it
finally, you can try to adapt the usual MiniMax – an algorithm that is used during regular chess (and similar) games – but the problem is that in the endgame you need great depth and the branching of the search tree is enormous – at the same time, some heuristic considerations arise that can significantly reduce search volume
Well, so I – although knowing about the first two methods – began to try the third method. My solution still doesn’t always win – but what’s interesting is that my program taught me how to place such a checkmate better than I’ve done it myself so far. I usually pushed the enemy king with my rook and defended the rook with my king – it turned out that the program more actively included the king in the game, quickly driving the enemy into a corner.
In general, tinkering with programming games of varying complexity is quite fun and entertaining at any age and regardless of skills. If possible (if you have read this far), write in the comments:
what games did you write (or wanted to write) when you were learning programming?
what areas of learning through game programming seem more important to you (technical – graphics, sounds; logical – algorithms and strategies; ideological – inventing gameplay, etc.)
