Как играть в игру быки и коровы


Разработка оптимальной стратегии игры «Быки и коровы» на основе теории информации

Когда я поступил в институте, очень популярной была игра «Быки и коровы». Так совпало, что в это же время я прочитал математическую новеллу Альфреда Реньи «Дневник. – Записки студента по теории информации». Благодаря этой статье я познакомился с основами теории информации. И у меня родилась идея, как улучшить свои показатели в «Быках и коровах», опираясь на новые знания [1].

Кратко напомню правила. Играют двое. Каждый задумывает и записывает тайное 4-значное число с неповторяющимися цифрами (первой может быть и ноль). Игрок, который начинает игру по жребию, делает попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику в виде вопроса. Противник говорит в ответ, сколько цифр угадано с совпадением их позиций в тайном числе и сколько угадано без совпадения. Например: задумано тайное число 3219; попытка (вопрос) 2310; результат (ответ): один «бык» (цифра 1 из вопроса входит в тайное число и стоит на своем месте) и две «коровы» (цифры 2 и 3 из вопроса входят в тайное число, но стоят не на своем месте). Ответ сообщается в виде 2-значного числа. В нашем примере ответ – 12 (один «бык», две «коровы»). Игроки делают попытки по очереди. Побеждает тот, кто первым получит на свой вопрос ответ 40.

Скачать заметку в формате Word или pdf, примеры в формате Excel, пример Неоптимальный второй вопрос в формате zip (внутри Excel-файл на 57МВ).

Рекомендую скачивать после прочтения соответствующего места заметки, и только если поймете, что вам хочется изучить детали.

Вот какие идеи теории информации мне показались полезными для улучшения показателей в игре (см. Введение в теорию информации):

  1. Вопрос нужно задавать так, чтобы ответ на него давал максимальное количество информации.
  2. Для этого вопрос нужно формировать так, чтобы вероятности различных ответов были по возможности близкими.
  3. Кроме того, вопрос должен быть таким, чтобы ответ на него не содержал информацию, полученную ранее из предыдущих вопросов.

Для лучшего понимания материала полезно также открыть Excel-файл.

1. Тайное число можно задумать 10*9*8*7 = 5040 способами (на первом месте может стоять любая из 10 цифр, на втором – любая из 9 оставшихся и т.д.). Для того, чтобы сформировать массив допустимых чисел я использовал простые алгоритмы в Excelе (см. листы «Подг1» и «Подг2»). Поскольку вероятность быть задуманным любого из 5040 чисел одинакова, неопределенность (Н) вычисляется по формуле Хартли: Н = log 2N. Перед началом игры неопределенность составляет log25040 = 12,30 бит информации.

2. Понятно, что первый вопрос может быть любым, например, 0123. На него возможны 14 ответов (см. также лист «Вопрос1» Excel-файла):

Ответ Число ответов р H h
00 360 7,1% 8,49 3,81
01 1440 28,6% 10,49 1,81
02 1260 25,0% 10,30 2,00
03 264 5,2% 8,04 4,25
04 9 0,2% 3,17 9,13
10 480 9,5% 8,91 3,39
11 720 14,3% 9,49 2,81
12 216 4,3% 7,75 4,54
13 8 0,2% 3,00 9,30
20 180 3,6% 7,49 4,81
21 72 1,4% 6,17 6,13
22 6 0,1% 2,58 9,71
30 24 0,5% 4,58 7,71
40 1 0,02% 0,00 12,30
5040 100,0% 12,30 2,77

Здесь: р – вероятность ответа, Н – неопределенность, оставшаяся после соответствующего ответа, h – количество информации, полученное, если реализовался тот или иной ответ. Наиболее вероятный ответ – 01, означающий, что из вопроса в тайное число входит лишь одна цифра, причем стоит она не на своем месте. Ответ 01 подразумевает, что задуманным может быть одно из 1440 чисел, то есть неопределенность, оставшаяся после этого ответа, составляет log21440 = 10,49 бит, а информация, полученная при таком ответе 12,30 – 10,49 = 1,81 бит. Ответ 40 дает 12,30 бит информации, а неопределенности после него не остается J Поскольку вероятности ответов различны, количество информации, содержащееся в вопросе определяется по формуле Шеннона: Н(x) = p1 log2(1/p1) + p2log2(1/p2) + … + pNlog2(1/pN). Первый вопрос приносит 2,77 бит информации.

3. При выборе второго вопроса следует руководствоваться тремя идеями сформулированными выше. На практике это означает, что вопрос должен допускать ответ 40.

Правило формирования второго вопроса. Пусть на первый вопрос (0123) мы получили ответ 01. Для второго вопроса возьмем одну цифру из первого вопроса, поставим ее на новое место и добавим три новые цифры. Получим, например, 4561. Если на вопрос1 был получен, например, ответ 11, надо взять две цифры из первого вопроса, одну оставить на своем месте, вторую поставить на новое место, и добавить две новые цифры; например, 0435.

На вопрос2 4561 также возможны 14 ответов (см. лист «Вопрос2»):

Ответ Число ответов р H h
00 54 3,8% 5,75 4,74
01 378 26,3% 8,56 1,93
02 369 25,6% 8,53 1,96
03 91 6,3% 6,51 3,98
04 6 0,4% 2,58 7,91
10 126 8,8% 6,98 3,51
11 222 15,4% 7,79 2,70
12 83 5,8% 6,38 4,12
13 6 0,4% 2,58 7,91
20 57 4,0% 5,83 4,66
21 31 2,2% 4,95 5,54
22 5 0,3% 2,32 8,17
30 11 0,8% 3,46 7,03
40 1 0,07% 0,00 10,49
1440 100,0% 10,49 2,86

Выбранный нами второй вопрос принес 2,86 бита информации. Посмотрим, сколько информации дадут другие вторые вопросы. Для этих целей я создал отдельный файл «Неоптимальный второй вопрос.xlsx» (он «весит» 58МВ, поэтому будьте с ним аккуратнее :)). Второй вопрос может быть одним из 5040 возможных чисел (в том числе и повторение первого вопроса). В итоге этого исследования я получил количество информации, которое дают те или иные вторые вопросы (напомню, что анализ сделан в предположении, что первый вопрос 0123 дал ответ 01). Например, вопрос2 – 0123 дает ноль битов информации, так как на него возможен только один ответ 01, а (для N = 1) log21 = 0. Вопрос2 0132 дает 0,65 бит информации, вопрос2 0148 – 2,53 бита информации. Максимальное количество информации дают 1440 вторых вопросов, сформированных по выше описанному правилу. Результаты исследования я перенес на лист «Разные вопросы2» файла «Быки-коровы.xlsx» и далее буду говорить только об этом файле.

Как я уже сказал, максимальное количество информации – 2,859 – будет получено на вопрос2, подготовленный следующим образом: надо взять одну цифру из первого вопроса, поставить ее на новое место и добавить три новые цифры:

Информация от вопроса2, бит Число таких вопросов
0,000 1
0,650 6
0,811 8
0,918 9
1,899 24
2,104 72
2,258 144
2,268 72
2,365 216
2,372 48
2,530 180
2,624 360
2,664 720
2,756 360
2,766 480
2,767 720
2,774 180
2,859 1440
Итого 5040

Видно, что еще 180 вопросов дают почти столько же информации – 2,774 бита. Такое количество информации будет получено при ответе, например, на вопрос 1045 (см. лист «Вопрос2неопт»). Но этот вопрос не может дать ответа 40! То есть, вопрос подготовлен с нарушением сформулированного правила. Насколько велика разница в информации между 2,859 и 2,774 бита!? На первый взгляд она не выглядит большой. С другой стороны, при самом неблагоприятном ответе на вопрос2 4561 (01) останется 378 вариантов тайного числа, а при самом неблагоприятном ответе на вопрос2 1045 (также 01) – 408 вариантов. На 8% больше! Это и есть цена неоптимального вопроса.

4. При подготовке третьего (и последующих) вопросов я руководствуюсь следующим мнемоническим правилом. Необходимо составить агрегированную таблицу всех возможных тайных чисел, удовлетворяющих ответам на предыдущие вопросы. После этого сформировать вопрос3, используя ту часть этой таблицы, которая содержит больше вариантов (оценку произвожу «на глазок»). Немного запутанно? Давайте рассмотрим два примера.

Пример1. Первые два вопроса и ответа были следующими:

Вопрос1 0123 Ответ1 01
Вопрос2 4561 Ответ2 01

Первый вариант: входит единица, тогда не входят, ни 023, ни 456; то есть входят, не использовавшиеся в первых двух вопросах, цифры – 789. Получаем набор цифр тайного числа 1789 (порядок их расположения любой, удовлетворяющий ответам на первые два вопроса). Вариантов, отвечающих этому набору, 12.

Второй вариант: единица не входит, тогда входит одна цифра из 023, одна – из 456, и две – из 789. Записываю я это так:

Ориентировочное число вариантов набора цифр равняется 3 (одна из 023) * 3 (одна из 456) * 3 (две из 789) = 27. А с учетом мест расположения цифр вариантов существенно более 100. Для вопроса3 берем одну цифру из 023, одну из 456, две из 789. Располагаем цифры так, чтобы не было совпадений мест расположения с вопросом1 и вопросом2. Более того, располагаем цифры, которые ранее уже встречались (4 и 2) на совершенно новых местах, то есть на 2-м или 4-м. Например, вопрос3 7482 лучше, чем 2784. Так как в первом случае 4-ка и 2-ка стоят на местах, которые в вопросе1 и вопрос2 они не занимали. В то же время, в вопросе3 2784 цифра 2 стоит на месте 4-ки из вопроса2 (см. лист «Вопрос3»). Ответ на вопрос3 4782 содержит 2,958 бит информации, а ответ на вопрос 3 2784 – «только» 2,955.

Пример2. Первые два вопроса и ответа были следующими:

Вопрос1 0123 Ответ1 02
Вопрос2 3541 Ответ2 02

Первый вариант: входят 13, тогда не входят, ни 02, ни 45, а из оставшихся цифр входят две:

Количество тайных числе в варианте1 – 48.

Второй вариант: входит одна цифра из 13, тогда входит одна – из 02, одна – из 45, и одна – из 6789:

Ориентировочное количество тайных чисел в варианте2 – более 100.

Третий вариант: не входят 13, тогда входят и 02, и 45: 0245. Количество тайных чисел в варианте3 – 8.

Итак для вопроса3 выбираем число из варианта2, например, 1705.

5. Когда тайных чисел остается мало (от 4 до 10…20), я перехожу на полный перебор всех возможных вариантов.

Играйте с алгоритмом, построенным на основе теории информации, и выигрывайте!

Дополнение от 14 февраля 2015 г.

Нурым Кенжебеков написал программу, позволяющую играть с компьютером. Программа работает под Windows 7, 8, 8.1 с установленным Framework 4.5. Игра мне очень понравилась, но алгоритм явно далек от оптимального. Я сыграл трижды и все три раза выиграл.

Скачать программу в формате архива.


[1] http://slovesnov.narod.ru/articles/bullcow.pdf. Сказать по правде, мне не удалось ее осилить 🙂 Но упоминаний теории информации при беглом просмотре я в ней не нашел…

Игра для программистов — Быки и коровы / Habr

Привет Хабралюди. Я расскажу вам, как на Питоне написать движок и примерный бот игры для программистов. Игры для программистов — это такие игры, в которые играют не люди, а программы.


Мы будем писать вариант игры «Быки и коровы», по-английски которая называется «Bulls and Cows». Правила оригинальной игры между двумя людьми можете прочитать тут.
Правила нашей игры:

  1. Движок задумывает число, оно n значное и цифры в нем не могут повторяться. Движок сообщает программе-игроку число n
  2. Программа-игрок предполагает какое-то число, сообщает его движку
  3. Движок сообщает программе-игроку, сколько цифр из числа программы-игрока есть в задуманном и стоят на своем месте (Быки), и сколько есть в задуманно, но не стоят на своем месте (коровы).
  4. Если число не угаданно, возврат к п.2

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

Движок

Напишем вначале функциональные части:

Copy Source | Copy HTML
  1.  
  2. #!/usr/bin/python
  3. import random
  4.  
  5. class Game(object):
  6.     def __init__(self, number=6):
  7.         if number > 10:
  8.             exit()
  9.         self.number = number
  10.         self.secret = self.make_secret(self.number)
  11.         self.main()
  12.  
  13.     def is_right_secret(self, secret):
  14.         """check all digits are different"""
  15.         dct = {}
  16.         for digit in secret:
  17.             try:
  18.                 if dct[digit]:
  19.                     return False
  20.             except KeyError:
  21.                 dct[digit] = True
  22.         return True
  23.  
  24.     def make_secret(self, number):
  25.         """generate number-counted secret"""
  26.         while True:
  27.             result = ""
  28.             for i in range(number):
  29.                 result += "%d" % random.randint( 0,9)
  30.             if self.is_right_secret(result):
  31.                 return result

Здесь мы задумываем число, которое программы-игроки будут отгадывать. Также мы проверяем, чтобы все цифры в числе были разными. затем мы запускаем Game.main — основной цикл программы.

Также необходимо дописать функцию подсчета быков и коров:

Copy Source | Copy HTML
  1.  
  2. def count_bulls_cows(self, number, secret):
  3.      """count bulls and cows in number/secret"""
  4.      cows, bulls =  0,  0
  5.      dct = {}
  6.      for i in range(len(secret)):
  7.          if secret[i]==number[i]:
  8.              bulls += 1
  9.          else:
  10.              dct[secret[i]] = True
  11.              try:
  12.                  if dct[number[i]]:
  13.                      cows += 1
  14.              except KeyError:
  15.                  pass
  16.      return bulls, cows

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

Copy Source | Copy HTML
  1.  
  2. MESS_NUMBER_DIGITS = "number_digits" #start message
  3. MESS_GUESS = "guess!"
  4. MESS_COWS = "cows:" #If the matching digits on different positions, they are "cows" 
  5. MESS_BULLS = "bulls:" #If the matching digits are on their right positions, they are "bulls" 
  6. MESS_BULLS_COWS_SPLIT = "|" #Splitter between cows and bulls message
  7. MAX_TURN_NUMBER = 1000

Теперь опишем игровой процесс в main(): (привожу с отладочными сообщениями)

Copy Source | Copy HTML
  1. def main(self):
  2.     for player in self.players:
  3.         player.connect()
  4.         player.send("%s %d" % (MESS_NUMBER_DIGITS, self.number))
  5.         print ("%s %d" % (MESS_NUMBER_DIGITS, self.number))
  6.         starttime = time.time()
  7.         while True:
  8.             if player.turns > MAX_TURN_NUMBER:
  9.                 print ">>>> Player '%s' turns timeout" % player.name
  10.                 player.disconnect()
  11.                 break
  12.             answer = player.recieve()
  13.             print ">>>> Answer is %s" % answer
  14.             if len(self.secret)!=len(answer):
  15.                 self.stop_game("wrong number")
  16.             bulls, cows = self.count_bulls_cows(answer, self.secret)
  17.             if bulls==self.number:
  18.                 player.time = time.time() - starttime
  19.                 player.send("%s" % MESS_GUESS)
  20.                 player.disconnect()
  21.                 print ">>>> Player disconected"
  22.                 break
  23.             else:
  24.                 player.turns += 1
  25.                 player.send("%s %d%s%s %d" % (MESS_BULLS, bulls,\
  26.                         MESS_BULLS_COWS_SPLIT, MESS_COWS, cows))
  27.                 print(">>>> %s %d%s%s %d" % (MESS_BULLS, bulls,\
  28.                         MESS_BULLS_COWS_SPLIT, MESS_COWS, cows) )
  29.  
  30.     winner = self.players[ 0]
  31.     for player in self.players:
  32.         if player.turns<winner.turns:
  33.             winner = player
  34.     print ">>>> Winner name: %s" % winner.name

Тут все понятно. По очереди играем с каждым игроком. Вначале отправляем количество цифр в загаданном числе. Засекаем время. Принимаем число-догадку игрока, если не угадал (число быков не равно числу цифр в числе) — отправляем число быков/коров и увеличиваем число ходов, потребовавшеясе игроку на отгадку, если угадал — останавливаем таймер, пишем ему что он выиграл, отключаемся от игрока, переходим к следующему.

В конце выбираем победителя.

Опишем машинерию соединения с процессами программ-игроков в классе Player:

Copy Source | Copy HTML
  1.  
  2. class Player(object):
  3.     def __init__(self, name, progname):
  4.         self.name = name
  5.         self.turns =  0
  6.         self.time = -1
  7.         self.progname = progname
  8.  
  9.     def connect(self):
  10.         self.__proc = subprocess.Popen(self.progname, stdin=subprocess.PIPE,\
  11.                         stdout=subprocess.PIPE)
  12.  
  13.     def send(self, sendstring):
  14.         self.__proc.stdin.write(sendstring+'\n')
  15.  
  16.     def recieve(self)
  17.         return self.__proc.stdout.readline().strip('\n')
  18.  
  19.     def disconnect(self)
  20.         self.__proc.terminate()
  21.  

Немного перепишем Game.__init__, чтобы инициализировать игроков:

Copy Source | Copy HTML
  1. def __init__(self, number, players_progs):
  2.      if number > 10:
  3.          exit()
  4.      self.number = number
  5.      self.secret = self.make_secret(self.number)
  6.  
  7.      self.players = []
  8.  
  9.      for playername in players_progs:
  10.          self.players.append(Player(playername, players_progs[playername]))
  11.  
  12.      self.main()
  13.  
Тупой бот

Теперь надо потестировать получившееся. Для тестов нам нужна программа-игрок, самая простая. Она же потом будет api — классом, от которого настоящие программы-игроки будут наследоваться
Создадим в папке проекта подпапку api, а в нем файл mooapi.py:

Copy Source | Copy HTML
  1.  
  2. #!/usr/bin/python
  3. import random
  4. import sys
  5.  
  6. MESS_NUMBER_DIGITS = "number_digits" #start message
  7. MESS_GUESS = "guess!"
  8. MESS_COWS = "cows:" #If the matching digits on different positions, they are "cows" 
  9. MESS_BULLS = "bulls:" #If the matching digits are on their right positions, they are "bulls" 
  10. MESS_BULLS_COWS_SPLIT = "|" #Splitter between cows and bulls message
  11.  
  12.  
  13.  
  14. class MooPlayer(object):
  15.  
  16.     ##technical functions
  17.     def send(self, st):
  18.         sys.stdout.write("%s\n"%st)
  19.         sys.stdout.flush()
  20.  
  21.     def recieve(self):
  22.         return sys.stdin.readline().strip("\n")
  23.  
  24.  
  25.     def number_split(self, st):
  26.         num = st.split(' ')
  27.         if num[ 0]==MESS_NUMBER_DIGITS:
  28.             return int(num[1])
  29.         else:
  30.             exit()
  31.  
  32.     def answer_split(self, st):
  33.         try:
  34.             bullst, cowst = st.split(MESS_BULLS_COWS_SPLIT)
  35.         except ValueError:
  36.             exit()
  37.         bulls, cows = bullst.split(' '), cowst.split(' ')
  38.         if bulls[ 0]==MESS_BULLS and cows[ 0]==MESS_COWS:
  39.             return bulls[1], cows[1]
  40.         else:
  41.             exit()
  42.  
  43.     def main(self):
  44.         self.number = self.number_split(self.recieve())
  45.  
  46.         while True:
  47.             try:
  48.                 self.oldguess = guess
  49.                 guess = self.guess(cows=cows, bulls=bulls, firstrun=False)
  50.             except NameError:
  51.                 guess = self.guess(firstrun=True)
  52.             self.send(guess)
  53.             answer = self.recieve()
  54.             if answer == MESS_GUESS:
  55.                 exit()
  56.             else:
  57.                 bulls, cows = self.answer_split(answer)
  58.  
  59.  
  60.     ##some functions
  61.     def is_right_secret(self, secret):
  62.         """check all digits are different"""
  63.         dct = {}
  64.         for digit in secret:
  65.             try:
  66.                 if dct[digit]:
  67.                     return False
  68.             except KeyError:
  69.                 dct[digit] = True
  70.         return True
  71.  
  72.     def generate_number(self, number):
  73.         """generate number-counted secret"""
  74.         while True:
  75.             result = ""
  76.             for i in range(number):
  77.                 result += "%d" % random.randint( 0,9)
  78.             if self.is_right_secret(result):
  79.                 return result
  80.  
  81.     ############ Main guess function ###########
  82.     def guess(self, firstrun, bulls= 0, cows= 0):
  83.         """This is main api function. firstrun means that it is first time run,<br/>        bulls/cows is number of bulls and cows from last time.<br/>        also you have:<br/>            self.number  - number of digits<br/>            self.oldguess - old guess try<br/>        """
  84.         return self.generate_number(self.number)
  85.  
  86.  
  87. if __name__ == "__main__":
  88.     mooplayer = MooPlayer()
  89.     mooplayer.main()

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

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

>>number_digits 4
5032
>>bulls: 0|cows: 0
4123
>>bulls: 0|cows: 0
2890
>>bulls: 0|cows: 0
2691
>>guess!

(>>) обозначает ввод с клавиатуры

Запускаем

теперь добавим в конец модуля движка:

Copy Source | Copy HTML
  1.  
  2. if __name__ == "__main__":
  3.     game = Game(2, {'Player1':"api/mooapi.py", 'Player2':"api/mooapi.py", 'HabraMan':"api/mooapi.py" })

Это запустит игру с двухзначными числами, тремя игроками с одинаковыми программами api/mooapi.py. С двухзначными — это чтобы наша тупая программа смогла угадать.

Запустим модуль движка:
>>>> bulls: 0|cows: 1
>>>> Answer is 67
>>>> bulls:1 cows:0
>>>> bulls: 1|cows: 0
>>>> Answer is 87
>>>> bulls:0 cows:0
>>>> bulls: 0|cows: 0
>>>> Answer is 49
>>>> bulls:0 cows:0
>>>> bulls: 0|cows: 0
>>>> Answer is 54
>>>> bulls:0 cows:0
>>>> bulls: 0|cows: 0
>>>> Answer is 82
>>>> bulls:1 cows:0
>>>> bulls: 1|cows: 0
>>>> Answer is 21
>>>> bulls:0 cows:0
>>>> bulls: 0|cows: 0
>>>> Answer is 62
>>>> bulls:2 cows:0
>>>> Player disconected
>>>> Winner name: HabraMan

Работает!
В следующем посте я расскажу, как сделать программу полезной — прикрутить к ней парсинг аргументов коммандной строки и вывод всего добра в xml, в котором хавает ввод наш будущий флеш-проигрыватель на нашем будущем сайте.

Ссылка на полные тексты программ

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

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

Быки и коровы решение

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

И так, первый ход он всегда на удачу. Выбираем любые четыре цифры. К примеру 1234.

Получаем ответ две коровы. Что это нам даёт? Мы нашли две цифры, но не знаем какие они и где должны стоят. Не будем пока их трогать и пытаться выяснить кто есть кто. Это будет напрасной тратой драгоценных ходов. Идём дальше и второй вопрос составляем из других цифр. К примеру, 5678.

Мы получили в ответ один бык и одну корову. Хочу сказать, что мы тут молодцы и удача нам улыбается. Нам удалось выявить, что ноль и девять не состоят в загаданном числе. И теперь мы их можем использовать для определения быков! Таким образом у нас с Вами есть два варианта развития дальнейших событий. Это искать быков из первого или второго вопроса. Я выберу первый, так как в этом варианте нет быков и все цифры не на своих местах. Снова скрестим пальцы на удачу. Выберем две цифры и переставим их местами, думаю взять 3 и 4, и поставить их на первое и второе место. И добьём третий вопрос нашими пустышками 0 и 9. Получаем такой вопрос 3490.

Ответ просто волшебный! Два быка. Мы снова угадали 3 и 4 - это и есть быки. Значит единичка и двойка вне игры. Осталось найти вторую пару цифр. Начинаем перебирать цифры с нашего второго вопроса. Возьмём 5 и 7, но поставим их на другие места. Это важный момент - места нужно менять, у нас ведь во втором ответе имеется один бык и есть шанс 25%, что мы этого быка снова поставим на место в третьем вопросе и у нас будет неоднозначность, какая из второй пары цифр точно есть бык. И таким образом получаем четвёртый вопрос - 3457.

Пришёл ответ - два быка и одна корова. Два быка это наши угаданные с третьей попытки 3 и 4. Корова - это одна их цифр 5 или 7. Но мы можем точно определить быка, у нас ведь во втором ответе есть один бык. Пятёрка чтобы быть быком должна стоять на первом месте, а это место у нас занято тройкой. Значит остаётся цифра семь и должна она стоять на третьем месте!

Продолжаем рассуждать дальше. У нас осталось две цифры - шесть и восемь. Что нам о них известно? А то, что во втором ответе одна из них является коровой, то есть стоит не на своём месте. Шестёрка на втором, восьмёрка на четвёртом. У нас свободно осталось только четвёртое место! И если это 8, то у нас возникнет противоречие, так как тогда во втором ответе она должна была быть быком, потому что стоит на четвёртом месте! В ходе таких рассуждений мы абсолютно точно выявили, что цифра шесть это наш четвёртый бык и стоит она на четвёртой позиции. Проверяем: 3476.

И Чудеса! Четыре быка. Поздравляю мы победили!

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

Пожелания, критику или Ваши предложения жду на форуме или на почту.

6 | Pandia.ru

6 полезных и развивающих игр для школьников


Быки и коровы

Фрагмент картины Лоуэлла Эрреро Корова прыгает через луну

Эта игра особенно хороша для того, чтобы развить у ребёнка фонематический слух. Играть в неё просто. Один игрок загадывает слово, для начала из трёх букв. Допустим, я загадала слово чай. Здорово загадывать слова с редкими буквами: тын, кий и хна. Дети предлагают в ответ другие трёхбуквенные слова: сыр, лес, мак. В слове мак с загаданным словом совпадает буква А, и она стоит на том же месте в слове: у нас есть один бык. Через несколько выстрелов в молоко кто-то предлагает слово йод. О, уже теплее! Но буква Й (и тут вы противным голосом Мальвины спрашиваете: Все помнят, что буква Й означает мягкий звонкий согласный?) стоит на другом месте в загаданном слове, поэтому я говорю: Одна корова. И так повторять нужно до полного попадания.

Когда вы с детьми натренируетесь так, что будете угадывать любое трёхбуквенное слово меньше, чем за 10 ходов, можно переходить на слова из четырёх букв. И вот там вас могут поджидать открытия, связанные с правописанием глухих/звонких согласных, йотированных гласных (я загадала слово маяк, Дуся не может его отгадать, сдаётся, а когда слышит ответ, возмущённо вопит: Не честно! Он же м-о-й-а-к!), безударных гласных. Слово овца вполне может быть воссоздано как афца, и хорошо бы, чтобы вы могли объяснить, как и что проверяется. Кстати, в быков и коров отлично играется в дороге.

Снежный ком

Фрагмент картины Корнелиуса Киммеля Снежный ком

Для тренировки словарного запаса можно поиграть в Снежный ком в обеих модификациях: подбираем определения к существительному и существительные к определению. Вы называете любое слово, обозначающее предмет, а дети должны назвать как можно больше определений. Песок — он какой? Мокрый, сухой, сыпучий, морской, речной, жёлтый, зыбучий, плотный, жёсткий Очень хорошо, если вы можете привязать этот набор к каким-то важным и приятным для вас событиям, например: Какой был песок на пляже, когда мы ездили на море? А в деревне? А у нас на площадке? Выигрывает тот, кто назовёт последнее слово. И в обратную сторону. Что может быть мокрым? А скользким? Я использую эту игру для разминки на уроке, иногда в качестве поощрения: если выполним все задания быстро, успеем поиграть.

Буриме

Фрагмент картины Николая Николаевича Ге Пушкин в Михайловском

Более сложная игра, но смешная до колик. Зафиксированы случаи, когда игроки просто писались от смеха. В неё хорошо играть впятером-вчетвером, если участников меньше, то не получается складного текста. Правила простые: раздаются длинные и узкие полоски бумаги (половинка тетрадного листа вдоль), затем задаётся некий стихотворный размер, например, пошла муха на базар и купила самовар. Каждый игрок пишет первую строчку и заворачивает один раз листочек, сверху пишет последнее слово предложения. Если это Я люблю гонять гусей, выписываем слово гусей. После этого бумажку нужно передать соседу справа и взять новую у соседа слева. Игрок справа пишет следующую строчку с рифмой на слово гусей: Прискакал тут Елисей. Строчкой ниже пишет свою строку с новой рифмой: Мы гуляли в казино — и пишет сверху казино. Передаёт дальше. Веселье начинается, когда все свитки заканчиваются, разворачиваются и получившаяся белиберда зачитывается. Между прочим, у этого развлечения весьма древние и почтенные корни: в Буриме любили играть поэты Серебряного века, да, кажется, и во времена Пушкина забава пользовалась популярностью. Игра не только весёлая, но и очень полезная: Буриме тренирует чувство ритма, словарный запас, чувство юмора, правописание.

Придумай 10 слов на одну букву и Антонимы

Фрагмент картины Жюля Анри Жан Жоффруа

Для совсем маленьких детей хорошо искать сочетания букв на уличных вывесках или в надписях на упаковках, а потом давать задания из игр Придумай 10 слов на одну букву и Антонимы в формате давай говорить наоборотные слова? Ты говори всё наоборот, а я буду угадывать, что ты имел в виду. Можно даже устроить день одной буквы — это тоже очень веселит народ, когда абсолютно все свои послания надо выражать словами на одну букву. Главное, не выбирайте гласные, а вот буквы Т или П очень хорошо подойдут. Заодно сами выясните, как устроен русский язык.

Тайный язык шпионов

Фрагмент картины Магритт Рене Шпион

Моя любимая с детства игра — Тайный язык шпионов. Берете любой слог, допустим, цэ (потому что в русском языке такого сочетания не встречается) и начинаете вставлять его МЕЖДУ слогами слов: цэ-ма-цэ-ма, цэ-пой-цэ-ди цэ-сю-цэ-да!. Отлично тренируются сразу несколько навыков: разбивать слова на слоги, выделять значимую часть в беглой речи, концентрация внимания. Если детей в семье несколько, старшим может понравиться говорить на непонятном младшим языке, или чтобы бабушка не понимала.

Быки и коровы (игра для детей)

Развивающие игры

Быки и коровы – математическая игра, где главная цель угадать число противника. Кто первый отгадал – тот победитель. Вычисление цифры противника проходит по определённым правилам.

Что развивает?

Игра познакомит с миром больших чисел, научит логически думать, вычислять.

Для игры понадобятся:

  1. два игрока
  2. лист бумаги
  3. ручка

Как играть (правила)

Шаг 1.

Игроки задумывают 4-значное число, но так, чтобы все цифры в нём были разные. Записывают на своих листочках, или просто запоминают.

Шаг 2.

Ходы делятся по очереди. Каждый ход, игрок называет число, четырехзначное, в котором все цифры разные. В случае, если цифры совпадают, хотя бы одно, то игрок говорит корова.

Шаг 3.

При повторном ходе, когда произносится число, и они совпадают и стоят на одной и том же месте, то такая ситуация называется бык. Например, загаданное число 3185, игрок называет 3596, игрок говорит – корова, второй ход игрока, он называет 3274, игрок говорит бык. Выигрывает тот, кто отгадал число первым.

Важно помнить!

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

Оцените игру

Играли в эту иргу? Оцените ее пожалуйста.

Сохранить для себя, поделиться с друзьями:

Мамы играют Загрузите фото, как вы играли с ребенком

Загрузить фото

Похожие игры

0

Для игры понадобится:

Кукла, мягкие игрушки, игрушечная посуда, игрушечный столик и стулья ( если есть)

Рассади гостей

5

Для игры понадобится:

ничего

Сочиняем сказку

Больше интересных игр

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

Здорово, когда и родители включены в этот процесс, помогают малышам и детям постарше в том, как научиться правильно играть. И, конечно, совместные часы активностей – это отличное времяпрепровождение для всей семьи, когда разные поколения всё лучше «узнают» особенности друг друга, учатся понимать и слушать.

Из всех вариаций игр – подвижных, уличных, для маленьких и больших компаний, для взрослых и малышей – выбирайте ту, которая по душе. Например, игра "Быки и коровы " станет отличным поводом провести время с пользой. Узнайте, что нужно для игры "Быки и коровы ", каковы правила игры и какие качества она развивает.

Играйте вместе, учите детей и узнайте правила новых полезный активностей!

games:nastolnye_igry:igry_na_bumage:byki_i_korovy

Быки и коровы — логическая игра для двоих игроков. Для игры достаточно иметь бумагу, ручку и уметь считать.

Синонимы

Также игра может называться «цифры» или «цвета». В настольном варианте известна как «Mastermind».

Правила игры

Играют двое. Каждый задумывает и записывает тайное 4-значное число с неповторяющимися цифрами. Игрок, который начинает игру по жребию, делает попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (сколько «коров») и сколько угадано вплоть до позиции в тайном числе (сколько «быков»).

Например: Задумано тайное число «3219». Попытка: «2310». Результат: две «коровы» (две цифры: «2» и «3» — угаданы на неверных позициях) и один «бык» (одна цифра «1» угадана вплоть до позиции). Игроки делают попытки угадать по очереди. Побеждает тот, кто угадает число первым.

Вариации игры

В игре «мастермайнд» (англ. Mastermind, возможный перевод: «гениальный отгадчик») загадывается последовательность из 4 цветных фишек, причём цвета могут повторяться. В усложнённом варианте может использоваться последовательность из 5, 6 или большего количества фишек. Существует вариант игры со словами. То есть игрок загадывает слово, обычно из 5 букв (в именительном падеже единственном числе по правилам игры «Балда»), и задача противника — угадать его, используя в качестве попыток такие же корректные слова из словаря русского языка. Известное слово из 4 букв для подлавливания новичков — «эльф»: в нём три буквы из четырёх крайне редкие, и неопытный игрок может сделать много ходов, прежде чем добьётся хотя бы «коровы».

Алгоритм

В общем случае количество вариантов для k-значного числа в N-ричной системе счисления без повторений, будет равно числу размещений: Akn = n!/(n-k)!. В случае варианта с повторениями количество вариантов будет равно n^k. Большинство известных алгоритмов суть вариации алгоритма полного перебора с определённой эвристикой. В связи с тем, что количество вариантов не столь велико и схема прямого перебора элементарно реализуется, компьютер играет в «быки и коровы» намного сильнее человека. Чем больше знаков в числе, тем больше разница в силе игры человека и компьютера.

Настольный вариант игры Mastermind для 4 мест и 6 цветов

Как показал Дональд Кнут, для игры Mastermind (64 вариантов) при предложенной им стратегии нужно не более 5 попыток, чтобы отгадать любую комбинацию, и в среднем 4,34 попыток для отгадывания. В классическом случае игры с четырьмя не повторяющимися цифрами для отгадывания любого номера требуется не более семи ходов. Средняя минимальная длина игры составляет 26274/5040=5.2131 попытки.

Реализации

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

  • классическая (на бумаге), четыре неповторяющиеся цифры.

  • обычная, 4 места для фишек 6 цветов с повторениями.

  • продвинутая, 5 мест для фишек 8 цветов.

Ссылки

Быки и коровы - это... Что такое Быки и коровы?

Быки и коровы — логическая игра для двоих игроков. Для игры достаточно иметь бумагу, ручку и уметь считать. Также игра может называться «цифры» или «цвета».

Правила игры

Играют двое. Каждый задумывает и записывает тайное 4-значное число с неповторяющимися цифрами[1]. Игрок, который начинает игру по жребию, делает попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе и сколько угадано вплоть до позиции в тайном числе. Например:

Задумано тайное число «3219».

Попытка номер: «2310».

Результат: две «коровы» (две цифры: "2" и "3" — угаданы на неверных позициях) и один «бык» (одна цифра "1" угадана вплоть до позиции).

Игроки делают попытки угадать по очереди. Побеждает тот, кто угадает число первым.

Вариации игры

В игре «мастермайнд» (англ. Mastermind, возможный перевод: «гениальный отгадчик») загадывается последовательность из 4 цветных фишек, причём цвета могут повторяться.

В усложнённом варианте может использоваться последовательность из 5, 6 или большего количества фишек[2][3][неавторитетный источник? 661 день].

Существует вариант[неавторитетный источник? 661 день] игры со словами. То есть игрок загадывает слово, обычно из 5 букв (в именительном падеже единственном числе по правилам игры «балда»), и задача противника — угадать его, используя в качестве попыток такие же корректные слова из словаря русского языка.

Алгоритм

В общем случае количество вариантов для k-значного числа в N-ричной системе счисления без повторений, будет равно числу размещений: .

В случае варианта с повторениями количество вариантов будет равно .

Большинство известных алгоритмов суть вариации алгоритма полного перебора с определённой эвристикой[4]. В связи с тем, что количество вариантов не столь велико и схема прямого перебора элементарно реализуется, компьютер играет в «быки и коровы» намного сильнее человека. Чем больше знаков в числе, тем больше разница в силе игры человека и компьютера.

Настольный вариант игры Mastermind для 4 мест и 6 цветов

Как показал Дональд Кнут, для игры Mastermind (64 вариантов) при предложенной им стратегии нужно не более 5 попыток, чтобы отгадать любую комбинацию, и в среднем 4,34 попыток для отгадывания[5].

В классическом случае игры с четырьмя не повторяющимися цифрами для отгадывания любого номера требуется не более семи ходов. Средняя минимальная длина игры составляет 26274/5040=5.2131 попытки[6].

Реализации

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

Настольные игры Mastermind популярны во всём мире. Наиболее распространены вариации:

  • классическая, четыре не повторяющиеся цифры.
  • обычная, 4 места для фишек 6 цветов с повторениями.
  • продвинутая, 5 мест для фишек 8 цветов[источник не указан 224 дня].

Ссылки

  • Кандидат технических наук Е. Гик. Быки и коровы. «Наука и жизнь», № 2, 1978, с. 150—151; № 8, 1978, с. 142—143.
  • Чарльз Уэзерелл. Этюды по программированию, Великий комбинатор. М.: 1982, с. 140.

Примечания


Смотрите также