БлогNot. Задача о "русской рулетке"

Задача о "русской рулетке"

Актуальная и своевременная задачка.

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

Можно выделить несколько основных стратегий загрузки пуль в патронники изначально пустого барабана.

1. Крутануть барабан после загрузки первой пули и повторно крутануть после первого выстрела.

2. Крутануть барабан только после загрузки первой пули.

3. Крутануть барабан только после первого выстрела.

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

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

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

Какая из стратегий обеспечивает наибольшие шансы на успех?

Выделив действия "загрузить", "повернуть" (на случайное количество ячеек от 1 до 6) и "выстрелить", процедуру нетрудно смоделировать программно. Код запускался в консоли актуальной сборки Visual Studio 2019.

#include <iostream>
#include <iomanip>
#include <sstream>
#include <array>
#include <random>

class RussianRoulette {
private:
 std::array<bool, 6> cylinder;
 std::mt19937 gen;
 std::uniform_int_distribution<> distrib;

 int nextInt() { 
  return distrib(gen); 
 }

 void rightShift() { 
  std::rotate(cylinder.begin(), cylinder.begin() + 1, cylinder.end()); 
 }

 void unload() { 
  std::fill(cylinder.begin(), cylinder.end(), false); 
 }

 void load() {
  while (cylinder[0]) rightShift();
  cylinder[0] = true;
  rightShift();
 }

 void spin() {
  int lim = nextInt();
  for (int i = 1; i < lim; i++) rightShift();
 }

 bool fire() {
  auto shot = cylinder[0];
  rightShift();
  return shot;
 }

public:
 RussianRoulette() {
  std::random_device rd;
  gen = std::mt19937(rd());
  distrib = std::uniform_int_distribution<>(1, 6);
  unload();
 }

 int selectAction(const std::string& s) {
  unload();
  for (auto c : s) {
   switch (c) {
    case 'L':
     load();
    break;
    case 'S':
     spin();
    break;
    case 'F':
     if (fire()) return 1;
    break;
   }
  }
  return 0;
 }
};

std::string makeLog(const std::string& s) {
 std::stringstream sstream;
 bool first = true;
 auto append = [&sstream, &first](const std::string s) {
  if (first) first = false;
  else sstream << ", ";
  sstream << s;
 };
 for (auto c : s) {
  switch (c) {
  case 'L':
   append("load");
   break;
  case 'S':
   append("spin");
   break;
  case 'F':
   append("fire");
   break;
  }
 }
 return sstream.str();
}

void testStrategy(const std::string& src) {
 const int tests = 1000000; //по миллиону тестов на стратегию
 int sum = 0;
 RussianRoulette r;
 for (int t = 0; t < tests; t++) sum += r.selectAction(src);
 double pc = 100.0 * sum / tests;
 std::cout << std::left << std::setw(40) << makeLog(src) << 
  " make " << pc << "% success." << std::endl;
}

int main() {
 testStrategy("LSLSFSF");
 testStrategy("LSLSFF");
 testStrategy("LLSFSF");
 testStrategy("LLSFF");
 return 0;
}

Лог результатов показывает, что наиболее успешной оказывается вторая стратегия, наименее успешной - четвёртая.

load, spin, load, spin, fire, spin, fire make 55.5034% success.
load, spin, load, spin, fire, fire       make 58.2711% success.
load, load, spin, fire, spin, fire       make 55.5883% success.
load, load, spin, fire, fire             make 49.9708% success.

P.S. на небольшой технический вопрос:

Зачем процедуру загрузки пули формализовать проверкой первого патронника? Ведь обе пули ещё в руке? Или всё таки подстава?

В коде мы начинаем всегда с пустого патронника, т.к. для каждого теста вызываем конструктор класса RussianRoulette, а он вызывает метод unload. Формальная процедура "загрузки пули" описана в общем виде, в том числе, для случаев, когда загружается N пуль.

12.02.2022, 12:11 [746 просмотров]


теги: c++ игра random

К этой статье пока нет комментариев, Ваш будет первым