алиса и боб перебирают все варианты
Apr. 27th, 2024 06:40 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(эта запись - не про математику, а про программирование. В конце ее я предлагаю соревнование: приз за лучшую программу)
Недавно я несколько раз писал об игре Алисы и Боба с честной монетой:
Алиса и Боб вместе бросают одну честную монету 100 раз. Каждый раз, когда во время бросков выпадают подряд два орла ОО, Алиса получает очко. Когда выпадает ОР, Боб получает очко. Побеждает тот, у кого больше очков после 100 бросков.
Эта запись - не про математику, а про программирование. Чтобы проверить свои мысли об этой игре, я написал код, который проходит по *всем* возможным играм - но не 100 бросков, это было бы 2^100 игр, слишком много - а скажем 26. Для каждой возможной игры, т.е. вариантов бросков, надо посчитать, сколько очков у каждого и кто победил. В конце мы хотим знать, сколько из, скажем, 2^26 возможных игр - победы Боба, сколько победы Алисы, сколько ничьи.
Мой первый вариант был на Питоне. Потом мне стало любопытно, насколько быстро это можно сделать, и я переписал его на C. В этой быстрой версии игра представлена с помощью числа - его биты это результаты бросков - и я проверяю, есть ли 11 (Алиса) или 10 (Боб) в первых двух битах, потом сдвигаю все число вправо на 1, проверяю опять, и так в цикле 25 раз (если длина игры 26). Эта программа перебрала все 2^26 игр за полторы секунды (Питон за много минут, не помню уже сколько).
Тогда мне стало интересно, как еще можно это убыстрить, и сколько бросков я смогу перебрать без проблем на обычном десктопе. Программа прошла еще через две версии, и в конце концов я закончил на следующей (показываю только главную часть):
Для максимальной эффективности ее надо компилировать так: gcc -O3 -march=native, тогда компилятор использует инструкцию popcnt вместо функции __builtin_popcount.
Наверняка для MSVC тоже можно найти правильные параметры и способ использовать эту инструкцию, я не проверял (я компилировал под 64-битным Windows, но gcc).
Эта версия проходит через все 40-бросковые игры за 25 минут. Это примерно триллион вариантов, довольно круто по-моему.
Предположим, я захотел бы таким образом узнать точное число побед Алисы и Боба на игре из 64 бросков. Используя эту программу на одном компьютере, я ждал бы ответа 38 лет. Но ясно, что эту программу тривиально легко разбить на параллельные вычисления. На моем десктопе 28 ядер на двух процессорах; если 25 из них занять этим вычислением, то машина справится уже за полгода, а тысяча машин - за 12 часов.
Я не буду это делать. Во-первых, я уже не работаю в Гугле и у меня нет тривиально легкого и бесплатного доступа к 1000 машин. Во-вторых, на то мы и программисты, чтобы не все и всегда делать в лоб. Найти точное число побед Алисы и Боба в первоначальной версии игры, со 100 бросками, полным перебором - не сможет, думаю, вся наша цивилизация за год или десять лет. Но по-моему, должно быть не слишком тяжело сделать это умнее.
Я предлагаю конкурс: написать программу, которая должна как можно быстрее вычислить и напечатать правильное число побед Алисы и Боба в игре из 100 бросков. Варианты можно предлагать в течение недели. Автор варианта, который делает это быстрее всех (и правильно), получает приз в $100. Для этого надо не только дать ответ, но и исходный код, и в случае если это нетривиально - пояснения, как его скомпилировать или запустить (под стандартным Windows или Линуксом), а также время, за которое программа выдает ответ у вас на компьютере. В случае близких по времени результатов я буду сравнивать их, запуская на своем десктопе (два процессора Intel Xeon [Bad username or site: 2 @ 40GHz] по 14 ядер в каждом, 32GB памяти, стандартная Windows 10, в случае надобности Линукса установлю на ней WSL2). Можно посылать больше одного варианта. Посылать можно в комментариях или почтой на avorobey в GMail. Вроде ничего не забыл, но если непонятно, можно задавать вопросы.
(разумеется, программа не может просто напечатать вычисленный отдельно автором ответ, а должна "честно" его найти)
Недавно я несколько раз писал об игре Алисы и Боба с честной монетой:
Алиса и Боб вместе бросают одну честную монету 100 раз. Каждый раз, когда во время бросков выпадают подряд два орла ОО, Алиса получает очко. Когда выпадает ОР, Боб получает очко. Побеждает тот, у кого больше очков после 100 бросков.
Эта запись - не про математику, а про программирование. Чтобы проверить свои мысли об этой игре, я написал код, который проходит по *всем* возможным играм - но не 100 бросков, это было бы 2^100 игр, слишком много - а скажем 26. Для каждой возможной игры, т.е. вариантов бросков, надо посчитать, сколько очков у каждого и кто победил. В конце мы хотим знать, сколько из, скажем, 2^26 возможных игр - победы Боба, сколько победы Алисы, сколько ничьи.
Мой первый вариант был на Питоне. Потом мне стало любопытно, насколько быстро это можно сделать, и я переписал его на C. В этой быстрой версии игра представлена с помощью числа - его биты это результаты бросков - и я проверяю, есть ли 11 (Алиса) или 10 (Боб) в первых двух битах, потом сдвигаю все число вправо на 1, проверяю опять, и так в цикле 25 раз (если длина игры 26). Эта программа перебрала все 2^26 игр за полторы секунды (Питон за много минут, не помню уже сколько).
Тогда мне стало интересно, как еще можно это убыстрить, и сколько бросков я смогу перебрать без проблем на обычном десктопе. Программа прошла еще через две версии, и в конце концов я закончил на следующей (показываю только главную часть):
#define TURNS 40
#define MAXN (1ULL << TURNS)
unsigned long long i, ascore, bscore;
for (i = 0; i < MAXN; ++i) {
ascore = __builtin_popcount(i&(i>>1));
bscore = __builtin_popcount(i&((~i & (MAXN-1))>>1));
awins += (ascore > bscore);
bwins += (ascore < bscore);
}
Для максимальной эффективности ее надо компилировать так: gcc -O3 -march=native, тогда компилятор использует инструкцию popcnt вместо функции __builtin_popcount.
Наверняка для MSVC тоже можно найти правильные параметры и способ использовать эту инструкцию, я не проверял (я компилировал под 64-битным Windows, но gcc).
Эта версия проходит через все 40-бросковые игры за 25 минут. Это примерно триллион вариантов, довольно круто по-моему.
Предположим, я захотел бы таким образом узнать точное число побед Алисы и Боба на игре из 64 бросков. Используя эту программу на одном компьютере, я ждал бы ответа 38 лет. Но ясно, что эту программу тривиально легко разбить на параллельные вычисления. На моем десктопе 28 ядер на двух процессорах; если 25 из них занять этим вычислением, то машина справится уже за полгода, а тысяча машин - за 12 часов.
Я не буду это делать. Во-первых, я уже не работаю в Гугле и у меня нет тривиально легкого и бесплатного доступа к 1000 машин. Во-вторых, на то мы и программисты, чтобы не все и всегда делать в лоб. Найти точное число побед Алисы и Боба в первоначальной версии игры, со 100 бросками, полным перебором - не сможет, думаю, вся наша цивилизация за год или десять лет. Но по-моему, должно быть не слишком тяжело сделать это умнее.
Я предлагаю конкурс: написать программу, которая должна как можно быстрее вычислить и напечатать правильное число побед Алисы и Боба в игре из 100 бросков. Варианты можно предлагать в течение недели. Автор варианта, который делает это быстрее всех (и правильно), получает приз в $100. Для этого надо не только дать ответ, но и исходный код, и в случае если это нетривиально - пояснения, как его скомпилировать или запустить (под стандартным Windows или Линуксом), а также время, за которое программа выдает ответ у вас на компьютере. В случае близких по времени результатов я буду сравнивать их, запуская на своем десктопе (два процессора Intel Xeon [Bad username or site: 2 @ 40GHz] по 14 ядер в каждом, 32GB памяти, стандартная Windows 10, в случае надобности Линукса установлю на ней WSL2). Можно посылать больше одного варианта. Посылать можно в комментариях или почтой на avorobey в GMail. Вроде ничего не забыл, но если непонятно, можно задавать вопросы.
(разумеется, программа не может просто напечатать вычисленный отдельно автором ответ, а должна "честно" его найти)
