Optimal Strategies for Static Black-Peg AB Game With Two and Three Pegs

2025-04-29 0 0 356.71KB 36 页 10玖币

侵权投诉

arXiv:2210.04652v1 [math.CO] 10 Oct 2022

Optimal Strategies for Static Black-Peg AB Game With

Two and Three Pegs

Gerold Jägera, Frank Drewesb

aDepartment of Mathematics and Mathematical Statistics, University of Umeå, SE-901-87

Umeå, Sweden

bDepartment of Computer Science, University of Umeå, SE-901-87 Umeå, Sweden

Abstract

The AB Game is a game similar to the popular game Mastermind. We study

a version of this game called Static Black-Peg AB Game. It is played by two

players, the codemaker and the codebreaker. The codemaker creates a so-called

secret by placing a color from a set of ccolors on each of p≤cpegs, subject

to the condition that every color is used at most once. The codebreaker tries

to determine the secret by asking questions, where all questions are given at

once and each question is a possible secret. As an answer the codemaker reveals

the number of correctly placed colors for each of the questions. After that, the

codebreaker only has one more try to determine the secret and thus to win the

game.

For given pand c, our goal is to ﬁnd the smallest number kof questions the

codebreaker needs to win, regardless of the secret, and the corresponding list

of questions, called a (k+ 1)-strategy. We present a (⌈4c/3⌉ − 1)-strategy for

p= 2 for all c≥2, and a ⌊(3c−1)/2⌋-strategy for p= 3 for all c≥4and show

the optimality of both strategies, i.e., we prove that no (k+ 1)-strategy for a

smaller kexists.

Keywords: game theory, Mastermind, AB Game, optimal strategy

1. Introduction

The AB Game (also known as “bulls and cows game”) is a game similar to

the popular game Mastermind. Whereas the ﬁrst one dates back more than a

century, the latter was invented by Meirowitz in 1970. Mastermind has since

turned out to have interesting applications in ﬁelds such as cryptography [7],

bioinformatics [8] and privacy protection [1]. In both games a codemaker and

⋆A preliminary version of a part of this paper appeared in the proceedings of the 11th

International Conference on Combinatorial Optimization and Applications, COCOA 2017,

Ed.: Gao, X., Du, H. Han, M., LNCS 10628, pp. 409-424.

Email addresses: gerold.jaeger@math.umu.se (Gerold Jäger), frank.drewes@cs.umu.se

(Frank Drewes)

acodebreaker play against each other. The codemaker chooses a secret code

by placing colors from a set of cavailable colors on ppegs. In the original

version of the AB Game and Mastermind, respectively, p= 4,c= 6 and p= 4,

c= 10, respectively, are ﬁxed, but to make the computational and mathematical

properties of the game interesting, at least one of these parameters must be made

variable. The goal of the codebreaker is to discover the secret code by making

a sequence of guesses until the secret has been found. Each guess is a possible

secret. The corresponding answers of the codemaker consist of black and white

pegs, a black one for each peg of the question which is correct in both position

and color, and a white one for each peg which is correct in color but not in

position. The goal of the codebreaker is to minimize the number of questions

needed to ﬁnd the secret, i.e., to receive pblack pegs as the last answer. We

call games of this kind codebreaking games.

Mastermind can be turned into a decision problem, Mastermind Satisﬁabil-

ity, as follows: given a list of questions and corresponding answers, are these

answers compatible with at least one possible secret? Interestingly, in [23] this

problem was shown to be N P-complete. For further results on (non-static)

Mastermind see for example [3, 16, 20].

The diﬀerence between Mastermind and the AB Game is that a possible se-

cret or question of the latter may contain repeated colors whereas the AB Game

requires the secret as well as each question to consist of pdistinct colors. Thus,

the distinction between the two games mirrors the well-known distinction made

in combinatorics between an ordered choice of pitems from a set of celements

either with or without replacement.

Both Mastermind and the AB Game also have a black-peg variant, where

the answers of the codebreaker contain only black pegs (i.e., in addition to how

many pegs are correct in both position and color, no further information about

correct colors placed on the wrong pegs is provided).

While strategies for the Black-Peg AB Game were previously studied in [4,

17, 18], we continue our study of optimal strategies for the static black-peg

variant of codebreaking games which was started in [10, 11, 13, 14, 15]. The

static black-peg variant diﬀers from the standard version described as follows.

The codebreaker is required to present all questions except the last one (which

reveals the secret) right at the beginning of the game. Thus, the game is static,

meaning that the codebreaker cannot adapt later questions to previous answers.

In [3] it was shown that the original and the static version of Mastermind

need O(nlog log n)questions for the most prominent case n=c=p. For the

Static Black-Peg AB Game, for this case n=p=c, a lower bound of Ω(nlog n)

and an upper bound of O(n1.525 )were presented in [11], and this upper bond

has recently been improved to O(nlog n)[19].

A(k+ 1)-strategy is a sequence of kquestions such that the answers to

these questions uniquely determine the secret (i.e., the codebreaker can win the

game with the (k+ 1)-th question). We are interested in optimal strategies –

(k+ 1)-strategies where k+ 1 is as small as possible. Let us denote this optimal

k+ 1 (depending on pand c) by s(p, c). Erdös and Rényi [5] and Söderberg and

Shapiro [22] showed independently that s(p, c)∈ O(p/log p)for c= 2, a result

that was later generalized to c≤p1−ǫfor ǫ > 0by Chvátal [2]. Goddard [12]

developed a (⌈2c/3⌉+ 1)-strategy for two pegs and c-strategies for three and

four pegs. For suﬃciently large c, these strategies are optimal.

In [13], we presented an optimal ⌈(4c−1)/3⌉-strategy for Static Black-Peg

Mastermind in the case of p= 2 pegs and an arbitrary number c≥1of colors,

and in [15] an optimal (⌊3c/2⌋+ 1)-strategy for Static Black-Peg Mastermind

in the case of p= 3 pegs and an arbitrary number c≥2of colors. We now

continue this line of research by considering the corresponding cases of the Static

Black-Peg AB Game with p= 2 and p= 3, respectively. We start with an

investigation of the simpler p= 2 case and an arbitrary number cof colors

(where by deﬁnition of the AB Game, c≥2must hold) resulting in an optimal

(⌈4c/3⌉ − 1)-strategy. This strategy improves an earlier optimal strategy that

was presented in [10] without explicit proof of feasibility and optimality. While

our new strategy obviously has the same number of questions as the earlier one,

the improvement lies in its structural simplicity.

Our main result of this work is an optimal ⌊(3c−1)/2⌋-strategy for the

Static Black-Peg AB Game with p= 3 and an arbitrary number c≥4of colors.

The strategies for both cases for the Static Black-Peg AB Game with p= 2

and p= 3 have a similar structure. This structure can also be applied to and

simplify our earlier strategies for Static Black-Peg Mastermind with p= 2 and

p= 3 [13, 15]. Our expectation is that extending and comparing the strategies

for Static Black-Peg Mastermind of [13, 15] and of the AB Game in this work will

eventually make it possible to develop generic optimal strategies for arbitrary p

for both of these codebreaking games.

Interestingly, there is also a graph-theoretic interpretation of strategies for

Static Black-Peg Mastermind to the so-called metric dimension. For an undi-

rected graph G, the metric dimension of Gis deﬁned as the minimum number of

vertices in a subset Sof Gsuch that all other vertices are uniquely determined

by their distances to the vertices in S, see for example [6, 21, 24] for results

on special graph classes. Furthermore, the decision variant of this problem is

N P-complete [9]

Concretely, Static Black-Peg Mastermind with ppegs and ccolors needing

exactly kquestions is equivalent to the metric dimension of the graph Zp

cbeing

k(see [15] for more details). Thus, the results of [13, 15] show that the metric

dimension of Zn×Znis ⌈(4c−1)/3⌉ − 1and that of Zn×Zn×Znis ⌊3c/2⌋. An

open question is whether the results of the present paper can also be connected

to the metric dimension of other types of graphs. In any case, our new way

to assemble optimal strategies by iterating color-shifted copies of a ﬁxed block

can similarly be used to compose simpler optimal strategies for Static Black-Peg

Mastermind than those in [13, 15]. In turn, this results in simpliﬁed proofs of the

fact that the metric dimensions of Zn×Znand Zn×Zn×Znare ⌈(4c−1)/3⌉−1

and ⌊3c/2⌋, respectively.

This work is set up as follows. After giving some preliminaries in Section 2,

we present an optimal (⌈4c/3⌉−1)-strategy for p= 2 in Section 3 and an optimal

⌊(3c−1)/2⌋-strategy for p= 3 in Section 4. Finally, we conclude and suggest

possible future work in Section 5.

2. Preliminaries

Let p≥1denote the number of pegs and c≥pthe number of colors.

W.l.o.g., throughout the remainder of this paper, let the pegs be numbered by

1,2...,p, and the colors by 1,2,...,c. We write the questions and secrets in

the form Q= (q1|q2|... |qp). The possible answers are written as 0B, 1B, 2B,

...,pB.

For k∈N, a (k+ 1)-strategy for Static Black-Peg AB Game consists of k

questions which the codebreaker has to ask altogether at the beginning of the

game. These are the so-called main questions. Such a strategy is feasible if

every secret Sis uniquely determined by the kanswers. Having received these

answers, the codebreaker can ask the ﬁnal question Sto win the game.

We use the letter kto denote the number of main questions, excluding the

ﬁnal question. Since we will only be concerned with the main questions, in

the following we will generally omit the term “main”, referring to the main

questions simply as questions. A (k+ 1)-strategy is called optimal if there is

no feasible k-strategy. Clearly, all questions of an optimal strategy must be

distinct. Therefore, we shall in the following only consider strategies in which

all questions are distinct, without explicitly mentioning this fact.

Remark 1. Determining an optimal strategy for the Static Black-Peg AB Game

is trivial in the case p= 1 because the questions (1),(2),...,(c−1) reveal the

secret and, obviously, no set consisting of fewer than c−1questions does. Thus,

in the case p= 1 this strategy is an optimal strategy for all c(and so is any

other strategy consisting of c−1questions). In other words, there is an optimal

c-strategy for p= 1 and every c≥1.

We need the following deﬁnition.

Deﬁnition 1. Let Q= (q1|q2|... |qp)and Q′= (q′

1|q′

2|... |q′

p)be questions.

(a) Qand Q′are called neighboring, if qi=q′

ifor some i∈ {1,2,...,p}. We

say that they overlap in peg iand call peg ian overlapping peg (of Qand

Q′).

(b) Qand Q′are are double neighboring if they overlap in at least two distinct

pegs.

jfor all i, j ∈ {1,2,...,p}. More generally,

we say that Qand Q′are disjoint in pegs i1, i2,...,ikif {qi1, qi2,...,qik}∩

{q′

i1, q′

i2. . . , q′

ik}=∅.

(d) For a1, a2,...,ap∈N,Qis a (a1, a2,...,ap)-question1of a given strat-

egy if the i-th color of Qoccurs exactly aitimes on the i-th peg of the

1Note the diﬀerent notation in comparison to the question itself, where we separate the

numbers by the symbol “ |”.

Peg 1 2

Q11 2

(a) c= 2,k= 1.

Peg 1 2

Q11 2

Q23 1

(b) c= 3,k= 2.

Peg 1 2

Q11 3

Q23 1

Q32 3

Q43 2

Table 1: Feasible and optimal (⌈4c/3⌉ − 1)-strategies for p= 2 and 2≤c≤4.

questions of the strategy, for i= 1,2,...,p. Sometimes, for one or more

i∈ {1,2, . . . , p}, we do not want to specify ai, i.e., it is not relevant how

often the i-th color occurs on the i-th peg. Then “ai” is replaced by the

symbol “⋆”. Finally, “ai” can be replaced by “≥ai” to express that qioccurs

at least aitimes on the i-th peg.

In the remainder of the paper, we investigate the cases p= 2,3. For both

cases, the feasible strategy starts with so-called base questions for a small num-

ber of colors and then repeats a copy of a ﬁxed block of questions, shifting the

colors in each copy appropriately. This structure makes the proof of feasibility

relatively easy. However, for the proof of optimality all possible feasible strate-

gies have to be considered, without making speciﬁc assumptions regarding their

structure, and it has to be excluded that they may require fewer questions.

3. Two Pegs

In this section let p= 2.

3.1. A (⌈4c/3⌉ − 1)-Strategy

We introduce a (⌈4c/3⌉ − 1)-strategy for each c≥2which we will later show

to be feasible and optimal. We start with presenting such a strategy explicitly

for c= 2,3,4in Table 1. These three strategies have been found by brute-force

computer search.

As mentioned, we create (⌈4c/3⌉ − 1)-strategies for all c≥2by starting

with a block of so-called base questions and then repeatedly adding copies of a

ﬁxed block of questions, shifting the colors in each copy appropriately. As for

the base questions, we start with one of the three strategies of Table 1. The

iterative step is based on the strategy of Table 1c, which we repeat a suitable

number of times (with shifted colors).

Concretely, let c≥p= 2 and c= 3s+t, where s∈N0,t∈ {2,3,4}are

uniquely determined. For t= 2 we start with the k= 1 question of the strategy

of Table 1a, for t= 3 with the k= 2 questions of the strategy of Table 1b and

for t= 4 with the k= 4 questions of the strategy of Table 1c. As mentioned,

we call this ﬁrst group of questions the base questions.

In all three cases the base questions are followed stimes by the 4questions

of Table 1c. For l= 1,2,...,s, the number t+ 3 (l−1) is added to the colors

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.04652v1[math.CO]10Oct2022OptimalStrategiesforStaticBlack-PegABGameWithTwoandThreePegsGeroldJägera,FrankDrewesbaDepartmentofMathematicsandMathematicalStatistics,UniversityofUmeå,SE-901-87Umeå,SwedenbDepartmentofComputerScience,UniversityofUmeå,SE-901-87Umeå,SwedenAbstractTheABGameisagamesi...

展开>> 收起<<

Optimal Strategies for Static Black-Peg AB Game With Two and Three Pegs.pdf

共36页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Optimal Strategies for Static Black-Peg AB Game With Two and Three Pegs

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: