Game in 30 teams of the Assembler
Last year, topics like writing a program in 30 lines of code were popular. All examples were made in JavaScript. To launch such programs, you need not only a web page, but also a browser, different libraries, the OS kernel. In fact, it is not the 30 lines of code that are working, but tens, hundreds of megabytes of program code, which are in the computer’s memory.
Is it possible to write a program that is not completely useless for 30 assembly lines, without unnecessary libraries and megabytes of the OS?
In this article I will describe how you can make tic-tac-toe in 30 assembly lines. UPD Now for just 20 lines. UPD2 And 18 or 16 lines without a single conditional branch.
Task: make a working tic-tac-toe game.
Rules of the game":
The complexity of the implementation of 30 lines of assembler lies in the fact that the assembler simple cycle takes several lines (commands). Each operation is a separate command, which means a new line.
The simplest implementation of tic-tacs is a matrix with the values ​​of the cells that need to be compared in cycles to determine victory, displayed in cycles. Therefore, to make a game in 30 lines of code seems unreal at first glance
Since if you store the playing field as an array, and even more so the matrix, it will take several cycles to determine the victory. You can accommodate the entire playing field, the size of 3 by 3 (enough for 4 * 4) in 4 bytes, or 2 machine words, two bytes per player. Thus, one can reduce the victory check by searching for eight variants of victory, represented in the form of eight numbers (comparing coincidence of bits with int map_x, int map_0).
To test the ideas made the implementation of C.
The game displays the playing field on the screen as follows:
The user presses on the numeric keypad the numbers at the position corresponding to the cell. For example, the number 5 is the center, 1 is the left-bottom cell.
Too much code. Decompiling the resulting program, I saw that there were more than a hundred commands, not counting the printf and scanf calls. Can try to translate most into assembler?
Only the win check function takes about 30 teams. And there are still functions of displaying the result on the screen, reading the position from the keyboard.
This option is not suitable. But such an implementation can fit in BNZ , the size of which is 512 bytes of the first sector of the disk.
And if you think about how this can be solved on HTML in 0 lines of JavaScript?
Write each game variant as a finished line of output to the screen, and add the addresses of the following entries to each variant, which should be shown when pressing the corresponding buttons.
In HTML, this is realized with the help of anchors and a long "party girl". On the assembler, or C, you need to make a program that simply displays text on the screen, depending on the button press.
The program itself will turn out to be small, but the data needed for its work is huge.
An example of an algorithm implemented in C:
And what will be on the assembler?
The program works, only BIOS functions are required, it can start without an operating system, you only need to correct the registers at the beginning of the program (add mov ax, cs; mov ds, ax; mov es, ax ..., remove org 0x100 at the beginning of the program) register it in the loader. It turned out to decorate the output of the program by changing the color of the text. You can insert sound by adding characters with code 7 in the text of the victory lines (PC speaker).
Half the deed is done. It now remains to write arrays of data consisting of several thousand addresses and variants of the game.
Approximate data size calculations:
Total about 31-34 bytes for each option. Total game options can be 9! (9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1). This is a lot, but we need to store only a set of options for the player, since the options for the computer are determined at the stage of data generation. For this option there will be no more than 9 * 7 * 5 * 3 * 1 = 945. If we consider that some options can be completed before filling the last cell (wins, defeats), then there will be even fewer options. The total memory required for storing all variants and addresses will require no more than 32,130 bytes (34 * 945) that fit on one memory page (65535 bytes).
To get this data, a C ++ program was written that generates all the variants and outputs them as an array for C / C ++ and data for the assembler. Then the ability to display the full source code in C, assembler, then HTML with 0 JS lines was added.
, "--help" , :
UPD: found a more compact solution in terms of the number of teams (19-20 teams). If data is presented not in the form of two separate arrays, but in the form of an array of structures, then fewer multiplications will be required to obtain the address. And since you only need to multiply one number per record, you can perform all multiplications in advance. To make it even shorter, I used DOS interrupts; fewer commands are spent on their call, but the color adjustment was lost.
UPD2: for 16 teams, without conditional branches.
')
30 Java Script, , . , . , .
UPD2: , 30 , 20 (), 16 ( - ). — ( «if»).
- 3x3.
* , 255168. (PVE) , .
Is it possible to write a program that is not completely useless for 30 assembly lines, without unnecessary libraries and megabytes of the OS?
In this article I will describe how you can make tic-tac-toe in 30 assembly lines. UPD Now for just 20 lines. UPD2 And 18 or 16 lines without a single conditional branch.
Task: make a working tic-tac-toe game.
Rules of the game":
- up to 30 lines of pure assembler commands. No scam as a machine code entry in one line db ......
- There is no limit to the size of the data. Playing 0 lines of JS had a lot of data in the form of HTML and CSS
- do not use third-party libraries, better without OS interruptions, only BIOS
- the program should work
The complexity of the implementation of 30 lines of assembler lies in the fact that the assembler simple cycle takes several lines (commands). Each operation is a separate command, which means a new line.
An example showing how many lines are needed for loops, for those who don't know assembly language well
// C++ for ( int i=0; i<100; i++)...; _asm { // mov ecx,0 ; int i=0 labelForI: ... inc ecx ;i++ cmp ecx,100 ;i<100 jl labelForI // 127 , jmp, ecx, ... mov ecx,0 ; int i=0 labelForI: push ecx ... pop ecx inc ecx ;i++ cmp ecx,99 ;i<100 ja labelEndFor jmp labelForI labelEndFor: // . mov ecx,100 ; int i=100 labelForI: ... dec ecx ;i-- jnz labelForI // mov ecx,100 ; int i=100 labelForI: nop ; nop - , loop labelForI // , , . DB B9h,00,01,00,00,90h,E2h,F8h ; 99 nop (90h), . } The simplest implementation of tic-tacs is a matrix with the values ​​of the cells that need to be compared in cycles to determine victory, displayed in cycles. Therefore, to make a game in 30 lines of code seems unreal at first glance
The first attempt is to reduce arrays and optimize
Since if you store the playing field as an array, and even more so the matrix, it will take several cycles to determine the victory. You can accommodate the entire playing field, the size of 3 by 3 (enough for 4 * 4) in 4 bytes, or 2 machine words, two bytes per player. Thus, one can reduce the victory check by searching for eight variants of victory, represented in the form of eight numbers (comparing coincidence of bits with int map_x, int map_0).
To test the ideas made the implementation of C.
The game displays the playing field on the screen as follows:
The user presses on the numeric keypad the numbers at the position corresponding to the cell. For example, the number 5 is the center, 1 is the left-bottom cell.
Option 1, C
/* * File: main.c * Author: godAlex * * . * . * * Created on 29 2014 ., 11:51 */ #include <stdio.h> #include <stdlib.h> #define win_x 1 #define win_0 2 #define win_tie 3 #define win_not 0 unsigned short KEYBOARD_BYTE_OFFSET[] = {0x40,0x80,0x100,0x8,0x10,0x20,0x1,0x2,0x4 }; //{0b001000000,0b010000000,0b100000000,0b000001000,0b000010000,0b000100000,0b000000001,0b000000010,0b000000100 }; unsigned short BOT_POSITION_PRIORITY[] = { 0x10, 0x40, 0x4, 0x100, 0x1, 0x80, 0x2, 0x8, 0x20}; // center bounds other //{0b000010000, 0b001000000,0b000000100,0b100000000,0b000000001,0b010000000,0b000000010,0b000001000,0b000100000 }; unsigned short WIN_MATRIX[] = { 0x1C0, 0x38, 0x7, 0x124, 0x92, 0x49, 0x111, 0x54 }; //{ 0b111000000, 0b000111000, 0b000000111, 0b100100100, 0b010010010, 0b001001001, 0b100010001, 0b001010100 }; // unsigned short MAP_X = 0; unsigned short MAP_0 = 0; unsigned short WIN_MATRIX_NOT_WIN = 0x1FF; //0b111111111; // , xor unsigned short STRING_ENTER_POS = 0x124;//0b100100100; // void specialPrintChar(char *c) { printf(c); // TODO ASM } unsigned short specialReadNumber() { char outC; scanf("%c",&outC); // TODO ASM return outC-'0'; } short testWon() { char i; for (i=0; i<8; i++) { if ( (MAP_X & WIN_MATRIX[i]) == WIN_MATRIX[i] ) return win_x; if ( (MAP_0 & WIN_MATRIX[i]) == WIN_MATRIX[i] ) return win_0; } if ( (MAP_X | MAP_0) == WIN_MATRIX_NOT_WIN ) return win_tie; // return win_not; } void printField() { unsigned short bOfs; for (bOfs=1; bOfs<WIN_MATRIX_NOT_WIN; bOfs=bOfs<<1) { // shl if ( MAP_X & bOfs ) specialPrintChar("X"); else { if ( MAP_0 & bOfs ) specialPrintChar("0"); else specialPrintChar("."); } if ( bOfs & STRING_ENTER_POS ) specialPrintChar("\n"); // } } // - - - - - - - - - - - - - - - - int main(int argc, char** argv) { specialPrintChar("Test XO game!\n"); printField(); // // ... int whoIsWon=win_not; while (whoIsWon==win_not) { short cKey; unsigned short full_map; unsigned short p; // do { do { specialPrintChar("Enter cell position (1-9):\n"); cKey = specialReadNumber(); } while ( cKey<1 || cKey>9 ); p=KEYBOARD_BYTE_OFFSET[cKey-1]; // full_map = MAP_X | MAP_0; // } while ( (full_map & p) !=0); // . MAP_X = MAP_X | p; // printField(); // // test Win whoIsWon=testWon(); if (whoIsWon!=win_not) break; // full_map = MAP_X | MAP_0; for (p=0 ; (full_map & BOT_POSITION_PRIORITY[p]) != 0 ; p++); MAP_0 = MAP_0 | BOT_POSITION_PRIORITY[p]; // specialPrintChar(" the BOT:\n"); printField(); // whoIsWon=testWon(); // test Win }; switch (whoIsWon) { // GoTo label testWon (asm) case win_x: specialPrintChar("Won X!\n"); return 1; case win_0: specialPrintChar("Won 0!\n"); return 2; case win_tie: specialPrintChar("Win nothing!\n"); return 3; } return (EXIT_SUCCESS); }
Too much code. Decompiling the resulting program, I saw that there were more than a hundred commands, not counting the printf and scanf calls. Can try to translate most into assembler?
Option 1, function testWon (), rewritten to assembler
int testWon() { int winResult=-1; // todo to asm _asm { mov ecx,0 ;xor ecx,ecx mov edx, offset WIN_MATRIX lForI: //mov bx,WIN_MATRIX[ecx] mov bx, word ptr [edx] ; !!! add edx,2 ; [edx][ecx] mov ax,MAP_X and ax,bx cmp ax,bx ; TODO test, JE lblWonX mov ax,MAP_0 and ax,bx cmp ax,bx JE lblWon0 inc ecx cmp ecx,8 jne lForI mov ax,MAP_X ; or ax,MAP_0 cmp ax,WIN_MATRIX_NOT_WIN jne lblRet ; mov winResult,win_no ; jmp lblRet ;RET lblWonX: mov winResult,win_x jmp lblRet ;RET lblWon0: mov winResult,win_0 jmp lblRet ;RET lblRet: ;RET } return winResult; }
Only the win check function takes about 30 teams. And there are still functions of displaying the result on the screen, reading the position from the keyboard.
This option is not suitable. But such an implementation can fit in BNZ , the size of which is 512 bytes of the first sector of the disk.
The second way is how to do the same in HTML for 0 JS lines?
And if you think about how this can be solved on HTML in 0 lines of JavaScript?
Write each game variant as a finished line of output to the screen, and add the addresses of the following entries to each variant, which should be shown when pressing the corresponding buttons.
In HTML, this is realized with the help of anchors and a long "party girl". On the assembler, or C, you need to make a program that simply displays text on the screen, depending on the button press.
The program itself will turn out to be small, but the data needed for its work is huge.
An example of an algorithm implemented in C:
#include <stdio.h> #include <stdlib.h> unsigned short data_addres[374][9] = {{1, 71, 113, 190, 214, 262, 300, 327, 353}, {1, 1, 2, 16, 24, 31, 45, 52, 65}, ...}; char text[374][13] = {"...\n...\n...\n\0", "...\n...\nX0.\n\0", "...\n..0\nX0X\n\0", ...}; int main(int argc, char** argv) { unsigned int data_pos = 0; while (1) // data_pos != { printf(text[data_pos]); int i; do scanf("%i",&i); while ( i<1 || i>9 ); data_pos=data_addres[data_pos][i-1]; } return (EXIT_SUCCESS); }
And what will be on the assembler?
Option 2, in assembler for 29 commands, working on BIOS interrupts!
SECTION .text org 0x100 ; .com . , . lblShowVariant: mov ax,0x0001 ; clear screen, set graphic mode 40x25, color int 10h mov ax, [data_pos] mov bx, [TEXT_BLOCK_SIZE] mul bx mov bp, text_data add bp,ax ; offset mov cx,[TEXT_BLOCK_SIZE] mov ax,1300h mov bx,0eh ; color mov dx,0500h ; 5 0 int 10h lReadKey: xor ax,ax int 16h ; BIOS read key xor ah,ah sub al,'1' ; al , cmp ax,8 ja lReadKey shl ax,1 ; ax=ax*2 mov bx, data_addres add bx,ax ; bx = data_addres[key] mov ax, [data_pos] mov cx, [CASE_BLOCK_SIZE] mul cx ; cx = [data_pos] add bx,ax ; bx = data_addres[data_pos][key] mov ax,[bx] mov [data_pos],ax ; . jmp lblShowVariant SECTION .data ; Out data on assembler data format data_pos DW 0 ; max=394 CASE_BLOCK_SIZE DW 18 ;bytes (2 byte per 1 case) TEXT_BLOCK_SIZE DW 16 data_addres: DW 1, 42, 72, 100, 139, 167, 198, 272, 341 DW 1, 2, 7, 9, 13, 14, 1, 17, 33 ... text_data: DB "...", 13,10, "...", 13,10, "...", 13,10, " " DB "0..", 13,10, "...", 13,10, "X..", 13,10, " " DB "00.", 13,10, "...", 13,10, "XX.", 13,10, " " DB "You are won!", " " ...
The program works, only BIOS functions are required, it can start without an operating system, you only need to correct the registers at the beginning of the program (add mov ax, cs; mov ds, ax; mov es, ax ..., remove org 0x100 at the beginning of the program) register it in the loader. It turned out to decorate the output of the program by changing the color of the text. You can insert sound by adding characters with code 7 in the text of the victory lines (PC speaker).
Half the deed is done. It now remains to write arrays of data consisting of several thousand addresses and variants of the game.
Approximate data size calculations:
- 9 cells (buttons), addressing word => 18 bytes for each variant of the playing field
- 13-16 byte text field
Total about 31-34 bytes for each option. Total game options can be 9! (9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1). This is a lot, but we need to store only a set of options for the player, since the options for the computer are determined at the stage of data generation. For this option there will be no more than 9 * 7 * 5 * 3 * 1 = 945. If we consider that some options can be completed before filling the last cell (wins, defeats), then there will be even fewer options. The total memory required for storing all variants and addresses will require no more than 32,130 bytes (34 * 945) that fit on one memory page (65535 bytes).
To get this data, a C ++ program was written that generates all the variants and outputs them as an array for C / C ++ and data for the assembler. Then the ability to display the full source code in C, assembler, then HTML with 0 JS lines was added.
Source C ++ data generator for games in 30 lines of assembler code (UPD or 20 lines using DOS interrupts, but without colors), 12 lines C, and 0 lines JS (HTML)
/* * Author: godAlex (C) 2014 * version 1.2 * License GNU GPL v 3 * param: -h -a -c -sa -sc -sh * data optimization: -pvp, -pve, -findequal * optimization: -o0, -o1, -o2, -o3 (unstable), -dosint */ #include <cstdlib> #include "iostream" #include "string.h" using namespace std; //------------------------------------------- //#define show_debug 1 #define win_x 1 #define win_0 2 #define win_end 3 #define win_gameNext 0 #define CASE_BLOCK_SIZE 9 #define TEXT_BLOCK_SIZE 16 int Text_Block_Size=13; // 13, 13, 13,10 16. asm. char End_Of_String=0; bool useDOSInt=false; // BIOS bool mode_pve=true; // pvp ( ) bool optimizeDataFind=true; // bool casheWinVar=true; // char *winText[4]; // , . unsigned short KEYBOARD_BYTE_OFFSET[] = {0x40,0x80,0x100,0x8,0x10,0x20,0x1,0x2,0x4 }; //{0b001000000,0b010000000,0b100000000,0b000001000,0b000010000,0b000100000,0b000000001,0b000000010,0b000000100 }; //unsigned short BOT_POSITION_PRIORITY[] = //{ 0x10, 0x40, 0x4, 0x100, 0x1, 0x80, 0x2, 0x8, 0x20}; // center bounds other //{0b000010000, 0b001000000,0b000000100,0b100000000,0b000000001,0b010000000,0b000000010,0b000001000,0b000100000 }; unsigned short WIN_MATRIX[] = { 0x1C0, 0x38, 0x7, 0x124, 0x92, 0x49, 0x111, 0x54 }; //{ 0b111000000, 0b000111000, 0b000000111, 0b100100100, 0b010010010, 0b001001001, 0b100010001, 0b001010100 }; unsigned short MATRIX_FULL = 0x1FF; //0b111111111; unsigned short STRING_ENTER_POS = 0x124;//0b100100100; // mode_pve==false && optimizeDataFind==false, max = 294781 #define MAX_DATA_SIZE 550000 int data_addres[MAX_DATA_SIZE][CASE_BLOCK_SIZE]; char text[MAX_DATA_SIZE][TEXT_BLOCK_SIZE]; int data_pos = 0; // FIXME unsigned short data_hashcashe[MAX_DATA_SIZE][2]; // findGameVar optimizeDataFind //---- int testWon(unsigned short MAP_X,unsigned short MAP_0) { for (int i=0; i<8; i++) { if ( (MAP_X & WIN_MATRIX[i]) == WIN_MATRIX[i] ) return win_x; if ( (MAP_0 & WIN_MATRIX[i]) == WIN_MATRIX[i] ) return win_0; } if ( (MAP_X | MAP_0) == MATRIX_FULL ) return win_end; return win_gameNext; } void printField(unsigned short MAP_X,unsigned short MAP_0, char* result) { //char result[TEXT_BLOCK_SIZE]="...\n...\n...\n"; int p=0; for (unsigned int bOfs=1; bOfs<MATRIX_FULL; bOfs=bOfs<<1) { // shl TODO test owerflow! if ( MAP_X & bOfs ) result[p]='X'; else { if ( MAP_0 & bOfs ) result[p]='0'; else result[p]='.'; } if ( bOfs & STRING_ENTER_POS ) { p++; result[p]='\n'; } p++; } result[p]=End_Of_String; return result; } // ---- int setVariant(int varID, int variants[CASE_BLOCK_SIZE], char* txt) { int i; for (i=0;i<CASE_BLOCK_SIZE;i++) data_addres[varID][i]=variants[i]; // TODO memcopy for (i=0; i<Text_Block_Size && ( txt[i]!=End_Of_String && txt[i]!=0 ) ; i++) text[varID][i]=txt[i]; text[varID][Text_Block_Size-1]=End_Of_String; // . #ifdef show_debug cout<<" set â„–"<<varID<<" as "<<text[varID]<<endl; #endif return varID; } void addToCasheVar(int i,unsigned short MAP_X,unsigned short MAP_0) // if optimizeDataFind { data_hashcashe[i][0]=MAP_X; data_hashcashe[i][1]=MAP_0; } int getFreeVar() { int p=data_pos; if (p>=MAX_DATA_SIZE-1) { cout<<"Owerflow data pos! " << p <<endl; return -1; } data_pos++; #ifdef show_debug cout<<"New variant â„–"<<p<<endl; #endif return p; } int itrGameHod_traceAll(unsigned short MAP_X,unsigned short MAP_0, bool playOn_X); /** * -. * (0) * - int [0,8], . */ int getBestBotHod(unsigned short MAP_X,unsigned short MAP_0) { // TODO bot . unsigned short lastMAP_X=MAP_X; unsigned short lastMAP_0=MAP_0; unsigned short full_map = MAP_X | MAP_0; int winLevel=-1; // int winPos=-1; //* //if (winLevel<1) for (int i=0; i<9; i++) { // unsigned short p = 1<<i; if ( (full_map & p) == 0 ) { // MAP_0 |= p; // if (playOn_X) MAP_X |= p; else MAP_0 |= p; int tmpWLvl=0; int w=testWon(MAP_X,MAP_0); if ( w!=win_gameNext ) { if (w==win_0) tmpWLvl=40; } else { w=itrGameHod_traceAll(MAP_X,MAP_0, true); if (w & win_0) tmpWLvl+=4; if (w & win_end) tmpWLvl+=2; if (w & win_x) tmpWLvl+=0; } if (tmpWLvl>winLevel) { //|| (tmpWLvl==winLevel && (rand() % 3 == 1))) { winLevel=tmpWLvl; winPos=i; } MAP_X=lastMAP_X; MAP_0=lastMAP_0; } } //*/ return winPos; } int winWariantCashe[4]={0,0,0,0}; // , , . int winWariantVer[4]={0,0,0,0}; // , int setEndGameVariant(unsigned short MAP_X,unsigned short MAP_0, char* txt) { int currentRecordID; if (casheWinVar) { int wonIs = testWon(MAP_X,MAP_0); winWariantVer[wonIs]++; if (winWariantCashe[wonIs]==0) { int addres[CASE_BLOCK_SIZE]={0,0,0,0,0,0,0,0,0}; // ( ) currentRecordID=getFreeVar(); // setVariant(currentRecordID,addres, txt); winWariantCashe[wonIs]=currentRecordID; } else currentRecordID=winWariantCashe[wonIs]; } else { int addres[CASE_BLOCK_SIZE]={0,0,0,0,0,0,0,0,0}; // ( ) //currentText= printField (MAP_X,MAP_0); // , 2 . int currentRecordID=getFreeVar(); setVariant(currentRecordID,addres, txt); } return currentRecordID; } /* * bot 0, mode_pve==true * * playOn_X - 0= , * */ int itrGameHod_traceAll(unsigned short MAP_X,unsigned short MAP_0, bool playOn_X) { unsigned short lastMAP_X=MAP_X; unsigned short lastMAP_0=MAP_0; unsigned short full_map = MAP_X | MAP_0; int winResult=0; int allWinVariant=win_x | win_0 | win_end; if (playOn_X || !mode_pve) { // user, for (int i=0; i<CASE_BLOCK_SIZE; i++) { unsigned short p = 1<<i; if ( (full_map & p) == 0 ) { // //MAP_X |= p; // if (playOn_X) MAP_X |= p; else MAP_0 |= p; int w=testWon(MAP_X,MAP_0); if (w!=win_gameNext) { winResult |= w; if (winResult==allWinVariant) return winResult; // , = } else w=itrGameHod_traceAll(MAP_X,MAP_0, !playOn_X); // iteration MAP_X=lastMAP_X; MAP_0=lastMAP_0; } } } else { // , ( mode_pve ) int i=getBestBotHod(MAP_X,MAP_0); unsigned short p = 1<<i; if ( (full_map & p) == 0 ) { // MAP_0 |= p; int w=testWon(MAP_X,MAP_0); if (w!=win_gameNext) { winResult |= w; if (winResult==allWinVariant) return winResult; } else w=itrGameHod_traceAll(MAP_X,MAP_0, !playOn_X); // iteration MAP_0=lastMAP_0; } } return winResult; } /** * * -1 */ int findGameVar(unsigned short MAP_X,unsigned short MAP_0) { for ( int i=0; i<data_pos ; i++ ) if ( data_hashcashe[i][0]==MAP_X && data_hashcashe[i][1]==MAP_0 ) return i; return -1; } /* * bot 0 * * playOn_X - 0= , * addNewWariant. . */ int itrGameHod_recordAll(unsigned short MAP_X,unsigned short MAP_0, bool playOn_X) { unsigned short lastMAP_X=MAP_X; unsigned short lastMAP_0=MAP_0; unsigned short full_map = MAP_X | MAP_0; int addres[CASE_BLOCK_SIZE]; // ( ) char currentText[Text_Block_Size]; // printField (MAP_X,MAP_0,currentText); if (optimizeDataFind) { int gVar = findGameVar(MAP_X, MAP_0); if ( gVar >=0 ) return gVar; } int currentRecordID=getFreeVar(); if (currentRecordID==-1) { return -1; } if (optimizeDataFind) addToCasheVar(currentRecordID, MAP_X, MAP_0); if (playOn_X || !mode_pve) { // for (int i=0; i<CASE_BLOCK_SIZE; i++) { unsigned short p = KEYBOARD_BYTE_OFFSET[i]; //1<<i; if ( (full_map & p) == 0 ) { // if (playOn_X) MAP_X |= p; else MAP_0 |= p; int w=testWon(MAP_X,MAP_0); if (w!=win_gameNext) { // out who is won addres[i]=setEndGameVariant(MAP_X,MAP_0, winText[w]); // FIXME TEST! winText[win_x] } else { if (mode_pve) { // BOT, PVE int p2Int=getBestBotHod(MAP_X,MAP_0); // 0, !playOn_X if (p2Int == -1) cout<<"Wrong bot variant!"<<endl; unsigned short p2Bit=1<<p2Int; MAP_0 |= p2Bit; int w=testWon(MAP_X,MAP_0); if (w!=win_gameNext) { // out who is won addres[i]=setEndGameVariant(MAP_X,MAP_0, winText[win_0]); } else { // add new wariant int nextDataAddr=itrGameHod_recordAll(MAP_X,MAP_0, playOn_X); // iteration addres[i] = nextDataAddr; } } else { // PVP int nextDataAddr=itrGameHod_recordAll(MAP_X,MAP_0, !playOn_X); // iteration addres[i] = nextDataAddr; // TODO if == -1 } } MAP_X=lastMAP_X; MAP_0=lastMAP_0; } else { addres[i]=currentRecordID; } } currentRecordID=setVariant(currentRecordID, addres,currentText); return currentRecordID; } else { cout<<"Error! ."<<endl; return -1; } } // -------------- void outDataFormatC() { int minimalCaseSize=1; if (data_pos>0xff) minimalCaseSize=2; if (data_pos>0xffff) minimalCaseSize=4; cout<< "// Out data on C array:"<<endl; cout<<"int data_pos = 0; // max="<<data_pos<<endl; cout<<"int CASE_BLOCK_SIZE = "<<CASE_BLOCK_SIZE<<";"<<endl; cout<<"int TEXT_BLOCK_SIZE = "<<Text_Block_Size<<";"<<endl; cout<<"unsigned "; //data_addres if (minimalCaseSize==1) cout<<"char"; if (minimalCaseSize==2) cout<<"short"; if (minimalCaseSize==4) cout<<"int"; cout<<" data_addres["<<data_pos<<"]["<<CASE_BLOCK_SIZE<<"] = {"; for ( int i=0; i<data_pos; i++) { if (i!=0) cout<<", "; cout<<"{"; for ( int j=0; j<CASE_BLOCK_SIZE; j++) { if (j!=0) cout<<", "; cout<<data_addres[i][j]; } cout<<"}"; } cout<<"};"<<endl; //text cout<<"char text["<<data_pos<<"]["<<Text_Block_Size<<"] = {"; for ( int i=0; i<data_pos; i++) { if (i!=0) cout<<", "; // //cout<<"{"; //for ( int j=0; j<TEXT_BLOCK_SIZE; j++) { // if (j!=0) cout<<", "; // cout<< (int)text[i][j]; //} //cout<<"}"; //cout<< "\""<<text[i]<<"\""<<endl; // cout<<"\""; for ( int j=0; j<Text_Block_Size; j++) { if (text[i][j]>=30) cout<< text[i][j]; else { if (text[i][j]=='\n') cout<<"\\n"; else if (text[i][j]==0) cout<<"\\0"; else cout<< "\\("<<(int)text[i][j]<<")"; } } cout<<"\""; } cout<<"};"<<endl; cout<<"// ---- end of data ----"<<endl; } /** * * @param premul , ( ) */ void outDataFormatAsm(int optLevel) { int minimalCaseSize=2; //if (data_pos>0xff) minimalCaseSize=2; //if (data_pos>0xffff) minimalCaseSize=4; cout<<"; Out data on assembler data format"<<endl; if (optLevel==0) { cout<<"data_pos DW 0 ; max="<<data_pos<<"-1"<<endl; cout<<"CASE_BLOCK_SIZE DW "<<CASE_BLOCK_SIZE*minimalCaseSize<<" ;bytes ("<<minimalCaseSize<<" byte per 1 case)"<<endl; cout<<"TEXT_BLOCK_SIZE DW "<<Text_Block_Size<<endl; cout<<"data_addres:"<<endl; for ( int i=0; i<data_pos; i++) { //if (minimalCaseSize==1) cout<<"DB "; //if (minimalCaseSize==2) cout<<"DW "; //if (minimalCaseSize==4) cout<<"QW "; // data_pos 16- DW cout<<"DW "; for ( int j=0; j<CASE_BLOCK_SIZE; j++) { if (j!=0) cout<<", "; cout<<data_addres[i][j]; } cout<<endl; } cout<<endl; //text cout<<"text_data: \n"; bool textMarker=false; for ( int i=0; i<data_pos; i++) { cout<<"DB "; int maxOutBytes=Text_Block_Size; for ( int j=0; j<maxOutBytes; j++) { if (text[i][j]>=30) { if (!textMarker) { if (j!=0) cout<<", "; cout<<"\""; textMarker=true; } cout<< text[i][j]; } else { if (textMarker) { cout<<"\""; textMarker=false; } if (text[i][j]=='\n') { cout<<", 13,10"; maxOutBytes--; } else if (text[i][j]==0 && End_Of_String!=0) cout<<", \""<<End_Of_String<<"\""; // DOS int 21h. else if (text[i][j]==0) cout<<", \" \""; // FIXME ? else cout<< ", "<<(int)text[i][j]; } } if (textMarker) { cout<<"\""; textMarker=false; } cout<<endl; } } if (optLevel==1) { cout<<"data_pos DW 0 ; max="<<data_pos<<"-1"<<endl; //cout<<"CASE_BLOCK_SIZE DW "<<CASE_BLOCK_SIZE*minimalCaseSize<<" ;bytes ("<<minimalCaseSize<<" byte per 1 case)"<<endl; //cout<<"TEXT_BLOCK_SIZE DW "<<Text_Block_Size<<endl; cout<<"data_addres:"<<endl; //data_addres for ( int i=0; i<data_pos; i++) { cout<<"DW "; for ( int j=0; j<CASE_BLOCK_SIZE; j++) { if (j!=0) cout<<", "; cout<< (data_addres[i][j] * (CASE_BLOCK_SIZE*minimalCaseSize+Text_Block_Size)); // . } cout<<endl; //text cout<<"DB "; bool textMarker=false; int maxOutBytes=Text_Block_Size; for ( int j=0; j<maxOutBytes; j++) { if (text[i][j]>=30) { if (!textMarker) { if (j!=0) cout<<", "; cout<<"\""; textMarker=true; } cout<< text[i][j]; } else { if (textMarker) { cout<<"\""; textMarker=false; } if (text[i][j]=='\n') { // "" cout<<", 13,10"; maxOutBytes--; } else if (text[i][j]==0 && End_Of_String!=0) cout<<", \""<<End_Of_String<<"\""; // DOS int 21h. else if (text[i][j]==0) cout<<", \" \""; // , ? else cout<< ", "<<(int)text[i][j]; } } if (textMarker) { cout<<"\""; textMarker=false; } cout<<endl; } } if (optLevel>=2) { cout<<"data_pos DW d_0"<<endl; for ( int i=0; i<data_pos; i++) { cout<<"d_"<< i <<" "; //data_addres cout<<"DW "; for ( int j=0; j<CASE_BLOCK_SIZE; j++) { if (j!=0) cout<<", "; cout<< "d_"<<data_addres[i][j]; // . } cout<<endl; //text cout<<"DB "; bool textMarker=false; int maxOutBytes=Text_Block_Size; for ( int j=0; j<maxOutBytes; j++) { if (text[i][j]>=30) { if (!textMarker) { if (j!=0) cout<<", "; cout<<"\""; textMarker=true; } cout<< text[i][j]; } else { if (textMarker) { cout<<"\""; textMarker=false; } if (text[i][j]=='\n') { // "" cout<<", 13,10"; maxOutBytes--; } else if (text[i][j]==0 && End_Of_String!=0) cout<<", \""<<End_Of_String<<"\""; // DOS int 21h. else if (text[i][j]==0) cout<<", \" \""; // FIXME ? else cout<< ", "<<(int)text[i][j]; } } if (textMarker) { cout<<"\""; textMarker=false; } cout<<endl; } } cout<<"; ---- end of data ----"<<endl; return; } /** * @param showInfo */ void generator_game_data(bool showInfo) { if (showInfo) cout<<"Start generation."<<endl; for ( int i=0; i<MAX_DATA_SIZE; i++) for ( int j=0; j<Text_Block_Size; j++) text[i][j]=End_Of_String; int startP = itrGameHod_recordAll(0,0, true); if (showInfo) { cout<< "Finish generation. Start game position="<<startP<<endl; cout<< "Data length = "<<data_pos<<endl; int minimalCaseSize=1; if (data_pos>0xff) minimalCaseSize=2; if (data_pos>0xffff) minimalCaseSize=4; cout<< " key array size is "<<(data_pos*CASE_BLOCK_SIZE*minimalCaseSize)<<" byte ("<<minimalCaseSize<<" byte per case)"<<endl; cout<< " text array size is "<<(data_pos*Text_Block_Size*sizeof(char))<<" byte"<<endl; cout<< " : "<<winWariantVer[win_end]<<", 0 "<<winWariantVer[win_0]<<", X "<<winWariantVer[win_x] <<endl; cout<< "Use --help for help." <<endl; } } //------------------------------------------- void outListingC() { cout<<"/*"<<endl; cout<<"* example short command tic-tac-toe. By godAlex generator."<<endl; cout<<"*/"<<endl; cout<<"#include <stdio.h>"<<endl; cout<<"#include <stdlib.h>"<<endl; outDataFormatC(); cout<<"int main(int argc, char** argv) {"<<endl; cout<<" while (1) {"<<endl; cout<<" printf(text[data_pos]);"<<endl; cout<<" int i;"<<endl; cout<<" do scanf(\"%i\",&i); while ( i<1 || i>9 );"<<endl; cout<<" data_pos=data_addres[data_pos][i-1];"<<endl; cout<<" }"<<endl; cout<<" return (EXIT_SUCCESS);"<<endl; cout<<"}"<<endl; } void outListingAsm(int optLevel) { cout<<"SECTION .text"<<endl; cout<<"org 0x100 ; .com "<<endl; // cout<<"push cs"<<endl; // cout<<"pop ds ; "<<endl; cout<<"lblShowVariant: "<<endl; cout<<" mov ax,0x0001 ; clear screen, set graphic mode 40x25, color"<<endl; cout<<" int 10h"<<endl; if (!useDOSInt) { // BIOS if (optLevel==0) { cout<<" mov ax, [data_pos]"<<endl; cout<<" mov bx, [TEXT_BLOCK_SIZE]"<<endl; cout<<" mul bx"<<endl; cout<<" mov bp, text_data"<<endl; cout<<" add bp,ax ; offset "<<endl; } if (optLevel==1) { // -3 cout<<" mov bp, data_addres+"<<(CASE_BLOCK_SIZE*2)<<endl; cout<<" add bp, [data_pos]"<<endl; } if (optLevel>=2) { // -1/-3 cout<<" mov bp, "<<(CASE_BLOCK_SIZE*2)<<endl; cout<<" add bp, [data_pos]"<<endl; } cout<<" mov cx, "<<Text_Block_Size<<" ; [TEXT_BLOCK_SIZE]"<<endl; // [TEXT_BLOCK_SIZE] cout<<" mov ax,1300h"<<endl; cout<<" mov bx,0eh ; color"<<endl; cout<<" mov dx,0500h ; 5 0 "<<endl; cout<<" int 10h"<<endl; } else { // DOS if (optLevel==0) { cout<<" mov ax, [data_pos]"<<endl; cout<<" mov bx, [TEXT_BLOCK_SIZE]"<<endl; cout<<" mul bx"<<endl; cout<<" mov dx, text_data"<<endl; cout<<" add dx,ax ; offset "<<endl; } if (optLevel==1) { // -3 cout<<" mov dx, data_addres+"<<(CASE_BLOCK_SIZE*2)<<endl; cout<<" add dx, [data_pos]"<<endl; } if (optLevel>=2) {// -1 -3 cout<<" mov dx, "<<(CASE_BLOCK_SIZE*2)<<endl; cout<<" add dx, [data_pos]"<<endl; } cout<<" mov ah, 0x9 ; print [ds][dx]"<<endl; cout<<" int 21h ; dos, $"<<endl; } if (optLevel<3) cout<<"lReadKey: "<<endl; //cout<<" rep nop ; , "<<endl; cout<<" xor ax,ax"<<endl; cout<<" int 16h ; BIOS read key"<<endl; cout<<" xor ah,ah"<<endl; cout<<" sub al,'1' ; al , "<<endl; if (optLevel<3) cout<<" cmp ax,8"<<endl; // O3 - , , if (optLevel<3) cout<<" ja lReadKey"<<endl; cout<<" shl ax,1 ; ax=ax*2"<<endl; if (optLevel==0) { cout<<" mov bx, data_addres"<<endl; cout<<" add bx,ax ; bx = data_addres[key]"<<endl; cout<<" mov ax, [data_pos]"<<endl; cout<<" mov cx, [CASE_BLOCK_SIZE]"<<endl; cout<<" mul cx ; cx = [data_pos]"<<endl; cout<<" add bx,ax ; bx = data_addres[data_pos][key]"<<endl; } if (optLevel==1) { // -3 cout<<" add ax, data_addres ; bx = data_addres[key]"<<endl; cout<<" add ax, [data_pos]"<<endl; cout<<" mov bx,ax"<<endl; } if (optLevel>=2) { // -1 ; optLevel>2 -1-3 cout<<" add ax, [data_pos]"<<endl; cout<<" mov bx,ax ; TODO , xlat, ?"<<endl; } cout<<" mov ax,[bx]"<<endl; cout<<" mov [data_pos],ax ; ."<<endl; cout<<" jmp lblShowVariant"<<endl; // ;mov ax, 0x4c00; DOS EXIT, )) // ;int 0x21 cout<<"SECTION .data"<<endl; outDataFormatAsm(optLevel); } void outListingHTML() { cout<<"<html>"<<endl; cout<<"<head>"<<endl; cout<<"<!-- 0 JS -->"<<endl; cout<<"<script type=\"text-javascript\">"<<endl; cout<<"</script>"<<endl; cout<<"<style>"<<endl; cout<<" div {"<<endl; cout<<" height: 100%"<<endl; cout<<" }"<<endl; cout<<" td {"<<endl; cout<<" width:1em;"<<endl; cout<<" height:1em;"<<endl; cout<<" }"<<endl; cout<<"</style>"<<endl; cout<<"</head>"<<endl; cout<<"<body>"<<endl; for ( int i=0; i<data_pos; i++) { cout<<"<div id=\"p"<<i<<"\">"<<endl; if (text[i][0]=='X' || text[i][0]=='0' || text[i][0]=='.') { cout<<"<table border=\"border\">"<<endl; cout<<"<tr>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][0]<<"\">"<<text[i][6+2]<<"</a></td>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][1]<<"\">"<<text[i][7+2]<<"</a></td>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][2]<<"\">"<<text[i][8+2]<<"</a></td>"<<endl; cout<<"</tr><tr>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][3]<<"\">"<<text[i][3+1]<<"</a></td>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][4]<<"\">"<<text[i][4+1]<<"</a></td>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][5]<<"\">"<<text[i][5+1]<<"</a></td>"<<endl; cout<<"</tr><tr>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][6]<<"\">"<<text[i][0]<<"</a></td>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][7]<<"\">"<<text[i][1]<<"</a></td>"<<endl; cout<<" <td><a href=\"#p"<<data_addres[i][8]<<"\">"<<text[i][2]<<"</a></td>"<<endl; cout<<"</tr>"<<endl; cout<<"</table>"<<endl; } else cout<<"<a href=\"#p"<<data_addres[i][0]<<"\">"<<text[i]<<"</a>"<<endl; cout<<"</div>"<<endl; } cout<<"</body>"<<endl; cout<<"</html>"<<endl; } // ---- int main(int argc, char** argv) { int outFormat=-1; // 0 - assembler data, 1 - C array, -1 - . int optLevel=0; // 0 - , 1 - ( ), 2 - (), 3 - ()) for (int i=1; i<argc; i++) { if ( strcmp(argv[i],"--help")==0 || strcmp(argv[i],"-h")==0 ) { cout<<" . --help ."<<endl; cout<<" --help -h ."<<endl; cout<<" -a ( )"<<endl; cout<<" - "<<endl; cout<<" -sa "<<endl; cout<<" -s C"<<endl; cout<<" -sh HTML"<<endl; cout<<" -pvp ( )"<<endl; cout<<" -nodataopt , "<<endl; cout<<" -nowinopt , "<<endl; cout<<" (??) -nowinopt -nodataopt"<<endl; // TODO check text cout<<" :"<<endl; cout<<" -dosint (-3 ) DOS"<<endl; cout<<" -o0 (28 /25 dosint) . ."<<endl; cout<<" -o1 (-6 22 /19 dosint) . ."<<endl; cout<<" -o2 (-1 21/18 ) . , ()."<<endl; cout<<" -o3 (-2 19/16 ) o2 range check - if . !"<<endl; return 0; } else if ( strcmp(argv[i],"-a")==0 ) outFormat=0; else if ( strcmp(argv[i],"-c")==0 ) outFormat=1; else if ( strcmp(argv[i],"-sa")==0 ) outFormat=2; else if ( strcmp(argv[i],"-sc")==0 ) outFormat=3; else if ( strcmp(argv[i],"-sh")==0 ) outFormat=4; else if ( strcmp(argv[i],"-o0")==0 ) optLevel=0; else if ( strcmp(argv[i],"-o1")==0 ) optLevel=1; // -mul else if ( strcmp(argv[i],"-o2")==0 ) optLevel=2; // o1 + -add else if ( strcmp(argv[i],"-o3")==0 ) optLevel=3; // o2 + -range check else if ( strcmp(argv[i],"-dosint")==0 ) useDOSInt=true; else if ( strcmp(argv[i],"-pvp")==0 ) mode_pve=false; else if ( strcmp(argv[i],"-pve")==0 ) mode_pve=true; else if ( strcmp(argv[i],"-nodataopt")==0 ) optimizeDataFind=false; else if ( strcmp(argv[i],"-nowinopt")==0 ) casheWinVar=false; else { cout<<" \""<<argv[i]<<"\". --help ."<<endl; return 1; } } bool usePCSpeaker=false; if ( outFormat==0 || outFormat==2 ) { if (useDOSInt) End_Of_String = '$'; // DOS Text_Block_Size=13+3; usePCSpeaker=true; // } // init win text messages if (mode_pve) { if (usePCSpeaker) { // winText[win_x] = "You are won!\7\n"; winText[win_end]= "Not win. End\n"; winText[win_0] = "Bot won. 0\7\n"; } else { winText[win_x] = "You are won!"; winText[win_end]= "Not win. End"; winText[win_0] = "Bot won."; } } else { // PVP if (usePCSpeaker) { // winText[win_x] = "X are won!\7\n"; winText[win_end]= "Not win. End\n"; winText[win_0] = "0 won.\7\n"; } else { winText[win_x] = "X are won!"; winText[win_end]= "Not win. End"; winText[win_0] = "0 won."; } } generator_game_data( outFormat<2 ); if (outFormat==0) outDataFormatAsm(optLevel); if (outFormat==1) outDataFormatC(); if (outFormat==2) outListingAsm(optLevel); if (outFormat==3) outListingC(); if (outFormat==4) outListingHTML(); return 0; }
, "--help" , :
- 30 : «generator.exe -sa > name.asm», . nasm, «nasm -f bin name.asm -o asm30TTG.com», «asm30TTG.com» . , .
- UPD: 20 : «generator.exe -sa -o1 -dosint > name.asm», . DOS , .
- UPD2: 18 : «generator.exe -sa -o2 -dosint > name.asm», . -o3, 16 ( if), !
- : «generator.exe -sc > name.c» .
- HTML : «generator.exe -sh > name.html»
UPD: found a more compact solution in terms of the number of teams (19-20 teams). If data is presented not in the form of two separate arrays, but in the form of an array of structures, then fewer multiplications will be required to obtain the address. And since you only need to multiply one number per record, you can perform all multiplications in advance. To make it even shorter, I used DOS interrupts; fewer commands are spent on their call, but the color adjustment was lost.
Example for 20 assembler commands
SECTION .text org 0x100 ; .com lblShowVariant: mov ax,0x0001 ; clear screen, set graphic mode 40x25, color int 10h mov dx, data_addres+18 add dx, [data_pos] mov ah, 0x9 ; print [ds][dx] int 21h ; dos, $ lReadKey: xor ax,ax int 16h ; BIOS read key xor ah,ah sub al,'1' ; al , cmp ax,8 ja lReadKey shl ax,1 ; ax=ax*2 add ax, data_addres ; bx = data_addres[key] add ax, [data_pos] mov bx,ax ; mov ax,[ax] ? , mov ax,[bx] mov [data_pos],ax ; . jmp lblShowVariant SECTION .data ; Out data on assembler data format data_pos DW 0 ; max=394-1 ;CASE_BLOCK_SIZE DW 18 ;bytes (2 byte per 1 case) ;TEXT_BLOCK_SIZE DW 16 data_addres: DW 34, 1428, 2448, 3400, 4726, 5678, 6732, 9248, 11594 DB "...", 13,10, "...", 13,10, "...", 13,10, "$" DW 34, 68, 238, 306, 442, 476, 34, 578, 1122 DB "0..", 13,10, "...", 13,10, "X..", 13,10, "$" DW 68, 68, 102, 136, 136, 136, 68, 68, 170 DB "00.", 13,10, "...", 13,10, "XX.", 13,10, "$" DW 0, 0, 0, 0, 0, 0, 0, 0, 0 DB "You are won!", 7, 13,10, "$" DW 0, 0, 0, 0, 0, 0, 0, 0, 0 ...
UPD2: for 16 teams, without conditional branches.
Example of 16 assembler commands
SECTION .text org 0x100 ; .com lblShowVariant: mov ax,0x0001 ; clear screen, set graphic mode 40x25, color int 10h mov dx, 18 add dx, [data_pos] mov ah, 0x9 ; print [ds][dx] int 21h ; dos, $ xor ax,ax int 16h ; BIOS read key xor ah,ah sub al,'1' ; al , shl ax,1 ; ax=ax*2 add ax, [data_pos] mov bx,ax ; TODO , xlat, ? mov ax,[bx] mov [data_pos],ax ; . jmp lblShowVariant SECTION .data ; Out data on assembler format data_pos DW d_0 d_0 DW d_1, d_29, d_45, d_56, d_68, d_74, d_77, d_112, d_115 DB "...", 13,10, "...", 13,10, "...", 13,10, "$" d_1 DW d_1, d_2, d_7, d_9, d_13, d_14, d_1, d_16, d_28 DB "0..", 13,10, "...", 13,10, "X..", 13,10, "$" ...
')
Finally
30 Java Script, , . , . , .
UPD2: , 30 , 20 (), 16 ( - ). — ( «if»).
- 3x3.
| PVP, * | 294781 |
| PVP, | 7382 |
| PVE, | 1036 |
| PVE, | 306 |
| PVE, | 113 |
* , 255168. (PVE) , .
Source: https://habr.com/ru/post/207964/
All Articles