ISSN:
1572-9273
Schlagwort(e):
Primary 90D42
;
Secondary 68R99, 68Q25
;
Combinatorial games
;
computational complexity
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
Abstract This paper studies a two-person constant sum perfect information game, the End Play Game, arising from an abstraction of end play in bridge. This game was described by Emanuel Lasker who called it whistette. The game uses a deck of cards consisting of a single totally ordered suit of 2n cards. The deck is divided into two hands A and B of n cards each, held by players Left and Right, and one player is designated as having the lead. The player on lead chooses one of his cards, and the other player after seeing this card selects one of his own to play. The player with the higher card wins a ‘trick’ and obtains the lead. The cards in the trick are removed from each hand, and play then continues until all cards are exhausted. Each player strives to maximize his trick total, and the value of the game to each player is the number of tricks he takes. The strategy of this game seems to be quite complicated, despite its simple appearance. This paper studies partial orderings on hands. One partial order recognizes regularities in the value function that persist when extra cards are added to hands. A pair of hands (A * , B * ) dominates a pair of hands (A, B) for Left, if for any set of extra cards (C 1, C 2) added to the deck such that A ∪ B (which equals A * ∪ B * ) is a block of consecutive cards in the expanded deck A ∪ B ∪ {C 1 , C 2} the value of (A ∪ C 1, B ∪ C 2) to Left always is at least as much as the value to Left of (A * ∪ C 1, B * ∪ C 2) both when Left has the lead in both games and when Right has the lead in both games. The main result is that ({4, 1}, {3, 2}) dominates ({3, 2}, {4, 1}). Note that with just four cards the hands {4, 1} and {3, 2} are of identical value — they both take one trick independent of the lead or how the hands are played. The dominance result shows that {4, 1} is preferable to {3, 2} when other cards are present. We show that the dominance relation gives a partial order that is not a total order on hands of 3 or more cards. We also study the total point count ordering, which gives a rough estimate for the value of a hand. We derive upper and lower bounds for the value of a hand with given point count.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF00143897
Permalink
