В прошлом году были популярны темы, как написать программу за 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) может отличаться, в зависимости от реализации.
