Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/257438 
Erscheinungsjahr: 
2020
Quellenangabe: 
[Journal:] Games [ISSN:] 2073-4336 [Volume:] 11 [Issue:] 2 [Article No.:] 19 [Publisher:] MDPI [Place:] Basel [Year:] 2020 [Pages:] 1-11
Verlag: 
MDPI, Basel
Zusammenfassung: 
Mastermind is famous two-player game. The first player (codemaker) chooses a secret code which the second player (codebreaker) is supposed to crack within a minimum number of code guesses (queries). Therefore, the codemaker's duty is to help the codebreaker by providing a well-defined error measure between the secret code and the guessed code after each query. We consider a variant, called Yes-No AB-Mastermind, where both secret code and queries must be repetition-free and the provided information by the codemaker only indicates if a query contains any correct position at all. For this Mastermind version with n positions and kÏn colors and ℓ:=k+1−n , we prove a lower bound of ∑kj=ℓlog2j and an upper bound of nlog2n+k on the number of queries necessary to break the secret code. For the important case k=n , where both secret code and queries represent permutations, our results imply an exact asymptotic complexity of Θ(nlogn) queries.
Schlagwörter: 
Mastermind
permutation
query complexity
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Erscheint in der Sammlung:

Datei(en):
Datei
Größe
294.28 kB





Publikationen in EconStor sind urheberrechtlich geschützt.