Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Брутфорс головоломки «Китайские шашки»

Anna | 24.06.2014 | нет комментариев
Дабы летом удерживать мозг в тонусе я скачал себе альманах головоломок. По началу задания были достаточно примитивными и не особенно требовательными к проявлению логики, но по ходу игры чувствовалось возрастающее усложнение.
В какой-то момент я завязнул на головоломке под наименованием «Китайские шашки». Редчайшие потуги решить её своими силами не приносили специальных плодов на протяжение длинного времени и в выводе я отложил свои муки с решением до наилучших времен.
Закончилась зимняя сессия, а до начала учебы еще пара недель — чем не «лучшие времена»? Я заглянул в интернет, чтобы проверить есть ли у данной головоломки вообще хоть какое-нибудь решение, и первые же итоги поискового запроса уговорили меня в том, что оно подлинно существует.
Я не стал подглядывать в прохождение, мне хотелось дойти до него своими силами — либо самому решить, либо написать программу, которая обнаружит мне это решение. Впрочем напрямую применить силу мозга мне так и не удалось, я очевидно упускал из виду что-то твердо главное для нахождения решения.
— «Ну всё, пускай эта головоломка поговорит с моим многоядерным ином!» — пронеслось у меня в голове, и я сел за написание брутфорса.Постановка задачи
Поле — 33 ячейки, 32 из которых заняты фишками. Цель — съесть максимально допустимое число фишек(должна остаться лишь одна). Есть дозволено только по вертикали и горизонтали таким образом:

Пример ходаПервая попытка решения
1-й брутфорс был написан без учета теории за пол-часа, его идея заключалась в рекурсивном спуске по дереву допустимых ходов, с рандомным выбором всякого дальнейшего хода.

Псевдо блок-схема первой версии

И всё это Диво крутилось в цикле. В первые 15 секунд он даже сумел обнаружить ход решения приводящий к 3 остающимся фишкам на поле, а в последующую минуту и к 2! Но веселье была не длинной, потому как рандом, пускай даже псевдо, сложно предсказуем — за ночь работы он не сумел больше приблизиться к решению. Становилось очевидна надобность рассмотрения вопроса с теоретической точки зрения.

Немножко теории
Если действующее игровое поле вытянуть в строку, то получится 33 разрядное двоичное число, где 1 соответствует ячейке с фишкой, а 0 пустой ячейке. Соответственно каждого состояний у поля может быть не огромнее 2^33 — 2, так как по правилам поле не может стать всецело пустым(неизменно остается правда бы одна фишка), либо всецело заполненным фишками(их дается 32 первоначально и огромнее теснее стать не может).
Это дозволено интерпретировать как то, что ходов у нас каждого не больше 8 589 934 590, что абсолютно перебираемо на домашнем компьютере. То есть необходимо легко написать Добросовестный полный перебор.

Вторая попытка решения
Избавившись от рандомной составляющей алгорифм брутфорса принял дальнейший вид:

Псевдо блок-схема 2-й версии

Данный брутфорс написанный на C на всех знаменитых мне оптимизациях в релиз-версии работал достаточно резво, перебирая чуть ли не 200 000 ходов в секунду, а значит для полного перебора потребовалось бы (2^33 — 2) / (2 * 10^5) /340/3c2/6b2/3403c26b29e301768787a8bf71a73865.jpg”/>
Псевдо блок-схема третьей версии с запоминанием рассчитанных полей

Только вот это дело оказалось крайне убыточным, если беречь просчитанные поля в оперативной памяти, то получается в совершенном случае что нам понадобится 33 бита на одно поле, а их даже с учетом сделанного первого хода (2^33 — 2) / 4, то есть памяти потребуется на хранение всех просчитанных полей ((2^33 — 2) / 4) * 33) / (8 * 2^20) ndmk!lt; 2) || (j > 4))) out << ‘*’ << ‘ ‘; else out << fld[i][j] << ‘ ‘; } out << ‘n’ << std::flush; } return out; } // To display a some message void message(const std::string msg = “”) { std::cout << “Message: ” << msg << std::endl; system(“pause”); } // Returns a pointer to a memory was allocated for a field, or nullptr in error case field alloc_mem_for_field() { field fld = nullptr; try { fld = new bool*[x]; for (unsigned i = 0; i < x; i) { fld[i] = new bool[y]; } } catch(std::bad_alloc) { fld = nullptr; message(“Memory out in alloc_mem_for_field()”); } return fld; } // Copy a field and returns a reference on it, or nullptr in error case field copy_field(field fld_dest, const field fld_source) { if (fld_dest == nullptr) { if ((fld_dest = alloc_mem_for_field()) != nullptr) { for (unsigned i = 0; i < x; i) { for (unsigned j = 0; j < y; j) { fld_dest[i][j] = fld_source[i][j]; } } } } else { for (unsigned i = 0; i < x; i) { for (unsigned j = 0; j < y; j) { fld_dest[i][j] = fld_source[i][j]; } } } return fld_dest; } // First initialize of a field void init_field(field &fld) { for (unsigned i = 0; i < x; i) { for (unsigned j = 0; j < y; j) { if ( (((i == 0) || (i == 1)) || ((i == (x – 1)) || (i == (x – 2)))) && (((j == 0) || (j == 1)) || ((j == (y – 1)) || (j == (y – 2)))) ) fld[i][j] = (bool)2; // Not used else fld[i][j] = 1; } } // Make the first move to reduce space of moves on 3/4 fld[(x / 2)][(y / 2)] = 1; fld[(x / 2)][(y / 2 - 1)] = 0; fld[(x / 2)][(y / 2) - 2] = 0; } // Returns num of chips on field int IsWin(const field &fld) { int k = 0; for (unsigned i = 0; i < x; i) { for (unsigned j = 0; j < y; j) { if ( (i < 2 || i > 4) && (j < 2 || j > 4) ) continue; if (fld[i][j] == 1) k; } } return k; } // Free alloc memory void free_mem_from_field(field &fld) { if (fld == nullptr) { message(“Attempt to delete nullptr in free_mem_from_field()”); return; } for (unsigned i = 0; i < y; i) { delete[] fld[i]; } delete[] fld; fld = nullptr; } // Returns true if a cell is empty bool IsCell(const field &fld, const int lx, const int ly) { if ( (lx > 0 && ly > 0) && (lx < (int)x && ly < (int)y) && (!((lx < 2 || lx > 4) && (ly < 2 || ly > 4))) ) { if (fld[(unsigned)lx][(unsigned)ly] == 0) return true; } return false; } // Returns true if a cell has a chip bool IsChip(const field &fld, const int lx, const int ly) { if ( (lx > 0 && ly > 0) && (lx < (int)x && ly < (int)y) && (!((lx < 2 || lx > 4) && (ly < 2 || ly > 4))) ) { if (fld[(unsigned)lx][(unsigned)ly] == 1) return true; } return false; } // Returns a pointer on a list of all moves for the current field // or nullptr if moves doesn’t exist std::list<move*> *get_all_moves(const field &fld) { std::list<move*> *buf = nullptr; try { buf = new std::list<move*>; move* m = nullptr; for (int i = 0; (unsigned)i < x; i) { for (int j = 0; (unsigned)j < y; j) { if ((fld[i][j] == 1) && (!(((i < 2) || (i > 4)) && ((j < 2) || (j > 4))))) { if (IsCell(fld, i 2, j)) { if (IsChip(fld, i 1, j)) { m = new move(); m->first.first = i; m->first.second = j; m->second.first = i 2; m->second.second = j; buf->push_back(m); } } if (IsCell(fld, i – 2, j)) { if (IsChip(fld, i – 1, j)) { m = new move(); m->first.first = i; m->first.second = j; m->second.first = i – 2; m->second.second = j; buf->push_back(m); } } if (IsCell(fld, i, j 2)) { if (IsChip(fld, i, j 1)) { m = new move(); m->first.first = i; m->first.second = j; m->second.first = i; m->second.second = j 2; buf->push_back(m); } } if (IsCell(fld, i, j – 2)) { if (IsChip(fld, i, j – 1)) { m = new move(); m->first.first = i; m->first.second = j; m->second.first = i; m->second.second = j – 2; buf->push_back(m); } } } } } if (buf->size() == 0) { delete buf; buf = nullptr; } } catch (std::bad_alloc) { delete buf; buf = nullptr; message(“Memory out in get_all_moves()”); } return buf; }//*/ // To make a move field make_move(field fld, const move &mv) { if (fld == nullptr) { message(“Attempt to move on empty field in make_move()”); return fld; } if (mv.first.first != mv.second.first) { if (mv.first.first < mv.second.first) { fld[mv.first.first 1][mv.second.second] = 0; } else fld[mv.first.first - 1][mv.second.second] = 0; } else if (mv.first.second != mv.second.second) { if (mv.first.second < mv.second.second) { fld[mv.first.first][mv.first.second 1] = 0; } else fld[mv.first.first][mv.first.second - 1] = 0; } else { message(“Move is incorrect, error in get_all_moves()”); return fld; } fld[mv.first.first][mv.first.second] = 0; fld[mv.second.first][mv.second.second] = 1; return fld; } // Recursive passage all the moves void bruteforce(field fld) { static bool display = false; static int lvl = 33; static time_t counter = 0; // Num of checked field counter; // Num 7000 is empirical // Once we get the conclusion of the 7000, it allows the processor // to be optimally loaded, and we see a progress if ((counter % 7000) == 0) { display = true; } if ( counter > 33 ) { int ibuf = path_to_win.size(); if (lvl > ibuf) lvl = ibuf; } std::list<move*> *b = get_all_moves(fld); step buf; if (b != nullptr) { buf = step(fld, b); path_to_win.push_back(fld); } else { int res = IsWin(fld); path_to_win.push_back(fld); if (display == true) { system(“cls”); std::cout << “Min level: ” << lvl << “n<” << counter << ‘>’ << “nCurrent result:n” << fld << std::endl; display = false; } if (res == win_condition) { std::cout << “Num of checked fields: ” << fld_buf.size() << “nSize of the path_to_win: ” << path_to_win.size() << std::endl; std::ofstream winpath_to_win(“path_to_win.txt”); if (winpath_to_win) { for (std::list<field>::const_iterator it = path_to_win.begin(); it != path_to_win.end(); it) { winpath_to_win << (*it) << std::endl; } winpath_to_win.close(); } for (std::list<field>::const_iterator it = path_to_win.begin(); it != path_to_win.end(); it) { std::cout << (*it) << std::endl; } system(“pause”); } path_to_win.pop_back(); return; } field fwithmove = nullptr; for ( std::list<move*>::iterator it = buf.second->begin(); it != buf.second->end(); fwithmove = nullptr, buf.second->pop_front(), it = buf.second->begin() ) { fwithmove = copy_field(fwithmove, buf.first); // Make move in copy of the buf.first field, // buf.first field not changed and use to copy in next iteration make_move(fwithmove, *(*it)); Field *f = new Field(fwithmove); if (fld_buf.count(*f)) { free_mem_from_field(fwithmove); delete (*it); continue; } else fld_buf.insert(*f); delete f; bruteforce(fwithmove); free_mem_from_field(fwithmove); // Free alloc memory for the fwithmove field, where we did move delete (*it); // Free memory from under “move” in list<move*> which we did } path_to_win.pop_back(); delete buf.second; } public: China_Checkers_Hack(const int _x = 7, const int _y = 7, const int wincondition = 1) : win_condition(wincondition) { x = _x; y = _y; field main_field; if ((main_field = alloc_mem_for_field()) != nullptr) { init_field(main_field); bruteforce(main_field); free_mem_from_field(main_field); } else message(“Memory out, your computer gonna update RAM!”); } ~China_Checkers_Hack() { for (std::list<field>::iterator it = path_to_win.begin(); it != path_to_win.end(); it) { free_mem_from_field(*it); } } }; } int main(int argc, char* argv[]) { China_Checkers::China_Checkers_Hack bruteforce; system(“pause”); return 0; }

Пример обнаруженного решения

* * 1 1 1 * *
* * 1 0 1 * *
1 1 1 0 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * ** * 1 1 1 * *
* * 1 0 1 * *
1 0 0 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * ** * 1 1 1 * *
* * 1 0 1 * *
1 1 0 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 1 1 1 * *
* * 1 0 1 * *
0 0 1 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 1 1 1 * *
* * 1 0 1 * *
0 1 0 0 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 1 1 0 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
1 1 0 0 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 1 1 1
1 1 0 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 1 1 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 1 0 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 1 1 * *
0 0 0 0 1 1 1
0 0 1 0 0 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 1 0 1 1
0 0 1 0 1 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 1 1 0 0
0 0 1 0 1 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 0 0 1 0
0 0 1 0 1 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 0 0 1 1
0 0 1 0 1 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 0 1 0 0
0 0 1 0 1 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 1 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 1 0 0
0 0 1 0 1 0 0
0 0 1 0 0 1 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 1 1 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 1 0 0 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 1 0 0 0 0
* * 0 1 0 * *
* * 0 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 0
* * 1 1 0 * *
* * 0 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 0
* * 1 1 0 * *
* * 1 0 0 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 1 0 0 0 0
* * 0 1 0 * *
* * 0 0 0 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
* * 0 1 0 * *
* * 0 0 0 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
* * 0 0 0 * *
* * 0 1 0 * *

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB