В прошлом году были популярны темы, как написать программу за 30 строк кода. Все примеры были сделаны на JavaScript. Для запуска таких программ требуется не только веб страница, но и браузер, разные библиотеки, ядро ОС. На самом деле работают не 30 строк кода, а десятки, сотни мегабайты программного кода, находящиеся в памяти компьютера.
А можно ли написать не полностью бесполезную программу за 30 строк ассемблера, без лишних библиотек и мегабайт ОС?
В этой статье я опишу, как можно сделать крестики-нолики за 30 строк ассемблера. UPD Теперь всего за 20 строк. UPD2 И 18 или 16 строк без единого условного ветвления.
Задача: сделать рабочую игру крестики-нолики.
Правила «игры»:
Сложность реализации за 30 строк ассемблера заключается в том, что на ассемблере простой цикл занимает несколько строк (команд). Каждая операция — это отдельная команда, а значит новая строка.
Самая простая реализация крестиков-ноликов — это матрица со значениями клеток, которые нужно в циклах сравнивать для определения победы, в циклах выводить на экран. По этому сделать игру за 30 строк кода на первый взгляд кажется нереально.
Так как если хранить игровое поле в виде массива, а уж тем более матрицы, то потребуется несколько циклов, чтобы определять победу. Можно вместить всё игровое поле, размером 3 на 3 (хватит и на 4*4) в 4 байта, или 2 машинных слова, по два байта на игрока. Так можно сократить проверку победы перебором восьми вариантам победы, представленным в виде восьми чисел (сравнивая совпадения бит с int map_x, int map_0).
Для проверки идеи сделал реализацию на Си.
Игра выводит игровое поле на экран в следующем виде:
Пользователь нажимает на цифровой клавиатуре цифры, по позиции соответствующие клетке. Например цифра 5 — это центр, 1 — левая-нижняя клетка.
Слишком много кода. Декомпилировав полученную программу, увидел, что команд больше сотни, не считая вызова printf и scanf. Может попробовать самому перевести на ассемблер?
Только функция проверки победы занимает около 30 команд. А ещё остались функции вывода результата на экран, чтение позиции с клавиатуры.
Этот вариант не подходит. Зато такая реализация может поместиться в БНЗ, размер которого 512 байт первого сектора диска.
А если подумать, как это можно решить на HTML за 0 строк JavaScript?
Каждый вариант игры записать как готовую строку вывода на экран, и к каждому варианту добавить адреса следующих записей, которые нужно показывать при нажатии соответствующих кнопок.
На HTML это реализовывается с помощью анкоров и длинной «партянки». На ассемблере, или Си нужно сделать программу, которая просто выводит текст на экран, в зависимости от нажатия кнопок.
Сама программа при этом получится маленькой, но данные, нужные для её работы огромные.
Пример алгоритма, реализованного на Си:
А что будет на ассемблере?
Программа работает, требуются функции только BIOS, может запуститься без операционной системы, только надо поправить регистры в начале программы (добавить mov ax,cs; mov ds,ax; mov es,ax..., убрать org 0x100 в начале программы), и прописать её в загрузчике. Получилось украсить вывод программы, изменив цвет текста. Можно вставить звук, добавив символы с кодом 7 в текст победных строк (PC speaker).
Половина дела сделана. Теперь осталось написать массивы данных, состоящие из нескольких тысяч адресов и вариантов игры.
Приблизительные расчёты размера данных:
Итого около 31-34 байт на каждый вариант. Всего вариантов игры может быть 9! (9*8*7*6*5*4*3*2*1 ). Это много, но нам нужно хранить только набор вариантов для игрока, так как варианты для компьютера определены на этапе генерации данных. По этому вариантов будет не больше 9*7*5*3*1 = 945. Если учесть, что некоторые варианты могут быть завершены до заполнения последней клетки (победы, поражения), то вариантов будет ещё меньше. Итого памяти, требуемой на хранения всех вариантов и адресов, потребуется не более 32130 байт (34*945), что уместится на одной странице памяти (65535 байт).
Чтобы получить эти данные, была написана программа на C++, генерирующая все варианты и выводящая их в виде массива для C/C++ и данных для ассемблера. Затем была добавлена возможность вывода полного исходника на C, ассемблере, затем и HTML с 0 строк JS.
Компилируете, запускаете с параметром "--help" для вызова справки, или сразу получаете исходники:
UPD: обнаружил более компактное решение, с точки зрения количества команд (19-20 команд). Если представить данные не в виде двух отдельных массивов, а в виде массива из структур, то потребуется меньше умножений, для получения адреса. А раз умножать потребуется только одно число на запись, то можно произвести все умножения заранее. Чтобы ещё сократить, использовал прерывания DOS, н�� их вызов тратится меньше команд, но потерялась настройка цвета.
UPD2: за 16 команд, без условных ветвлений.
Сделать игру за 30 строк кода можно не только на Java Script, но и на других языках, например на ассемблере. Компилятор может оптимизировать программу и на минимальное время выполнения, и на размер. Но выбор алгоритма ускоряет работу или сокращает размер программы намного больше, чем может это сделать оптимизация.
UPD2: Позже выяснилось, что размер в 30 команд не предел, и можно сократить до 20 (стабильно), или до 16 команд (нестабильно из-за отсутствия проверки выхода за границы диапазона). Заметил интересную особенность — данный код способен работать без условных ветвлений (без «if»).
При работе генератора было рассчитано количество вариантов игры крестики-нолики на поле 3x3.
* в Википедии написано, что вариантов всего 255168. Результат при игре с компьютерным игроком (PVE) может отличаться, в зависимости от реализации.
А можно ли написать не полностью бесполезную программу за 30 строк ассемблера, без лишних библиотек и мегабайт ОС?
В этой статье я опишу, как можно сделать крестики-нолики за 30 строк ассемблера. UPD Теперь всего за 20 строк. UPD2 И 18 или 16 строк без единого условного ветвления.
Задача: сделать рабочую игру крестики-нолики.
Правила «игры»:
- до 30 строк чистых ассемблерных команд. Без жульничества в виде записи машинного кода в одну строку db ......
- нет ограничения на размер данных. Игра в 0 строк JS имела немало данных в виде HTML и CSS
- не использовать сторонние библиотеки, лучше без прерываний ОС, только BIOS
- при этом программа должна работать
Сложность реализации за 30 строк ассемблера заключается в том, что на ассемблере простой цикл занимает несколько строк (команд). Каждая операция — это отдельная команда, а значит новая строка.
Пример, показывающий сколько строк нужно на циклы, для тех кто плохо знает ассемблер
// На 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), те. бездействие
}
Самая простая реализация крестиков-ноликов — это матрица со значениями клеток, которые нужно в циклах сравнивать для определения победы, в циклах выводить на экран. По этому сделать игру за 30 строк кода на первый взгляд кажется нереально.
Первая попытка — сократить массивы и оптимизировать
Так как если хранить игровое поле в виде массива, а уж тем более матрицы, то потребуется несколько циклов, чтобы определять победу. Можно вместить всё игровое поле, размером 3 на 3 (хватит и на 4*4) в 4 байта, или 2 машинных слова, по два байта на игрока. Так можно сократить проверку победы перебором восьми вариантам победы, представленным в виде восьми чисел (сравнивая совпадения бит с int map_x, int map_0).
Для проверки идеи сделал реализацию на Си.
Игра выводит игровое поле на экран в следующем виде:
Пользователь нажимает на цифровой клавиатуре цифры, по позиции соответствующие клетке. Например цифра 5 — это центр, 1 — левая-нижняя клетка.
Вариант 1, на Си
/*
* 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);
}
Слишком много кода. Декомпилировав полученную программу, увидел, что команд больше сотни, не считая вызова printf и scanf. Может попробовать самому перевести на ассемблер?
Вариант 1, функция testWon(), переписанная на ассемблер
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;
}
Только функция проверки победы занимает около 30 команд. А ещё остались функции вывода результата на экран, чтение позиции с клавиатуры.
Этот вариант не подходит. Зато такая реализация может поместиться в БНЗ, размер которого 512 байт первого сектора диска.
Второй способ — как сделать то же на HTML за 0 строк JS?
А если подумать, как это можно решить на HTML за 0 строк JavaScript?
Каждый вариант игры записать как готовую строку вывода на экран, и к каждому варианту добавить адреса следующих записей, которые нужно показывать при нажатии соответствующих кнопок.
На HTML это реализовывается с помощью анкоров и длинной «партянки». На ассемблере, или Си нужно сделать программу, которая просто выводит текст на экран, в зависимости от нажатия кнопок.
Сама программа при этом получится маленькой, но данные, нужные для её работы огромные.
Пример алгоритма, реализованного на Си:
#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);
}
А что будет на ассемблере?
Вариант 2, на ассемблере за 29 команд, работающий на прерываниях BIOS!
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!", " "
...
Программа работает, требуются функции только BIOS, может запуститься без операционной системы, только надо поправить регистры в начале программы (добавить mov ax,cs; mov ds,ax; mov es,ax..., убрать org 0x100 в начале программы), и прописать её в загрузчике. Получилось украсить вывод программы, изменив цвет текста. Можно вставить звук, добавив символы с кодом 7 в текст победных строк (PC speaker).
Половина дела сделана. Теперь осталось написать массивы данных, состоящие из нескольких тысяч адресов и вариантов игры.
Приблизительные расчёты размера данных:
- 9 клеток (кнопок), адресация word => 18 байт на каждый вариант игрового поля
- 13-16 байт текстовое поле
Итого около 31-34 байт на каждый вариант. Всего вариантов игры может быть 9! (9*8*7*6*5*4*3*2*1 ). Это много, но нам нужно хранить только набор вариантов для игрока, так как варианты для компьютера определены на этапе генерации данных. По этому вариантов будет не больше 9*7*5*3*1 = 945. Если учесть, что некоторые варианты могут быть завершены до заполнения последней клетки (победы, поражения), то вариантов будет ещё меньше. Итого памяти, требуемой на хранения всех вариантов и адресов, потребуется не более 32130 байт (34*945), что уместится на одной странице памяти (65535 байт).
Чтобы получить эти данные, была написана программа на C++, генерирующая все варианты и выводящая их в виде массива для C/C++ и данных для ассемблера. Затем была добавлена возможность вывода полного исходника на C, ассемблере, затем и HTML с 0 строк JS.
Исходник генератора данных на C++ для игр в 30 строк кода assembler (UPD или 20 строк с использованием DOS прерываний, но без цветов), 12 строк С, и 0 строк 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: обнаружил более компактное решение, с точки зрения количества команд (19-20 команд). Если представить данные не в виде двух отдельных массивов, а в виде массива из структур, то потребуется меньше умножений, для получения адреса. А раз умножать потребуется только одно число на запись, то можно произвести все умножения заранее. Чтобы ещё сократить, использовал прерывания DOS, н�� их вызов тратится меньше команд, но потерялась настройка цвета.
Пример за 20 ассемблерных команд
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: за 16 команд, без условных ветвлений.
Пример из 16 ассемблерных команд
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, "$"
...
В заключение
Сделать игру за 30 строк кода можно не только на Java Script, но и на других языках, например на ассемблере. Компилятор может оптимизировать программу и на минимальное время выполнения, и на размер. Но выбор алгоритма ускоряет работу или сокращает размер программы намного больше, чем может это сделать оптимизация.
UPD2: Позже выяснилось, что размер в 30 команд не предел, и можно сократить до 20 (стабильно), или до 16 команд (нестабильно из-за отсутствия проверки выхода за границы диапазона). Заметил интересную особенность — данный код способен работать без условных ветвлений (без «if»).
При работе генератора было рассчитано количество вариантов игры крестики-нолики на поле 3x3.
| Условия расчёта | Количество вариантов |
|---|---|
| PVP, с повторениями* | 294781 |
| PVP, без повторений | 7382 |
| PVE, с повторениями | 1036 |
| PVE, без повторений | 306 |
| PVE, без повторений и завершающих комбинаций | 113 |
* в Википедии написано, что вариантов всего 255168. Результат при игре с компьютерным игроком (PVE) может отличаться, в зависимости от реализации.