History of madness or your sea battle on BrainFuckʻe

Good day, habra people. Before you is a self-diagnosing hopeless BrainFuck patient.
Those who understand everything from the title and do not want to read the entire post can completely download the game and BFDev and immediately go under the cut to the end of the post to the section “How to play”. The post tells how I got sick with BrainFuck, and also describes the process of creating the game “Sea Battle” in this wonderful language.

Medical history

Infection

The BrainFuck language was created solely in order to break (if translated culturally, not literally) your brain. In short, there are only 8 operators in the language that allow you to work with a memory tape from 8 bit cells. Read more written on wikipedia ( eng ). When I first read this article, I thought that the language is really esoteric and it is impossible to code on this at all. Is that something normal to write a program that will write programs that will write programs ... However, it was a false impression. Since there was nothing to do, I decided to figure it out. As you can see on the same Wikipedia, there are many derived languages: both parallel BrainFork and procedural pBF. After re-reading the article on Wikipedia, I found a link to the development environment in the BrainFuck language - BFDev. Fortunately, BFDev supports procedural BrainFuck, which significantly reduces the code without changing the atmosphere of the perverted language. In fact, this is just a way to get away from copy-paste. Everything is implemented through 3 new operators: (and) to describe the procedure, and: to call. The name of the procedure is the number in the cell at the time the operator was called (It took 30 seconds to learn all the operators. BFDev was very convenient, which added fuel to the fire.
')
First symptoms

I immediately started programming: I quickly wrote an adder program that adds the entered numbers, or rather the numbers. Then I learned to multiply and ... And that's it. I couldn’t invent anything else. I was unable to come up with a division algorithm. Almost the feeling that I can write on “this” anything instantly disappeared, and I returned to the ground. That is my opinion about the language, I think is still true: you can code on this, but very quickly BrainFuck begins in its true meaning. After that, BFDev was abandoned for a long time until it again wanted to stretch their brains.

Second wave

Again, I covered after posts on Habré on the sapper and sudoku on batch file. I decided that I also knew a lot about perversions, and started writing tic-tac-toe on BrainFack. For this, an algorithm was worked out for working with arrays. All the algorithms that will be discussed are described at the end of the post. Drawing a pseudographic field according to the data from the array turned out to be quite simple. Writing an element to the array in two coordinates was also not a problem. In what I wrote, it was already possible to play two players, but the computer did not take any part. The program only meekly drew crosses and toes on the screen without thinking about anything. All this is of course great, but not interesting. Then I tried sudoku. The system of working with tables, implemented in tic-tac-toe, was improved, but due to complete illiteracy in compiling and solving sudoku, the development project was not received either, having stopped at the same stage as tic-tac-toe.

Beginning of the End

And then, finally, I switched to the program, which is dedicated to this post - Sea Battle. Immediately make a reservation that I understand by this name. This is not a classic sea battle, but its modification with a 5x5 field and 4 single-deck ships, the location of which is not subject to any restrictions. And so, by this time I was already able to interact with the user and work with tables. Actually, the matter remains for small: to realize all sorts of game situations and teach how to play a computer. Problems appeared immediately. On bf, there is not even the simplest if, so I had to reinvent. When this problem was solved, I turned to the problem with intelligence.

Computer infection

It needed its own random number generator. Thanks to Google, the simplest congruent linear method for generating pseudo-random variables was found. During the implementation, two problems arose: in the method, division with the remainder is required and, to obtain coordinates, again, division with the remainder is required. Honestly, in solving both problems, I cheated. As it turned out, for a random generator it is not necessary to divide at all, it is enough to be able to add modulo n, and to calculate the coordinates, it is necessary to divide not all numbers and the previously known constant. For a random number generator, a seed is needed, which is considered the simplest of the sum of the coordinates of the ships placed by a person. Everything seems to be good in the algorithm: a uniform distribution across the field, an algorithm for calculating the next move that is not obvious to humans, and, most importantly, I was able to implement it!

What is wrong with this algorithm?

And the bad thing is that it generates a static sequence, and only the number in this sequence, from which the counting begins, depends on the sid. For this reason, the computer can play only 25 games, and if you remember everything, then it is easy to calculate the location of its ships. Although I still do not remember what it says about the not so great significance of this problem. You can of course use other algorithms for generating random numbers, but, unfortunately, while the charge of enthusiasm is over.

Autopsy revealed (Algorithm Descriptions)

Simple algorithms

[-] - reset the current cell.
[>] - go to the right until we find 0. It is convenient to store an array in the style of C strings.
[> + <-] - move the item to the cell to the right
[++++++++++>, –––––––––––] - user’s string query. The only algorithm that was overlooked in the examples to BFDev.

For incurable

Comparing cell value with given number
Brainfuck can only be compared with zero, so first we subtract from what we compare, what we compare with. Thus, it is possible through the operator [] to perform the action provided for the case else and reset the flag in advance. Accordingly, in [] for the flag we write an action for the case of equality. The subtlety is that the code in square brackets must end on the same cell where it started. Then do not forget to restore the value. Suppose you need to compare with 1, and we are standing on a cell with an element with which we compare.
[> +> + << -] >> [<< + >> -] backup
+ flag setting
> [mismatch code> - <[-]]
> [coincidence code [-]]

Plus modulo 25
The idea is in the usual plus, only with a check whether it turned out 25, if yes, then reset. Saving the old value does not interest, so there is no backup.
([-]> + -------------------------> [-] - <[> + <[<-> +]]
> [<< ------------------------- >> [-]] << +++++++++++++ +++++++++++++ [> + <-])

Work with a two-dimensional array
Suppose we have a two-dimensional array of size 6x22. This is the array used in the program. Such array sizes are related to the fact that both displayed fields, as well as symbols of the table image are stored in one array.
First we need to get a number from the two coordinates in the array. To do this, add the row number multiplied by 22 to the column number. Then the most interesting. We need to somehow get to this element. Suppose we are standing in the cell with the calculated number, we have a character that we want to write, or in which we want to write the value on the left, and another empty cell. The whole thing is located right in front of the first element of the array. Copy the first item to an empty cell. Shift two cells with the number and value one unit to the right and decrement the number. Repeat until the number becomes zero. In fact, we shift the first n-1 elements of the array two cells to the left in order to get to the n-th. Further we make copying and we shift the first elements into place. To stop, we need a zero in front of the array.

Division with remainder
The algorithm of dividing not any number into any, but some, not exceeding a predetermined constant, into a constant. In our case, the dividend is limited to 25, and the divisor is 5. Everything is simple - we decrement the number until it is zero, while every 5 iterations we increment the result. The remainder is increased at each iteration and reset to zero at every fifth.
[-> + <[-> + <[-> + <[-> + <[- >> + <[-] <
[-> + <[-> + <[-> + <[-> + <[- >> + <[-] <
[-> + <[-> + <[-> + <[-> + <[- >> + <[-] <
[-> + <[-> + <[-> + <[-> + <[- >> + <[-] <
[-> + <[-> + <[-> + <[-> + <[- >> + <[-] <
]]]]]]]]]]]]]]]]]]]]]]]]]]]

Linear congruential method for generating a pseudo-random variable
It is necessary to generate a number from 0 to 25. The algorithm is based on the following recurrent ratio:


According to the formula, it is necessary to multiply by a and add c, with everything modulo 25. Considering the simple formula, we get a = 6. c can be any, and generally speaking, it would be better to count it from Sid, only in this program with = 2. Using the plus modulo 25 algorithm, we get the code:
[> [-] :::::: <-]> [-] ::, where: calling the plus procedure modulo 25. That’s what a simple random number generator is like.

How to play

To run the program, you need the BFDev environment. Through it open the game file. Next, you need to select the procedural BrainFuck on the toolbar (the rightmost button, near the button with the number 16). Everything is ready, press F9 to start and enjoy the game. The game will start in the Output window from below. First you need to place 4 of their ships. Carefully read what the game writes. Coordinates are entered in the form of two numbers in the order of a row-column (without spaces and separators). Do not enter coordinates greater than 5, as well as more than 2 digits. Do not put the ships in the same cell! There are no checks, so the program will simply start doing anything. In case of an incorrect input, cycling is possible. For emergency completion, press Ctrl + F2. After placing the ships, the game will ask you for a sid. Sid can be any number from 0 to 9. It is necessary that with the same arrangement of the player’s ships there is a possible different behavior of the computer. The first you go. In case of hitting the move is for those who went. The game will end as soon as someone breaks all the enemy ships. There is one glitch here. The game can be completed only with a slip. If you win, the game will not end immediately. To complete, you need to shoot at any cell or press Ctrl + F2.
That's all! Have a nice game!
PS The link is provided on the dropbox, since the original Bfdev site is not stable hosting.