Симулируем вероятности в сложной логической задаче — Журнал «Код» программирование без снобизма

Вчера у нас вышла задача про игральные кубики и вероятности. Вот коротко суть. Есть 4 игральных кубика, на каждом — свои числа:

на первом — 3, 3, 3, 3, 3, 3 (на каждой стороне по тройке);
на втором — 0, 0, 4, 4, 4, 4;
на третьем — 1, 1, 1, 5, 5, 5;
на четвёртом — 2, 2, 2, 2, 6, 6.

Первый игрок выбирает один кубик, потом выбирает второй, оба кидают 1000 раз. Выигрывает тот, у кого за всё время было больше побед. Какой кубик взять второму игроку?

Когда мы решали её самостоятельно, первым интуитивным желанием было написать код, который тупым перебором найдёт лучший кубик. Но тогда писать тупой код было лень, и мы решили задачу логически. А потом время появилось, и теперь мы решим её через симуляцию вероятностей.

Логика проекта

Чтобы понять, какой кубик выбрать, сделаем так:

Создадим 4 виртуальных кубика.
Бросим каждый 1000 раз и запишем результаты бросков.
Попарно посчитаем количество побед и занесём данные в виртуальную таблицу.
Спросим, какой кубик выбрал первый игрок.
Посмотрим по таблице, у какого кубика больше всего выигрышей.
Этот кубик мы порекомендуем выбрать второму игроку.

Если нужна более высокая точность расчётов, можно бросать кубики не тысячу раз, а 10 тысяч, 100 тысяч или миллион. Чем больше бросков — тем стабильнее вероятность выигрыша правильного кубика.

Готовим переменные

Чтобы мы могли гибко управлять количеством бросков, выделим их в отдельную переменную:

// количество бросков var rollCount = 100000;

Сразу сделаем переменную для кубика, который нам в конце посоветует программа, и создадим виртуальные кубики с разными числами на гранях. Сюда же добавим описание каждого кубика — оно нам пригодится в вопросе о выборе соперника и для рекомендации в конце:

// кубик, который нам нужно выбрать
var choose;

// виртуальные кубики с числами на гранях
var c1 = [3,3,3,3,3,3];
var c2 = [0,0,4,4,4,4];
var c3 = [1,1,1,5,5,5];
var c4 = [2,2,2,2,6,6];

// названия кубиков
var cubeOptions = [];
cubeOptions[0] = 'кубик с тройками';
cubeOptions[1] = 'кубик с нолями и четвёрками';
cubeOptions[2] = 'кубик с единицами и пятёрками';
cubeOptions[3] = 'кубик с двойками и шестёрками';

Бросаем кубики

Когда мы бросаем кубик, каждая сторона выпадает с одинаковой вероятностью 1/6. Это значит, что мы можем взять случайное число от 0 до 5 и представить его как результат броска: какое число выпадет, значение той грани и смотрим. А от нуля мы считаем потому, что так принято в ИТ: элементы массива начинаются с нулевого.

Чтобы было удобнее, сделаем отдельную функцию по броскам — она вернёт случайное число в нашем диапазоне:

// виртуальный бросок кубика function diceRoll(){ // на выходе получаем целое число от 0 до 5, которое соответствует выпавшей стороне кубика return Math.floor(Math.random() * 6) }

Теперь будем бросать все кубики по очереди и смотреть на значение выпавшей грани. Все результаты мы запишем в двумерный массив: каждая строка будет отвечать за результаты бросков своего кубика:

// перебираем по очереди все 4 кубика
for (let i = 0; i < rollCount; i++) {
    // и виртуально подкидываем их, записывая результат в массив
    result[0][i] = c1[diceRoll()];
    result[1][i] = c2[diceRoll()];
    result[2][i] = c3[diceRoll()];
    result[3][i] = c4[diceRoll()];
}

Считаем победы

Все результаты бросков у нас записаны в двумерном массиве из четырёх строк, где каждая строка — это отдельный массив из всех бросков. Соответственно, нам нужна функция, которой мы сможем отдать два массива, а в ответ от которой получим количество побед второго массива над первым. Звучит сложно, но в коде всё проще:

// считаем количество побед, у кого больше — у соперника или у игрока
// на вход функции подаём два массива — с бросками соперника и со своими бросками
function winCount(player,you){
    // на старте побед пока нет
    var win = 0;
    // перебираем все броски
    for (let i = 0; i < rollCount; i++) {
        // если по результатам попарного броска у нас больше, чем у соперника
        if (player[i] < you[i]){
            // то увеличиваем на единицу количество побед
            win += 1;
        }
    }
    // возвращаем количество побед в этой паре
    return win;
}

Теперь, когда мы умеем считать победы, создадим виртуальную таблицу побед — двумерный массив 4 на 4. Работать он будет так:

на первой строке будут результаты побед других кубиков над первым кубиком (с тройками);
на второй строке — результаты побед других кубиков над вторым кубиком (с четвёрками) и так далее.

Так как мы с соперником не можем выбрать один и тот же кубик, то при совпадении номеров кубиков мы будем ставить в эту ячейку ноль. Это будет признаком того, что выбирать этот кубик не нужно (его уже взял соперник).

// создаём двумерный массив для виртуальной таблицы побед
var winResult = new Array(4);
// таблица будет 4 на 4, пока пустая
for (let i = 0; i < 4; i++) {
    winResult[i] = new Array(4); 
}

// заполняем таблицу побед
for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++){
        // чтобы кубик не соревновался сам с собой, в этом месте ставим ноль
        if (i == j) { winResult[i][j] = 0 }
        else {
            // заносим в таблицу результат побед второго кубика над первым
            winResult[i][j] = winCount(result[i],result[j])
        }
    }
}

Спрашиваем про кубик соперника

Самая простая часть программы. Всё, что нам нужно сделать, — узнать, какой кубик выбрал соперник. Чтобы было удобнее, номера выбора соответствуют наибольшим значениям каждого кубика. Если пользователь введёт какое-то другое значение — выводим сообщение и останавливаем программу.

Обратите внимание на последнюю команду: чтобы получить номер нужной нам строки в таблице побед, мы уменьшаем на 3 введённое значение. Если этого не сделать, мы не сможем понять, на какую строку смотреть при выборе лучшего кубика:

// спрашиваем про кубик соперника
var selected = prompt('Какой кубик выбрал соперник: \n\n 3 — ' + cubeOptions[0] + ' \n\n4 — ' + cubeOptions[1] + '\n\n5 — ' + cubeOptions[2] + '\n\n6 — ' + cubeOptions[3]);
if (selected != 3 && selected != 4 && selected != 5 && selected != 6) {
    // если ввели не то, что нам нужно, — выводим сообщение
    alert('Вы выбрали кубик, которого нет в условии');
    // и останавливаем программу с ошибкой
    throw new Error('Вы выбрали кубик, которого нет в условии');
}
// уменьшаем на 3 введённый результат, чтобы получить номер строки в таблице побед
selected -= 3;

Находим победный кубик и выводим результат

Последнее, что нам осталось сделать, — найти кубик, который покажет наибольшее число побед по сравнению с тем кубиком, который выбрал соперник. Для этого мы смотрим строку с номером кубика соперника и ищем там максимальное значение. Искать будем классическим перебором:

На старте максимальное значение равно нулю.
По очереди смотрим каждый элемент и сравниваем его с максимальным.
Если он больше максимального — делаем его максимальным и запоминаем номер элемента.
Когда цикл закончится, у нас будет номер максимального элемента в массиве. Это и будет наш победный кубик.

В финале выводим рекомендацию, какой кубик выбрать:

// тут мы будем хранить максимальное победное значение
var max = 0;
// перебираем всю строку таблицы
for (let i = 0; i < 4; i++) {
    // если победный результат в нужной строке больше максимального
    if (winResult[selected][i] > max){
        // то делаем это максимальным результатом
        max = winResult[selected][i];
        // и запоминаем номер кубика, который показал наибольший результат
        choose = i;
    }
}

// выводим номер кубика, с которым больше всего шансов выиграть у соперника
alert('Вам нужно выбрать ' + cubeOptions[choose]);

Чтобы найти выигрышный кубик, скопируйте и вставьте готовый код в консоль браузера.

// количество бросков
var rollCount = 100000;

// кубик, который нам нужно выбрать
var choose;

// виртуальные кубики с числами на гранях
var c1 = [3,3,3,3,3,3];
var c2 = [0,0,4,4,4,4];
var c3 = [1,1,1,5,5,5];
var c4 = [2,2,2,2,6,6];

// названия кубиков
var cubeOptions = [];
cubeOptions[0] = 'кубик с тройками';
cubeOptions[1] = 'кубик с нолями и четвёрками';
cubeOptions[2] = 'кубик с единицами и пятёрками';
cubeOptions[3] = 'кубик с двойками и шестёрками';

// создаём двумерный массив для результатов бросков
// сначала сделаем обычный массив из 4 элементов
var result = new Array(4);
// потом переберём в цикле все 4 элемента
for (let i = 0; i < 4; i++) {
    // и каждый превратим тоже в массив, размер которого совпадает с количеством бросков
    result[i] = new Array(rollCount); 
}

// виртуальный бросок кубика
function diceRoll(){
    // на выходе получаем целое число от 0 до 5, которое соответствует выпавшей стороне кубика
    return Math.floor(Math.random() * 6)
}

// перебираем по очереди все 4 кубика
for (let i = 0; i < rollCount; i++) {
    // и виртуально подкидываем их, записывая результат в массив
    result[0][i] = c1[diceRoll()];
    result[1][i] = c2[diceRoll()];
    result[2][i] = c3[diceRoll()];
    result[3][i] = c4[diceRoll()];
}

// считаем количество побед, у кого больше — у соперника или у игрока
// на вход функции подаём два массива — с бросками соперника и со своими бросками
function winCount(player,you){
    // на старте побед пока нет
    var win = 0;
    // перебираем все броски
    for (let i = 0; i < rollCount; i++) {
        // если по результатам попарного броска у нас выпало больше, чем у соперника
        if (player[i] < you[i]){
            // то увеличиваем на единицу количество побед
            win += 1;
        }
    }
    // возвращаем количество побед в этой паре
    return win;
}

// создаём двумерный массив для виртуальной таблицы побед
var winResult = new Array(4);
// таблица будет 4 на 4, пока пустая
for (let i = 0; i < 4; i++) {
    winResult[i] = new Array(4); 
}

// заполняем таблицу побед
for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++){
        // чтобы кубик не соревновался сам с собой, в этом месте ставим ноль
        if (i == j) { winResult[i][j] = 0 }
        else {
            // заносим в таблицу результат побед второго кубика над первым
            winResult[i][j] = winCount(result[i],result[j])
        }
    }
}

// спрашиваем про кубик соперника
var selected = prompt('Какой кубик выбрал соперник: \n\n 3 — ' + cubeOptions[0] + ' \n\n4 — ' + cubeOptions[1] + '\n\n5 — ' + cubeOptions[2] + '\n\n6 — ' + cubeOptions[3]);
if (selected != 3 && selected != 4 && selected != 5 && selected != 6) {
    // если ввели не то, что нам нужно, — выводим сообщение
    alert('Вы выбрали кубик, которого нет в условии');
    // и останавливаем программу с ошибкой
    throw new Error('Вы выбрали кубик, которого нет в условии');
}
// уменьшаем на 3 введённый результат, чтобы получить номер строки в таблице побед
selected -= 3;

// тут мы будем хранить максимальное победное значение
var max = 0;
// перебираем всю строку таблицы
for (let i = 0; i < 4; i++) {
    // если победный результат в нужной строке больше максимального
    if (winResult[selected][i] > max){
        // то делаем это максимальным результатом
        max = winResult[selected][i];
        // и запоминаем номер кубика, который показал наибольший результат
        choose = i;
    }
}

// выводим номер кубика, с которым больше всего шансов выиграть у соперника
alert('Вам нужно выбрать ' + cubeOptions[choose]);

Зачем так сложно

Конкретно этот код можно было бы записать в сто раз проще: «Если человек написал такую-то цифру — дать ему такой-то ответ», это бы всё уложилось в 10 строк кода. Это если смотреть на итоговый код как на продукт. Но дело не в конечном продукте.

Наш код — это симуляция большого числа игр. Ответы, которые даёт алгоритм, основаны не на логическом мышлении, а на реальном испытании данных. А это значит, что теперь мы можем делать симуляции на любых кубиках:

Любые числа на гранях.
Любое число граней (с доработкой в функции diceRoll).
Любое число кубиков.
Игра против двоих или троих соперников (с доработкой алгоритма).

А также можно добавить, например, денежные ставки, и получится симулятор казино. В общем, на базе этого кода можно считать намного более сложные игровые комбинации, чем те заранее заготовленные красивые сочетания, которые были предусмотрены в исходной задаче.

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Обложка:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев