#! /usr/bin/env python3
#
def high_card_probability ( n ):
#*****************************************************************************80
#
## high_card_probability() determines winning probabilities for the high card game.
#
# Discussion:
#
# The high card game presents the player with a deck of cards, each
# having an unknown value. The player is allowed to go throught the
# deck once, looking at the cards one at a time. At any time, the player
# may decide to take a particular card, winning that amount and stopping
# the game. If the player continues to the end, by default the last card
# indicates the amount won.
#
# An optimal strategy for selecting the highest card is as follows:
# * look at, but do not select, the first k-1 cards
# * stop at the first card, from k to n, that is higher than the
# first k-1 cards.
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 06 July 2022
#
# Author:
#
# John Burkardt
#
# Input:
#
# integer N, the number of cards.
#
# Output:
#
# real P(N). P(K) is the probability that a strategy that skips
# K-1 cards will win, given that the deck has N cards.
#
import numpy as np
p = np.zeros ( n )
for r in range ( 0, n ):
s = 0.0
for i in range ( r + 1, n ):
s = s + 1.0 / i
p[r] = ( 1 + r * s ) / n
return p
def high_card_shuffle ( n ):
#*****************************************************************************80
#
## high_card_shuffle() generates a sequence of numeric "cards" for a game.
#
# Discussion:
#
# In this game, you know that the deck contains N cards. You win by
# choosing the highest card in the deck. You don't know what this card
# is, and you must choose your card by saying "stop" as, one by one,
# the cards of the deck are exposed.
#
# A random guesser would get the high card with probability 1/N.
#
# An intelligent guesser can do much better.
#
# It is the goal of this program so "shuffle" a deck of cards suitable
# for this game. The problem is that we know the highest card in an
# ordinary deck. Let's replace the cards by integers. Then if we know
# in advance the range of the cards (say, they must lie between 1 and
# 1,000), it may be true that we can guess the card that is the maximum.
#
# However, this program produces a sequence of integer card values for
# which no information can be gained from the values. It does this
# by regarding the card values as binary integers between 1 and 2^N - 1.
# We can make a perfectly information-free sequence as follows:
#
# Card 1 sets bit N-1 to 1.
# Card 2 sets bit N-2 to 1, bit N-1 randomly.
# ...
# Card I sets bit N-I to 1, bits N-1 down to N-I+1 randomly.
# ...
# Card N sets bit N-N to 1, bits N-1 down to 1 randomly.
#
# The I-th card has equal probability to fall in any of the I intervals
# defined by the I-1 previous cards. So, knowing the previous cards tells
# you absolutely nothing about where the next card will fall, and each
# card is, at the moment you see it, as good a guess for the maximum as
# the unseen cards.
#
# For example, the command "high_card_shuffle(7)" might yield
#
# 64 96 80 8 4 82 29
# or
# 64 32 16 24 12 58 73
# or
# 64 96 48 8 100 26 93
# or
# 64 96 16 56 76 122 71
#
# in which the highest card is #2, #7, #5, or #6 respectively.
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 06 July 2022
#
# Author:
#
# John Burkardt
#
# Input:
#
# integer N, the number of cards. N probably needs to be less than 32.
#
# Output:
#
# integer SEQUENCE(N), a set of N integer values that can be used
# as the cards in the high card guessing game.
#
from numpy.random import default_rng
import numpy as np
if ( 32 <= n ):
print ( '' )
print ( 'high_card_shuffle(): Fatal error!' )
print ( ' This program can only handle N < 32.' )
raise Exception ( 'high_card_shuffle - Fatal error!' )
sequence = np.zeros ( n )
for i in range ( 0, n ):
c = 2 ** ( n - i - 1 )
k = rng.integers ( low = 0, high = 2, size = i )
for j in range ( 0, i ):
c = c + k[j] * 2 ** ( n - i + j )
sequence[i] = c
return sequence
def high_card_simulation ( deck_size, skip_num, trial_num ):
#*****************************************************************************80
#
## high_card_simulation() simulates a game of choosing the highest card in a deck.
#
# Discussion:
#
# You are given a deck of DECK_SIZE cards.
#
# Your goal is to select the high card. For convenience, we can assume
# the cards are a permutation of the integers from 1 to DECK_SIZE, but in
# fact the user mustn't see such values or else it's obvious which is the
# largest card.
#
# However, your choice is made under the following rules: You may turn over
# one card at a time. When a card is turned over, you may declare that to be
# your choice, or else turn over another card. If you have not chosen a card
# by the end, then your choice is the final card.
#
# If you have no idea what to do, and simply decide in advance to pick
# a card "at random", that is, for example, you decide to pick the 15th card
# before having seen any cards, then your probability of winning
# is 1/DECK_SIZE.
#
# The question is, can you do better than that?
#
# Your strategy is as follows: always look at the first SKIP_NUM cards without
# choosing them. Then choose the very next card you encounter that is larger
# than the cards you skipped.
#
# Using this program, you can easily see that skipping 5 cards is much better
# than picking one at random, skipping 10 is even better, and so on. Of course,
# you can't skip too many cards, and in fact, the results seem to be best for
# somewhere around 30 to 35 cards skipped. For problems like this, the
# optimal value is somewhere around 1 / e, where E is the base of the natural
# logarithm system.
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 06 July 2022
#
# Author:
#
# John Burkardt
#
# Input:
#
# integer DECK_SIZE, the number of cards in the deck.
# 2 <= DECK_SIZE. Default value is 52
#
# integer SKIP_NUM, the number of initial cards you plan to examine
# but will NOT select. If SKIP_NUM is 0, you don't look at any cards first.
# 0 <= SKIP_NUM < DECK_SIZE. Default value is DECK_SIZE/3.
#
# integer TRIAL_NUM, the number of times we will simulate this process.
# Default value is 100.
#
# Output:
#
# real P, the estimated probability that your strategy of skipping
# SKIP_NUM cards and then selecting the next card that is bigger, will
# result in choosing the highest card.
#
import numpy as np
#
# Check values.
#
if ( deck_size < 2 ):
print ( '' )
print ( 'high_card_simulation(): Fatal error!' )
print ( ' DECK_SIZE must be at least 2.' )
print ( ' Your value was ', deck_size )
raise Exception ( 'high_card_simulation(): Fatal error!' )
skip_num = int ( skip_num )
if ( skip_num < 0 ):
skip_num = 0
if ( deck_size <= skip_num ):
print ( '' )
print ( 'high_card_simulation(): Fatal error!' )
print ( ' SKIP_NUM must be less than DECK_SIZE.' )
print ( ' Your DECK_SIZE =', deck_size )
print ( ' Your SKIP_NUM =', skip_num )
raise Exception ( 'high_card_simulation(): Fatal error!' )
if ( trial_num < 1 ):
print ( '' )
print ( 'high_card_simulation(): Fatal error!' )
print ( ' TRIAL_NUM must be at least 1.' )
print ( ' Your value was', trial_num )
raise Exception ( 'high_card_simulation(): Fatal error!' )
correct = 0
for trial in range ( 0, trial_num ):
cards = np.arange ( 0, deck_size )
cards = np.random.permutation ( cards )
if ( 1 <= skip_num ):
skip_max = np.max ( cards[0:skip_num] )
else:
skip_max = - np.Inf
true_max = np.max ( cards )
#
# In case you don't encounter a card larger than SKIP_MAX,
# we'll assume you pick the last card in the deck, even though
# you know it's a loser.
#
choice = cards[deck_size-1]
#
# Turn over the remaining cards in the deck, but stop
# immediately when you find one bigger than SKIP_MAX.
#
for card in range ( skip_num + 1, deck_size ):
if ( skip_max < cards[card] ):
choice = cards[card]
break
#
# Record successful choices.
#
if ( choice == true_max ):
correct = correct + 1
#
# Estimate the probability.
#
p = correct / trial_num
return p
def high_card_simulation_test01 ( ):
#*****************************************************************************80
#
## high_card_simulation_test01() varies the skip number.
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 06 July 2022
#
# Author:
#
# John Burkardt
#
import numpy as np
deck_size = 100
trial_num = 100
print ( '' )
print ( 'high_card_simulation_test01():' )
print ( ' Using', deck_size, 'cards and', trial_num, 'trials,' )
print ( ' estimate the chances of' )
print ( ' picking the high card by skipping a given number of initial cards.' )
print ( '' )
print ( ' Skip Deck Size Chance of Winning' )
print ( '' )
for i in range ( 0, 10 ):
skip_num = 1 + np.floor ( i * deck_size / 10 )
p = high_card_simulation ( deck_size, skip_num, trial_num )
print ( ' %3d %3d %12g' % ( skip_num, deck_size, p ) )
return
def high_card_simulation_test02 ( ):
#*****************************************************************************80
#
## high_card_simulation_test02() plots the results for a deck of 100 cards.
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 06 July 2022
#
# Author:
#
# John Burkardt
#
import matplotlib.pyplot as plt
import numpy as np
deck_size = 100
trial_num = 1000
print ( '' )
print ( 'high_card_simulation_test02():' )
print ( ' Using', deck_size, 'cards and', trial_num, 'trials,' )
print ( ' compute the chances of picking the high card with ' )
print ( ' a skip of 0 through 99.' )
s = np.zeros ( deck_size )
p = np.zeros ( deck_size )
for i in range ( 0, deck_size - 1 ):
s[i] = i
p[i] = high_card_simulation ( deck_size, s[i], trial_num )
plt.clf ( )
plt.plot ( s, p, 'b-', linewidth = 2 )
plt.grid ( True )
plt.title ( 'Estimated chance of winning per given skip number' )
plt.xlabel ( 'Number of cards to skip before choice' )
plt.ylabel ( 'Chance of correct choice.' )
filename = 'high_card_simulation_test02.png'
plt.savefig ( filename )
print ( ' Graphics saved as "' + filename + '"' )
plt.show ( block = False )
plt.close ( )
return
def high_card_simulation_test03 ( ):
#*****************************************************************************80
#
## high_card_simulation_test03() plots the results for a deck of 100 cards.
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 06 July 2022
#
# Author:
#
# John Burkardt
#
import matplotlib.pyplot as plt
import numpy as np
deck_size = 100
print ( '' )
print ( 'high_card_simulation_test03():' )
print ( ' high_card_probability() computes the exact probability of ' )
print ( ' winning a high card game with a deck of', deck_size, 'cards' )
print ( ' assuming we skip the first K cards and select the next card' )
print ( ' that is bigger.' )
s = np.arange ( 0, deck_size )
p = high_card_probability ( deck_size )
print ( '' )
print ( ' K Prob(K)' )
print ( '' )
for i in range ( 0, deck_size ):
print ( ' %3d %8g' % ( s[i], p[i] ) )
plt.clf ( )
plt.plot ( s, p, 'r', linewidth = 2 )
plt.grid ( True )
plt.title ( 'Exact chance of winning per given skip number' )
plt.xlabel ( 'Number of cards to skip before choice' )
plt.ylabel ( 'Chance of correct choice.' )
filename = 'high_card_simulation_test03.png'
plt.savefig ( filename )
print ( ' Graphics saved as "' + filename + '"' )
plt.show ( block = False )
plt.close ( )
return
def high_card_simulation_test ( ):
#*****************************************************************************80
#
## high_card_simulation_test() tests high_card_simulation().
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 06 July 2022
#
# Author:
#
# John Burkardt
#
import platform
print ( '' )
print ( 'high_card_simulation_test():' )
print ( ' Python version: ' + platform.python_version ( ) )
print ( ' Test high_card_simulation().' )
high_card_simulation_test01 ( )
high_card_simulation_test02 ( )
high_card_simulation_test03 ( )
#
# Terminate.
#
print ( '' )
print ( 'high_card_simulation_test()' )
print ( ' Normal end of execution.' )
print ( '' )
return
def timestamp ( ):
#*****************************************************************************80
#
## timestamp() prints the date as a timestamp.
#
# Licensing:
#
# This code is distributed under the MIT license.
#
# Modified:
#
# 21 August 2019
#
# Author:
#
# John Burkardt
#
import time
t = time.time ( )
print ( time.ctime ( t ) )
return
if ( __name__ == '__main__' ):
timestamp ( )
high_card_simulation_test ( )
timestamp ( )