Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Strategy in Guess Who?: Beyond Binary Search
74
0
0.0
(
0
)
Added by
Mihai Nica
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Authors
Mihai Nica
Ask ChatGPT about the research
No Arabic abstract
Guess Who? is a popular two player game where players ask Yes/No questions to search for their opponents secret identity from a pool of possible candidates. This is modeled as a simple stochastic game. Using this model, the optimal strategy is explicitly found. Contrary to popular belief, performing a binary search is emph{not} always optimal. Instead, the optimal strategy for the player who trails is to make certain bold plays in an attempt catch up. This is discovered by first analyzing a continuous version of the game where players play indefinitely and the winner is never decided after finitely many rounds.
rate research
Read More
Game tree search algorithms such as minimax have been used with enormous success in turn-based adversarial games such as Chess or Checkers. However, such algorithms cannot be directly applied to real-time strategy (RTS) games because a number of reasons. For example, minimax assumes a turn-taking game mechanics, not present in RTS games. In this paper we present RTMM, a real-time variant of the standard minimax algorithm, and discuss its applicability in the context of RTS games. We discuss its strengths and weaknesses, and evaluate it in two real-time games.
We study a static game played by a finite number of agents, in which agents are assigned independent and identically distributed random types and each agent minimizes its objective function by choosing from a set of admissible actions that depends on its type. The game is anonymous in the sense that the objective function of each agent depends on the actions of other agents only through the empirical distribution of their type-action pairs. We study the asymptotic behavior of Nash equilibria, as the number of agents tends to infinity, first by deriving laws of large numbers characterizes almost sure limit points of Nash equilibria in terms of so-called Cournot-Nash equilibria of an associated nonatomic game. Our main results are large deviation principles that characterize the probability of rare Nash equilibria and associated conditional limit theorems describing the behavior of equilibria conditioned on a rare event. The results cover situations when neither the finite-player game nor the associated nonatomic game has a unique equilibrium. In addition, we study the asymptotic behavior of the price of anarchy, complementing existing worst-case bounds with new probabilistic bounds in the context of congestion games, which are used to model traffic routing in networks.
We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for the Straight-Jacket Auctions among certain deterministic auctions. Third, we employ computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.
Observations of an optical source coincident with gravitational wave emission detected from a binary neutron star coalescence will improve the confidence of detection, provide host galaxy localisation, and test models for the progenitors of short gamma ray bursts. We employ optical observations of three short gamma ray bursts, 050724, 050709, 051221, to estimate the detection rate of a coordinated optical and gravitational wave search of neutron star mergers. Model R-band optical afterglow light curves of these bursts that include a jet-break are extrapolated for these sources at the sensitivity horizon of an Advanced LIGO/Virgo network. Using optical sensitivity limits of three telescopes, namely TAROT (m=18), Zadko (m=21) and an (8-10) meter class telescope (m=26), we approximate detection rates and cadence times for imaging. We find a median coincident detection rate of 4 yr^{-1} for the three bursts. GRB 050724 like bursts, with wide opening jet angles, offer the most optimistic rate of 13 coincident detections yr^{-1}, and would be detectable by Zadko up to five days after the trigger. Late time imaging to m=26 could detect off-axis afterglows for GRB 051221 like bursts several months after the trigger. For a broad distribution of beaming angles, the optimal strategy for identifying the optical emissions triggered by gravitational wave detectors is rapid response searches with robotic telescopes followed by deeper imaging at later times if an afterglow is not detected within several days of the trigger.
For the problem of prediction with expert advice in the adversarial setting with geometric stopping, we compute the exact leading order expansion for the long time behavior of the value function. Then, we use this expansion to prove that as conjectured in Gravin et al. [12], the comb strategies are indeed asymptotically optimal for the adversary in the case of 4 experts.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
