Friday JS: Quic, which plays tic-tac-toe
Greetings to everyone in my traditional category, full of lovecraftian madness.
In the process of writing one of the past articles (do not look, it was not particularly good), I thought about the fact that Quine ... Yes, I remind you just in case: Quine is a program that outputs its own text, and does it "honestly" ( not having seen, for example, this text in the file on the hard disk). In general, the traditional pointless puzomerka programmers.
So, I thought about the fact that quine, in principle, can carry an arbitrary payload. That is - to do anything else besides its main function. And as a proof-of-concept, I decided to write a quine that plays tic-tac-toe. And wrote. Dirty details under the cut.
')
“But how can he do anything else besides outputting his text?” - you may ask. And easy. In addition to output, the program also has input. If the program displays its text when there is no input, then it is quine. If, on the other hand, the program does something else — who are we to condemn it?
Perhaps I will lay out the cards immediately on the table. Here is a link to my creation. There are three entities in the file by reference:
First we will talk about how to work with the quine function, and then how it works.
At the very beginning of the quine function, you can see the following:
The comment at the very beginning of the function is the user interface. Through it, the function will communicate with those who use it for the game. At first I thought about doing it through the console, but then I decided that it would be more correct to keep the function clean .
Let's check that the function is really quine. Here, for convenience, I posted a (almost) empty HTML page with the quine.js script connected. Having opened the developer tools, you can unambiguously drive the following code into it:
Now we can try to play with it. Let's say we make the first move in the upper left corner of the field.
Now the “user interface” looks like this:
Quine took our turn and made a return to the upper central field. By the way, the resulting function is also a quine - called without arguments, it will return its new text, and not the text of the original function. We can play the whole game, but for convenience we use the auxiliary function evalAndCall.
Voila! Quine plays, wins and even scores. You can play with him a little longer, but for more convenience, I recommend using the Game class, with which I tested the game myself. I think if you have read to this point, I do not need to explain how to use it.
In general, the task consisted of two parts: to write, if possible, a concise function of playing tic-tac-toe, then shove it into quine. Let's start with the tic-tac-toe.
The core of the "artificial intelligence" is on lines 66-90 and looks like an upright squirrel in silhouette:
This code looks a bit obfuscated, because it was interesting to me to make it as short as possible. Its essence is as follows: the input of the next function receives the state of the field — an array of nine elements — as well as the number of the cell where the player-person moves (next checks the validity of this move). Each element of the field can be a cross, a zero, an underscore (empty cell) or an exclamation mark (an empty cell, on which it is worthwhile to put a cross at the first opportunity). If there is an exclamation mark on the field, we immediately make a move there and win. Otherwise, we merge the array into a string and look for the corresponding rule in the rules object. To save space, the rules are given up to a turn, so the field rotates four times for a search. When the desired rule is found, the state of the field is replaced by the value of the rule, broken into characters. The next function then returns the new state of the field. At the same time, an additional tenth symbol can join it: “w” - if the AI ​​won, “d” - if there was a draw.
Thanks to the exclamation marks, “hints” and turns of the field, and also, of course, due to the fact that the AI ​​moves first, the optimal strategy was described in just 6 rules.
Using the next function, the quine function processes the input and writes some fields to the magicHash object. And here we smoothly turn to the second part: how the quine component works. All magic is in the magicHash object and its magicString property.
The string magicString, as it is easy to see, contains almost completely duplicated program text. However, as everyone who has ever tried to write a quine knows, it is impossible to cram a completely full text into her - because then she will have to strictly contain herself, which is impossible for lines of finite length. Therefore, in addition to the "simple" text, it also contains "magic" wildcard sequences, bounded on both sides by the "$" symbol.
When the X hour comes and we need to return the text of the function, we simply take the magicString and replace the wildcard sequences with the corresponding properties of the magicHash object. These properties can be static (backtick), vary during the process (field), or even added during the process (message) - it does not matter. It is important that for each “problem” piece of code that cannot be simply duplicated in a line, we have the “magic” property of the magicHash object. The last substitution is the magicString itself in itself. Lastly, because otherwise there would be additional wildcard sequences that would also be replaced.
I checked on my own experience that you can stuff anything into Quine. In principle, if you pozamorachivatsya, you can make quinogenerator - a function that turns into quine any other pure function and allows you to store an arbitrary state to which the above pure function can access. However, the fields of this manuscript are too narrow ...
In general, I do not claim the special novelty of my “discovery”. Hardcore functionals probably read this text with a smile of excellence. But it was interesting for me to pick it up with my own hands, to put my fingers into wounds, so to speak. And I hope that you were interested to read about it.
Goodbye, girls and boys. Until new meetings.
In the process of writing one of the past articles (do not look, it was not particularly good), I thought about the fact that Quine ... Yes, I remind you just in case: Quine is a program that outputs its own text, and does it "honestly" ( not having seen, for example, this text in the file on the hard disk). In general, the traditional pointless puzomerka programmers.
So, I thought about the fact that quine, in principle, can carry an arbitrary payload. That is - to do anything else besides its main function. And as a proof-of-concept, I decided to write a quine that plays tic-tac-toe. And wrote. Dirty details under the cut.
')
“But how can he do anything else besides outputting his text?” - you may ask. And easy. In addition to output, the program also has input. If the program displays its text when there is no input, then it is quine. If, on the other hand, the program does something else — who are we to condemn it?
Perhaps I will lay out the cards immediately on the table. Here is a link to my creation. There are three entities in the file by reference:
- The quine function is what I’m talking about.
- The evalAndCall function is auxiliary.
- The Game class is even more auxiliary.
First we will talk about how to work with the quine function, and then how it works.
How to work with her
At the very beginning of the quine function, you can see the following:
function quine(input){/* |1|2|3| |4|x|6| |7|8|9| ! - , -. , . , , . , . : - 0 - 0 - 0 */ The comment at the very beginning of the function is the user interface. Through it, the function will communicate with those who use it for the game. At first I thought about doing it through the console, but then I decided that it would be more correct to keep the function clean .
Let's check that the function is really quine. Here, for convenience, I posted a (almost) empty HTML page with the quine.js script connected. Having opened the developer tools, you can unambiguously drive the following code into it:
const quineText = quine(); const evaluatedQuine = eval("(" + quineText + ")"); // , eval // undefined, const evaluatedQuineText = evaluatedQuine(); quineText == evaluatedQuineText; // true Bore mod
In fact, of course, we only checked that the quine function returns the text of the quine, and not that it itself is quine. And to be completely accurate, we only checked that the quine function returns the text of the function, which in our case worked as quine. There are no guarantees that something like is not contained inside:
if(Math.random() < 0.99){ beAGoodQuine(); }else{ haltAndCatchFire(); } Now we can try to play with it. Let's say we make the first move in the upper left corner of the field.
let quineText = quine(1); Now the “user interface” looks like this:
function quine(input){/* |o|x|3| |4|x|6| |7|8|9| ! - , -. , . , , . , . : - 0 - 0 - 0 */ Quine took our turn and made a return to the upper central field. By the way, the resulting function is also a quine - called without arguments, it will return its new text, and not the text of the original function. We can play the whole game, but for convenience we use the auxiliary function evalAndCall.
let quineText = quine(); // , . /* |1|2|3| |4|x|6| |7|8|9| */ quineText = evalAndCall(quineText, 1) /* |x|o|3| |4|x|6| |7|8|9| */ quineText = evalAndCall(quineText, 3) /* |x|o|o| |4|x|6| |7|8|x| . , 0 */ quineText = evalAndCall(quineText, 0) /* |1|2|3| |4|x|6| |7|8|9| : - 0 - 1 - 0 */ Voila! Quine plays, wins and even scores. You can play with him a little longer, but for more convenience, I recommend using the Game class, with which I tested the game myself. I think if you have read to this point, I do not need to explain how to use it.
How things are arranged
In general, the task consisted of two parts: to write, if possible, a concise function of playing tic-tac-toe, then shove it into quine. Let's start with the tic-tac-toe.
The core of the "artificial intelligence" is on lines 66-90 and looks like an upright squirrel in silhouette:
const rules = { "o___x____": "ox__x__!_", "ox__x__o_": "ox!_x_xo_", "oxo_x_xo_": "oxo!xxxo_", "oxooxxxo_": "oxooxxxoxd", "_o__x____": "xo__x___!", "xo__x___o": "xo_xx!!_o" }; const next = (field, move) => { if(!~"!_".indexOf(field[--move])){ return null; } field[move] = "o"; const win = field.indexOf("!"); if(~win){ field[win] = "x"; return [...field, "w"]; } for(let n = 0; n < 4; n++){ field = field.map((_, i) => field[[2, 5, 8, 1, 4, 7, 0, 3, 6][i]]); rules[field.join("")] && (field = rules[field.join("")].split("")); } return field; } This code looks a bit obfuscated, because it was interesting to me to make it as short as possible. Its essence is as follows: the input of the next function receives the state of the field — an array of nine elements — as well as the number of the cell where the player-person moves (next checks the validity of this move). Each element of the field can be a cross, a zero, an underscore (empty cell) or an exclamation mark (an empty cell, on which it is worthwhile to put a cross at the first opportunity). If there is an exclamation mark on the field, we immediately make a move there and win. Otherwise, we merge the array into a string and look for the corresponding rule in the rules object. To save space, the rules are given up to a turn, so the field rotates four times for a search. When the desired rule is found, the state of the field is replaced by the value of the rule, broken into characters. The next function then returns the new state of the field. At the same time, an additional tenth symbol can join it: “w” - if the AI ​​won, “d” - if there was a draw.
Thanks to the exclamation marks, “hints” and turns of the field, and also, of course, due to the fact that the AI ​​moves first, the optimal strategy was described in just 6 rules.
Using the next function, the quine function processes the input and writes some fields to the magicHash object. And here we smoothly turn to the second part: how the quine component works. All magic is in the magicHash object and its magicString property.
The string magicString, as it is easy to see, contains almost completely duplicated program text. However, as everyone who has ever tried to write a quine knows, it is impossible to cram a completely full text into her - because then she will have to strictly contain herself, which is impossible for lines of finite length. Therefore, in addition to the "simple" text, it also contains "magic" wildcard sequences, bounded on both sides by the "$" symbol.
When the X hour comes and we need to return the text of the function, we simply take the magicString and replace the wildcard sequences with the corresponding properties of the magicHash object. These properties can be static (backtick), vary during the process (field), or even added during the process (message) - it does not matter. It is important that for each “problem” piece of code that cannot be simply duplicated in a line, we have the “magic” property of the magicHash object. The last substitution is the magicString itself in itself. Lastly, because otherwise there would be additional wildcard sequences that would also be replaced.
Total
I checked on my own experience that you can stuff anything into Quine. In principle, if you pozamorachivatsya, you can make quinogenerator - a function that turns into quine any other pure function and allows you to store an arbitrary state to which the above pure function can access. However, the fields of this manuscript are too narrow ...
In general, I do not claim the special novelty of my “discovery”. Hardcore functionals probably read this text with a smile of excellence. But it was interesting for me to pick it up with my own hands, to put my fingers into wounds, so to speak. And I hope that you were interested to read about it.
Goodbye, girls and boys. Until new meetings.
Source: https://habr.com/ru/post/435732/
All Articles