Lines and probability theory



    Everyone who played this game knows: if you try to pull out the blue ball that the cursor is pointing at to place a burgundy in its place, then one of the new three balls coming in will most likely “shut up” this place. If you try to pull it out again, it will shut up again. Throughout the long years of the existence of this effect, there have been disputes between my colleagues from time to time whether this happened by chance or such a trick was purposely made to make it harder to play.

    According to the conditions of the game, it is believed that the balls should fall into random fields. But for some reason, if there is a free field in the littered part of the board, it is filled first.

    In this article, you can go back 20 years and see how the reverse engineering process went around then. We will consider 16-bit assembler code that selects a place for balls. There will be no modern 32- and 64-bit instructions, overgrown with special sets of commands, there will not be any dll calls, threads, or other tricks. Just a simple code. It seems to me that even those who have never seen an assembler will understand it. Those who wish can fix the algorithm so that it works "honestly."

    Let's start with the theory. The simplest obvious algorithm is this: choose a random place on the board, and if it is busy, repeat it. And so until we get to an empty seat. 20 years ago, I thought that such an algorithm was chosen by the author of the game and that is why the game is so “dishonest”. I reasoned this way: what is the probability that in such a situation the next ball will fall into the only free field at the top of the board?



    The probability of getting into the upper and lower halves is the same, but the lower one is almost free, and in the upper one there is only one free field. Therefore, if a random number drops out at the bottom of the board, the algorithm will immediately end, and if at the top, it will be repeated until it falls into the very only free field. That's why it turns out that such free fields immediately “shut up”, and everything seems to fit in with the real behavior of the game.

    But a person familiar with the theory of probability will immediately say that this is wrong. It's like a chance to meet a dinosaur on the street. Either meet or not. The probability of a ball entering any cell is the same, regardless of how many and which cells are occupied. If the red ball has never dropped a red ball over the last 10 moves, then I understand that on the 11th move, most likely, it will still fall, although in fact the probability of it falling now is exactly the same as 10 moves back. If there is anyone else here who has not seen the “ God of Tetris, ” be sure to check out.

    Is it really just an incredible combination of circumstances or the errors of the pseudo-random number generator? There is one assumption, but let's not get ahead of ourselves. It's time to finally see how everything happens from the inside.

    Take for exampleEnglish floppy version of the game, although you can take any other. To start, you need an emulator, for example dosbox . To study and correct the code we use Hiew. The author offers to download his old DOS version on his site for free.

    Where to start? How to find the place in the program where a random number is selected? We have a 9x9 board board. Let's try to search for 16-bit numbers 9 or 81. There are a lot of nines, but 81 is just one. (81 = 51h)



    That's just 9s next to him, apparently we attacked the trail. Let's try randomly changing 51 to 30 and see what happens. We start the game, and it immediately throws the whole field with balls and freezes. This is unexpected. Is this 81 irrelevant to field size? Let's see what kind of cell [343E] it is written to.



    Well, just below the code, the value of this cell is compared with “4C”. Hmmm. 76? What is this? I don’t remember how long this question put me in a dead end, but suddenly (like everything in this process) it dawned on me: this is the number of free cells. At the very beginning of the game, 5 balls appear. First, the field is empty, 81 free cells. Then they throw balls until this number becomes 76. So this is the part of the code where the initial initialization of the board is performed. One of the routines between these operations should just choose the position for the ball. The transition to "not equal" marked as (8) forms a small cycle in which there are only 2 calls. Let's see the first one.



    After standard operations with the stack, as we see, the number 50h (80) is taken, and passed as an argument to call some procedure. It obviously returns the result in the AX register, which is stored in the variable [bp] [- 2]. Then we take this number, divide it by 9 (div cx), increase it by 1 (inc ax), swap the quotient and the remainder, and save the quotient in the cell [39E4]. Then we do the same thing, we only save the remainder of the same division in the cell [39E6].

    Well yes, that’s it. A routine is probably a random number. At the output, we have a random field number. Then we divide it by 9, we get two coordinates, X and Y. In a normal language, it could look like this:

    	cell = random(80);
    	x = cell / 9 + 1;
    	y = cell % 9 + 1;
    

    Go ahead:



    Take the previously calculated X and Y. One of them is shifted to the left (shl) by 1 bit (multiplied by 2), stored in CX. Multiply the other by 12 (18), add it to CX and use it as the index of the array at the address [3490]. What could it be? Well, of course, the contents of the playing field are like a 2-dimensional array of 16-bit numbers. Therefore, X is multiplied by 2, and Y by 18. That is, we already have:

    	cell = random(80);  // случ.число от 0 до 79
    	x = cell / 9 + 1;
    	y = cell % 9 + 1;
    	if (field[x,y]!=0) ...
    

    And the next, last section that we will need: The



    contents of the cell are compared with zero. If so (apparently the cell is free?), We move forward to 1E5A. If not, increase the cell number (which we have a continuous numbering from 0 to 80). Compare it with 51 (81), if less - again, go to 1E5A. If more - write zero there, that is, go to the beginning of the board. At this point, all of our conditional branches converge, and what are we doing? The code from the previous picture is repeated exactly to select the contents of the playing field and is once again compared with zero. If not equal, then go back to the address 1E15, and this is not the very beginning where a random number is selected, but the place where we calculate individual coordinates from it:

    	cell = random(80);  // случ.число от 0 до 79
    next:x = cell / 9 + 1;
         y = cell % 9 + 1;
    	if (field[x,y]!=0)
    	{
    	  cell++;
    	  if(cell==81) cell=0;
    	}
    	if (field[x,y]!=0) goto next;
    

    This is the algorithm. We select a random cell, and then, if it is busy, we simply move across the field from left to right and from top to bottom and in a circle until we find an empty cell. So the reason for "dishonesty" is found. Of course, with this algorithm, the probability of choosing cells will be very different, and depend on the location of the balls already on the board.

    Check that this part of the code really works in the game as we expect. Change at the beginning of 50 to 28. Now, in theory, the new balls should drop out only in the upper half of the board. We start, and nothing changes. Balls appear all over the board.

    It turned out that the program has two almost identical routines, one of which throws 5 balls of random color at the beginning of the game, and the other 3 balls each during the game, but their colors are already known (because they must be shown in advance). Copy / paste rules! Well, change this second subroutine, and make sure that it works.

    Now, in order for the algorithm to “honestly” place balls on random fields, it is enough to change the very last transition a little higher so that it goes to re-select a random number.

    For those who have never used hiew, the exact sequence of actions
    1. Run hiew, select lines.exe
    2. Switch to disassembler mode (Enter, Enter)
    3. Search for the beginning of the procedure (F7, type B8 50 00 bytes)
    4. Move down to the desired transition (by 1D51)
    5. Change the transition address (F3, F2, change 1CF4 to 1CE8)
    6. Exit editing and save changes (Esc, F9)
    7. Exit hiew

    You can check the result even visually in the game. If you simply rearrange all the balls in the upper part of the board, then gradually it will become noticeable how new balls fill first of all the free fields from top to bottom. This is especially noticeable when almost the entire board is full. After this modification, this effect disappears, and the balls begin to appear really in random places.

    It remains to add that in fact there should be cell = random (81), and not 80. Because of this error, the balls never fall into the rightmost lower cell. Unless if all the cells to the left of her are occupied, then he will get there due to this “wrong” algorithm.

    Oh yes, and one more thing. Of course, it would be right to choose a random number from 1 to the number of free cells, and put the ball immediately in the right place, knowing for sure that it is free, and not repeat the cycle until it gets to where it is needed. After all, if only one last cell remains, who knows how many times it will have to be repeated? How long will a 16-bit processor take to complete so many cycles? And according to probability theory, it may happen that he never gets there at all. But we all know that all these theories are nonsense, and sooner or later, and most likely cycles through 80, the ball will certainly fall into this single cell.

    Also popular now: