# A Game Theoretic Analysis
of the Three-Gambler Ruin Game

Ath. Kehagias, G. Gkyzis, A. Karakoulakis, A. Kyprianidis

###### Abstract

We study the following game. Three players start with initial capitals of
$s_{1},s_{2},s_{3}$ dollars; in each round player $P_{m}$ is selected with
probability $\frac{1}{3}$; then _he_ selects player $P_{n}$ and they play a
game in which $P_{m}$ wins from (resp. loses to) $P_{n}$ one dollar with
probability $p_{mn}$ (resp. $p_{nm}=1-p_{mn}$). When a player loses all his
capital he drops out; the game continues until a single player wins by
collecting everybody’s money.

This is a “strategic” version of the classical Gambler’s Ruin game. It seems
reasonable that a player may improve his winning probability by judicious
selection of which opponent to engage in each round. We formulate the
situation as a _stochastic game_ and prove that it has at least one Nash
equilibrium in deterministic stationary strategies.

##  1 Introduction

In this paper we study a version of the three-gambler ruin problem in which,
whenever a gambler is “activated”, he _chooses_ his opponent. More
specifically, we study our version is played by the following rules.

  1. 1.

The game is played in discrete time steps (rounds).

  2. 2.

Three players start at the $0$-th round with initial capitals, of $s_{1}$,
$s_{2}$ and $s_{3}$ dollars.

  3. 3.

In each round, one player is chosen with probability $\frac{1}{3}$ and then
_he_ chooses another player against whom he will play.

  4. 4.

Suppose that the $m$-th player plays against the $n$-th one; with probability
$p_{mn}$ (resp. $p_{nm}=1-p_{mn\text{ }}$) he wins from (resp. loses to) the
$n$-th player one dollar.

  5. 5.

The game continues until a single player wins (i.e. accumulates the total
$s_{1}+s_{2}+s_{3}$ dollars); if this never happens, the game continues ad
infinitum.

The above game is a “strategic” (in the _game-theoretic_ sense) version of the
“classical” Gambler’s Ruin (GR). Intuitively, it appears reasonable that a
player may improve his winning probability by judicious opponent selection in
each round. As far as we know, this game theoretic approach to GR has not been
explored previously.

The “classic” Gambler’s Ruin involves two gamblers, is one of the earliest-
studied probability problems (for a historical review see [6, 27, 30]) and
remains one of the most popular introductory examples in the theory of Markov
Chains. For an overview of the basic results see [8].

An obvious generalization of GR is to have three or more gamblers. An early
attempt in this direction is [21] but the first (as far as we know) major
advance appeared in [26] and involved “ _symmetric play_ ”, i.e., in each
round all players have equal probability of winning. Symmetric play was
further studied in [7, 24, 25] and numerous other publications [1, 2, 3, 4, 5,
12, 28, 29]. The case of “ _asymmetric play_ ”, i.e., when players’ winning
probabilities are not necessarily equal, has also been studied, first in [22,
23] and more recently in [13, 14, 15]. Finally versions played on graphs have
also been studied, for example in [19].

In all of the above works, no player _strategy_ is involved. In other words,
the players cannot influence who participates in a given round of the
game.111A notable exception appears in [24], where it is stated that “none of
the preceding quantities [winning probability, expected game duration etc.]
depend on the rule for choosing the players in each stage”. Here we have a
case in which strategies are implicitly considered, but they turn out to be
irrelevant. This is the case because the author studies _symmetric play_ ; as
we will see, things are different for asymmetric play.. Hence the evolution of
the game is governed by purely probabilistic laws.

As already mentioned, in this paper we take a different approach. In Section 2
we provide a rigorous formulation as a stochastic game. In Section 3 we
provide an introductory analysis of the simple case in which each player
starts with initial capital of one dollar. In Section 4 we study the general
case (i.e., with arbitrary initial capitals) and prove that the game has at
least one Nash equilibrium (NE) in deterministic stationary strategies. In
Section 5 we discuss the computation of the NE and provide several numerical
experiments. In Section 6 we summarize our results and propose some future
research directions.

It is worth emphasizing that our results can be generalized for the case of
more than three players; we limit ourselves to the three-player case mainly
for simplicity of presentation.

##  2 The Game

We denote our game by $\Gamma_{3}\left(\mathbf{p},K\right)$. It involves three
players (gamblers) $P_{1},P_{2},P_{3}$ and has parameters
$\mathbf{p}=\left(p_{1},p_{2},p_{3}\right)$ and $K$, which satisfy:

$\forall n\in\left\\{1,2,3\right\\}:p_{n}\in\left(0,1\right)\text{ and
}K\in\left\\{3,4,,...\right\\}.$

$\Gamma_{3}\left(\mathbf{p},K\right)$ is played as follows:

  1. 1.

At times $t\in\left\\{0,1,2,..\right\\}$ and for $n\in\left\\{1,2,3\right\\}$,
$P_{n}$’s _capital_ is $s_{n}\left(t\right)$.

  2. 2.

At $t=0$, the capitals satisfy $\ \sum_{n=1}^{3}s_{n}\left(0\right)=K$.

  3. 3.

At $t\in\left\\{1,2,...\right\\}$ a player $P_{n}$ is selected equiprobably
from the set $\left\\{n:s_{n}\left(t\right)>0\right\\}$.

  4. 4.

$P_{n}$ selects another player $P_{m}$ such that $s_{m}\left(t\right)>0$.

  5. 5.

With probability $p_{nm}$ (resp. $p_{mn}$) $P_{n}$ receives one unit from
(resp. pays one unit to)$\ P_{m}$, where

$p_{12}=p_{1},\text{\quad}p_{21}=1-p_{1},\quad
p_{23}=p_{2},\text{\quad}p_{32}=1-p_{2},\quad
p_{31}=p_{3},\text{\quad}p_{13}=1-p_{3}.$

Hence the players’ capitals change as follows:

    1. (a)

if $P_{n}$ wins then $s_{n}\left(t\right)=s_{n}\left(t-1\right)+1$ and
$s_{m}\left(t\right)=s_{m}\left(t-1\right)-1$;

    2. (b)

if $P_{n}$ loses then $s_{n}\left(t\right)=s_{n}\left(t-1\right)-1$ and
$s_{m}\left(t\right)=s_{m}\left(t-1\right)+1$;

    3. (c)

for $k\in\left\\{1,2,3\right\\}\backslash\left\\{n,m\right\\}$ we have
$s_{k}\left(t\right)=s_{k}\left(t-1\right)$.

Obviously, at all $t$ we have $\sum_{n=1}^{3}s_{n}\left(t\right)=K$.

  6. 6.

If at some time $t^{\prime}$ one player is left with zero capital, the game
continues between the two remaining players.

  7. 7.

The game continues until at some time $t^{\prime\prime}$ there exists a single
player $P_{m}$ with
$s_{m}\left(t^{\prime\prime}\right)=\sum_{n=1}^{3}s_{n}\left(0\right)$, in
which case this player is the winner. If we such a player does not exist for
any turn, the game continues ad infinitum.

The _game state_ at time $t$ is
$\mathbf{s}\left(t\right)=\left(s_{1}\left(t\right)s_{2}\left(t\right)s_{3}\left(t\right)\right)$.
The _state set_ is

$S=\left\\{\left(s_{1},s_{2},s_{3}\right):\forall n:s_{n}\geq 0\text{ and
}\sum_{n=1}^{3}s_{n}=K\text{ }\right\\}.$

Note that each $\left(s_{1},s_{2},s_{3}\right)$ can be rewritten as
$\left(s_{1},s_{2},K-s_{1}-s_{2}\right)$. For $s_{1}=i$, we have $K-i+1$
possible states of the form $\left(i,j,K-i-j\right)$ with
$j\in\left\\{0,1,...,K-i\right\\}$; since $i$ can take any value in
$\left\\{0,1,...,K\right\\}$, the total number of states is

$N_{K}=\left|S\right|=\frac{\left(K+1\right)\left(K+2\right)}{2}.$

We define the following state sets:

$S_{1}=\left\\{\left(K,0,0\right)\right\\},\quad
S_{2}=\left\\{\left(0,K,0\right)\right\\},\quad
S_{3}=\left\\{\left(0,0,K\right)\right\\},\quad
S_{i}=\left\\{\left(s_{1},s_{2},s_{3}\right):\forall n:s_{n}>0\right\\}.$

We will call the states $s\in S_{\tau}=S_{1}\cup S_{2}\cup S_{3}$ _terminal_ ,
the states $\mathbf{s}\in S_{i}$ _interior_ and the states $s\in
S_{b}=S\backslash S_{i}$ _boundary_. It is easily checked that
$\left|S_{i}\right|=\frac{\left(K-1\right)\left(K-2\right)}{2}$ and
$\left|S_{b}\right|=3K$. It will be convenient to number the states so that:
the first state is $(K,0,0)$, the second is $(0,K,0)$ and the third is
$(0,0,K)$; the remaining states can be numbered arbitrarily.

The _game history_ at time $t$ is
$\mathbf{h}\left(t\right)=\mathbf{s}\left(0\right)\mathbf{s}\left(1\right)...\mathbf{s}\left(t\right)$.
The set of all _admissible_ histories is denoted by $H$. _A terminal history_
is an
$\mathbf{h}\left(t\right)=\mathbf{s}\left(0\right)\mathbf{s}\left(1\right)...\mathbf{s}\left(t\right)$
such that $\mathbf{s}\left(t\right)\in S_{\tau}$.__

For $n\in\left\\{1,2,3\right\\}$, $P_{n}$’s _payoff_ is defined for every
terminal history
$\mathbf{h=s}\left(0\right)\mathbf{s}\left(1\right)...\mathbf{s}\left(t\right)$
by

$\mathsf{Q}_{n}\left(\mathbf{h}\right)=\left\\{\begin{array}[c]{ll}1&\text{iff
}\mathbf{s}_{n}\left(t\right)=K\\\ 0&\text{else;}\end{array}\right.$

payoff of nonterminal histories is zero.

A _strategy_ for $P_{n}$ is a function
$\sigma_{n}:H\rightarrow\Delta_{3}\cup\left\\{\left(0,0,0\right)\right\\}$,
where

$\Delta_{3}=\left\\{\left(x_{n1},x_{n2},x_{n3}\right)\text{ with }x_{nm}\geq
0\text{ for }m\neq n\text{, }x_{nn}=0\text{,
}\sum_{m=1}^{3}x_{nm}=1\right\\}.$

The interpretation is that

$\sigma_{n}\left(\mathbf{h}\right)=\left(x_{n1},x_{n2},x_{n3}\right)\Leftrightarrow\left(\forall
m,n:\Pr\left(P_{n}\text{ selects }P_{m}\text{ at
}t\text{$|$}\mathbf{h}\right)=x_{nm}\right).$

We will only consider _admissible_ strategies222For example, we exclude
strategies which assign positive probability to selecting a player with zero
capital, to a player selecting himself etc.. A strategy profile is a triple
$\sigma=\left(\sigma_{1},\sigma_{2},\sigma_{3}\right)$. A strategy
$\sigma_{n}$ is called _deterministic_ iff

$\forall\mathbf{h}=\mathbf{s}\left(0\right)\mathbf{s}\left(1\right)...\mathbf{s}\left(t\right):\sigma_{n}\left(\mathbf{h}\right)=\left(x_{1}\left(\mathbf{h}\right),x_{2}\left(\mathbf{h}\right),x_{3}\left(\mathbf{h}\right)\right)\text{
has a single nonzero element.}$

A strategy $\sigma_{n}$ is called _stationary_ iff, for every $\mathbf{h}$,
$\sigma_{n}\left(\mathbf{h}\right)$ depends only on the last state, i.e., iff

$\forall\mathbf{h}=\mathbf{s}_{0}\mathbf{s}_{1}...\mathbf{s}_{t}:\sigma_{n}\left(\mathbf{h}\right)=\sigma_{n}\left(\mathbf{s}_{t}\right);$

We will use the following shorter notation the $x_{mn}$’s:

$x_{1}=x_{12}\text{ (and }1-x_{1}=x_{13}\text{),\quad}x_{2}=x_{23}\text{ (and
}1-x_{2}=x_{21}\text{),\quad}x_{3}=x_{31}\text{ (and }1-x_{3}=x_{32}\text{),}$

and we will denote a stationary strategy profile by
$\mathbf{x}=\left(x_{1},x_{2},x_{3}\right)$.

An initial state $\mathbf{s}\left(0\right)$ and a strategy profile
$\mathbf{\sigma}=\left(\sigma_{1},\sigma_{2},\sigma_{3}\right)$ define a
probability measure on $H$. Hence the _expected payoff_ to $P_{n}$__ is well
defined by

$Q_{n}\left(\mathbf{s}\left(0\right),\mathbf{\sigma}\right)=\mathbb{E}_{\mathbf{s}\left(0\right),\mathbf{\sigma}}\left(\mathsf{Q}_{n}\left(\mathbf{h}\right)\right).$

It is easily seen that
$Q_{n}\left(\mathbf{s}\left(0\right),\mathbf{\sigma}\right)$ is $P_{n}$’s
probability of winning when the starting state is $\mathbf{s}\left(0\right)$
and the players use the strategy profile $\mathbf{\sigma}$.

##  3 The case $K=3$

As a preliminary step in our analysis, let us consider the game when total
capital is $K=3$ (this is obviously the first nontrivial case) and, for
$n\in\left\\{1,2,3\right\\}$, $P_{n}$ uses the _stationary_ strategy
$\mathbf{x}_{n}=\left(x_{n}\left(\mathbf{s}\right)\right)_{\mathbf{s}\in S}$ .
Suppressing the dependence on
$\mathbf{x=}\left(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}\right)$, we
denote $P_{n}$’s payoff, when the game starts at state $\mathbf{s}$, by

$V_{n}\left(s\right)=Q_{n}\left(s,\mathbf{x}\right).$

Let us compute
$\mathbf{V}_{1}\left(\mathbf{s}\right)=\left(V_{1}\left(\mathbf{s}\right)\right)_{\mathbf{s}\in
S}$. First, we have

$V_{1}\left(3,0,0\right)=1,\quad
V_{1}\left(0,3,0\right)=V_{1}\left(0,0,3\right)=V_{1}\left(0,1,2\right)=V_{1}\left(0,2,1\right)=0.$

Also, when two players are left in the game, the only admissible strategy for
each one is to select the other. For instance, in the state
$\left(1,2,0\right)$, we must have

$x_{1}\left(1,2,0\right)=x_{12}\left(1,2,0\right)=1,\quad
x_{2}\left(1,2,0\right)=x_{23}\left(1,2,0\right)=0.$

We have the following transition probabilites:

$\displaystyle\Pr\left(\left(2,1,0\right)\rightarrow\left(3,0,0\right)\right)$
$\displaystyle=p_{1},\quad\Pr\left(\left(2,1,0\right)\rightarrow\left(1,2,0\right)\right)=1-p_{1},$
$\displaystyle\Pr\left(\left(1,2,0\right)\rightarrow\left(2,1,0\right)\right)$
$\displaystyle=p_{1},\quad\Pr\left(\left(1,2,0\right)\rightarrow\left(0,3,0\right)\right)=1-p_{1}.$

Consequently

$\displaystyle V_{1}\left(2,1,0\right)$
$\displaystyle=p_{1}V_{1}\left(3,0,0\right)+\left(1-p_{1}\right)V_{1}\left(1,2,0\right),$
$\displaystyle V_{1}\left(1,2,0\right)$
$\displaystyle=p_{1}V_{1}\left(2,1,0\right)+\left(1-p_{1}\right)V_{1}\left(0,3,0\right),$

which becomes

$\displaystyle V_{1}\left(2,1,0\right)$
$\displaystyle=p_{1}+\left(1-p_{1}\right)V_{1}\left(1,2,0\right),$
$\displaystyle V_{1}\left(1,2,0\right)$
$\displaystyle=p_{1}V_{1}\left(2,1,0\right).$

Solving the above system we get

$V_{1}\left(2,1,0\right)=\frac{p_{1}}{1-p_{1}+p_{1}^{2}},\quad
V_{1}\left(1,2,0\right)=\frac{p_{1}^{2}}{1-p_{1}+p_{1}^{2}}.$

Similarly, we have

$\displaystyle V_{1}\left(2,0,1\right)$
$\displaystyle=\left(1-p_{3}\right)+p_{3}V_{1}\left(1,0,2\right)$
$\displaystyle V_{1}\left(1,0,2\right)$
$\displaystyle=\left(1-p_{3}\right)V_{1}\left(2,0,1\right)$

and we get

$V_{1}\left(2,0,1\right)=\frac{1-p_{3}}{1-p_{3}+p_{3}^{2}},\quad
V_{1}\left(1,0,2\right)=\frac{1-2p_{3}+p_{3}^{2}}{1-p_{3}+p_{3}^{2}}.$

Finally, simplifying $x_{n}\left(1,1,1\right)$ to $x_{n}$ (for
$n\in\left\\{1,2,3\right\\}$) we have

$\displaystyle V_{1}\left(1,1,1\right)=$ $\displaystyle\hskip
14.22636pt\frac{1}{3}\left(x_{1}\left(p_{1}V_{1}\left(2,0,1\right)+\left(1-p_{1}\right)V_{1}\left(0,2,1\right)\right)+\left(1-x_{1}\right)\left(p_{3}V_{1}\left(0,1,2\right)+\left(1-p_{3}\right)V_{1}\left(2,1,0\right)\right)\right)$
$\displaystyle+\frac{1}{3}\left(x_{2}\left(p_{2}V_{1}\left(1,2,0\right)+\left(1-p_{2}\right)V_{1}\left(1,0,2\right)\right)+\left(1-x_{2}\right)\left(p_{1}V_{1}\left(2,0,1\right)+\left(1-p_{1}\right)V_{1}\left(0,2,1\right)\right)\right)$
$\displaystyle+\frac{1}{3}\left(x_{3}\left(p_{3}V_{1}\left(0,1,2\right)+\left(1-p_{3}\right)V_{1}\left(2,1,0\right)\right)+\left(1-x_{3}\right)\left(p_{2}V_{1}\left(1,2,0\right)+\left(1-p_{2}\right)V_{1}\left(1,0,2\right)\right)\right).$

For example, $\frac{1}{3}x_{1}p_{1}V_{1}\left(2,0,1\right)$ is the probability
of:

$P_{1}$ being selected, $P_{1}$ selecting $P_{2}$ and $P_{1}$ beating $P_{2}$.

Substituting the known right hand values, after a considerable amount of
algebra we get

$\displaystyle V_{1}\left(1,1,1\right)$
$\displaystyle={\frac{\left(1-\mathit{p}_{\mathit{3}}\right)\left(\mathit{x}_{\mathit{1}}+1-\mathit{x}_{\mathit{2}}\right)\mathit{p}_{\mathit{1}}}{3\,\left({\mathit{p}}_{{\mathit{3}}}^{2}-\,{\mathit{p}}_{{\mathit{3}}}+1\right)}}+{\frac{\mathit{p}_{\mathit{1}}\,\left(\mathit{x}_{\mathit{3}}+1-\mathit{x}_{\mathit{1}}\right)\left(1-\mathit{p}_{\mathit{3}}\right)}{3\left(\,{\mathit{p}}_{{\mathit{1}}}^{2}-\,\mathit{p}_{\mathit{1}}+1\right)}}$
$\displaystyle+{\frac{\left(1-\mathit{p}_{\mathit{3}}\right)^{2}\left(\mathit{x}_{\mathit{2}}+1-\mathit{x}_{\mathit{3}}\right)\left(1-\mathit{p}_{\mathit{2}}\right)}{3\left(\,{\mathit{p}}_{{\mathit{3}}}^{2}-\,\mathit{p}_{\mathit{3}}+1\right)}}+{\frac{{\mathit{p}}_{{\mathit{1}}}^{2}\left(\mathit{x}_{\mathit{2}}+1-\mathit{x}_{\mathit{3}}\right)\mathit{p}_{\mathit{2}}}{3\,\left({\mathit{p}}_{{\mathit{1}}}^{2}-\,\mathit{p}_{\mathit{1}}+1\right)}.}$

This can also be written as

$V_{1}\left(1,1,1\right)=\frac{p_{1}(1-p_{3})(p_{1}+p_{3}-1)(p_{1}-p_{3})x_{1}+\Pi_{1}\left(x_{2},x_{3}\right)}{3\left(1-p_{3}+p_{3}^{2}\right)\left(1-p_{1}+p_{1}^{2}\right)}$
(1)

where $\Pi_{1}\left(x_{2},x_{3}\right)$ is a first degree polynomial in
$x_{2}$ and $x_{3}$. Hence we have completed the computation of
$\mathbf{V}_{1}=\left(V_{1}\left(\mathbf{s}\right)\right)_{\mathbf{s}\in S}$.

From (1) we can easily compute $P_{1}$’s _optimal_ strategy. Since he wants to
maximize his payoff by choice of $x_{1}=x_{1}\left(1,1,1\right)$, he will use
the following strategy:

$\widehat{x}_{1}=\left\\{\begin{array}[c]{cc}1\text{ iff:}&\text{either
(}p_{1}+p_{3}-1>0\text{ and }p_{1}-p_{3}>0\text{) or (}p_{1}+p_{3}-1<0\text{
and }p_{1}-p_{3}<0\text{)}\\\ 0\text{ iff:}&\text{either
(}p_{1}+p_{3}-1>0\text{ and }p_{1}-p_{3}<0\text{) or (}p_{1}+p_{3}-1<0\text{
and }p_{1}-p_{3}>0\text{)}\end{array}\right.$ (2)

For $n\in\left\\{2,3\right\\}$, a similar avalysis yields $P_{n}$’s payoff
$\mathbf{V}_{n}$ (as a function of strategy profile
$\mathbf{x=}\left(x_{1},x_{2},x_{3}\right)$) and his optimal strategy
$\widehat{x}_{n}$. The expressions for $\widehat{x}_{2}\left(1,1,1\right)$ and
$\widehat{x}_{3}\left(1,1,1\right)$ are analogous to (2). It is easily checked
that $\left(\widehat{x}_{1},\widehat{x}_{2},\widehat{x}_{3}\right)$ is the
unique Nash equilibrium of $\Gamma_{3}\left(\mathbf{p},3\right)$.

##  4 The General Case

Let us now study the general case, i.e., when $K\in\left\\{3,4,...\right\\}$.

###  4.1 Payoff Equations

For a given stationary strategy profile $\mathbf{x}$, for any
$\mathbf{s}=\left(s_{1},s_{2},s_{3}\right)\in S$ and any
$n\in\left\\{1,2,3\right\\}$, let
$V_{n}\left(s_{1},s_{2},s_{3}\right)=Q_{n}\left(s_{1},s_{2},s_{3},\mathbf{x}\right)$
and $\mathbf{V}_{n}=\left(V_{n}\left(\mathbf{s}\right)\right)_{\mathbf{s}\in
S}$. We will now write the _payoff system_ , i.e., the system of equations
satisfied by
$\mathbf{V}_{n}=\left(V_{n}\left(\mathbf{s}\right)\right)_{\mathbf{s}\in S}$.

To this end we start by recognizing that, for a given stationary strategy
profile $\mathbf{x}$, the process
$\left(\mathbf{s}\left(t\right)\right)_{t=0}^{\infty}$ is a Markov chain. Let
us define for each $\mathbf{s}=\left(s_{1},s_{2},s_{3}\right)\in S$ the
_neighborhood_ $\mathbf{N}\left(s_{1},s_{2},s_{3}\right)$ of $\mathbf{s}$ to
be the set of states reachable in one time step from $\mathbf{s}$. For
example, when $\mathbf{s}\in S_{i}$, we have

$\mathbf{N}\left(s_{1},s_{2},s_{3}\right)=\left\\{\left(s_{1}+1,s_{2}-1,s_{3}\right),\left(s_{1}-1,s_{2}+1,s_{3}\right),...,\left(s_{1},s_{2}-1,s_{3}+1\right)\right\\}.$

For every $\mathbf{s}\in S$ and
$\mathbf{s}^{\prime}\in\mathbf{N}\left(\mathbf{s}\right)$ we define the
transition probabilities

$\pi_{\mathbf{s}^{\prime},\mathbf{s}}=\Pr\left(\mathbf{s}\left(t+1\right)=\mathbf{s|s}\left(t\right)=\mathbf{s}^{\prime}\right).$

Then $\mathbf{V}_{1}$ satisfies the following equations.

  1. 1.

For boundary states we have:

$V_{1}\left(K,0,0\right)=1;$ (3)

for all $s_{2}\in\left(0,1,...,K\right)$:

$V_{1}\left(0,s_{2},K-s_{2}\right)=0;$ (4)

and for all $s_{1}\in\left(1,...,K-1\right)$:

$\displaystyle V_{1}\left(s_{1},K-s_{1},0\right)$
$\displaystyle=\sum_{\mathbf{s}^{\prime}\in\mathbf{N}\left(s_{1},K-s_{1},0\right)}\pi_{\left(s_{1},K-s_{1},0\right),\mathbf{s}^{\prime}}V_{1}\left(\mathbf{s}^{\prime}\right),$
$\displaystyle V_{1}\left(s_{1},0,K-s_{1}\right)$
$\displaystyle=\sum_{\mathbf{s}^{\prime}\in\mathbf{N}\left(s_{1},0,K-s_{1}\right)}\pi_{\left(s_{1},0,K-s_{1}\right),\mathbf{s}^{\prime}}V_{1}\left(\mathbf{s}^{\prime}\right),$

which becomes

$\displaystyle V_{1}\left(s_{1},K-s_{1},0\right)$
$\displaystyle=p_{1}V_{1}\left(s_{1}+1,K-s_{1}-1,0\right)+\left(1-p_{1}\right)V_{1}\left(s_{1}-1,K-s_{1}+1,0\right)$
(5) $\displaystyle V_{1}\left(s_{1},0,K-s_{1}\right)$
$\displaystyle=\left(1-p_{3}\right)V_{1}\left(s_{1}+1,0,K-s_{1}-1\right)+p_{1}V_{1}\left(s_{1}-1,0,K-s_{1}+1\right).$
(6)

  2. 2.

For all interior states $\left(s_{1},s_{2},s_{3}\right)$ $\in S_{i}\ $we have

$V_{1}\left(s_{1},s_{2},s_{3}\right)=\sum_{\mathbf{s}^{\prime}\in\mathbf{N}\left(s_{1},s_{2},s_{3}\right)}\pi_{\left(s_{1},s_{2},s_{3}\right),\mathbf{s}^{\prime}}V_{1}\left(\mathbf{s}^{\prime}\right)$

which can be written as either

$\displaystyle V_{1}\left(s_{1},s_{2},s_{3}\right)$
$\displaystyle=\left(\frac{x_{1}\left(s_{1},s_{2},s_{3}\right)+\left(1-x_{2}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\right)p_{1}V_{1}\left(s_{1}+1,s_{2}-1,s_{3}\right)$
$\displaystyle+\left(\frac{x_{1}\left(s_{1},s_{2},s_{3}\right)+\left(1-x_{2}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\right)\left(1-p_{1}\right)V_{1}\left(s_{1}-1,s_{2}+1,s_{3}\right)$
$\displaystyle+\left(\frac{x_{2}\left(s_{1},s_{2},s_{3}\right)+\left(1-x_{3}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\right)p_{2}V_{1}\left(s_{1},s_{2}+1,s_{3}-1\right)$
$\displaystyle+\left(\frac{x_{2}\left(s_{1},s_{2},s_{3}\right)+\left(1-x_{3}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\right)\left(1-p_{2}\right)V_{1}\left(s_{1},s_{2}-1,s_{3}+1\right)$
$\displaystyle+\left(\frac{x_{3}\left(s_{1},s_{2},s_{3}\right)+\left(1-x_{1}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\right)p_{3}V_{1}\left(s_{1}-1,s_{2},s_{3}+1\right)$
$\displaystyle+\left(\frac{x_{3}\left(s_{1},s_{2},s_{3}\right)+\left(1-x_{1}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\right)\left(1-p_{3}\right)V_{1}\left(s_{1}+1,s_{2},s_{3}-1\right),$
(7)

or as

$\displaystyle V_{1}\left(s_{1},s_{2},s_{3}\right)$
$\displaystyle=\frac{x_{1}\left(s_{1},s_{2},s_{3}\right)}{3}\left(p_{1}V_{1}\left(s_{1}+1,s_{2}-1,s_{3}\right)+\left(1-p_{1}\right)V_{1}\left(s_{1}-1,s_{2}+1,s_{3}\right)\right)$
$\displaystyle+\frac{\left(1-x_{1}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\left(\left(1-p_{3}\right)V_{1}\left(s_{1}+1,s_{2},s_{3}-1\right)+p_{3}V_{1}\left(s_{1}-1,s_{2},s_{3}+1\right)\right)$
$\displaystyle+\frac{x_{2}\left(s_{1},s_{2},s_{3}\right)}{3}\left(p_{2}V_{1}\left(s_{1},s_{2}+1,s_{3}-1\right)+\left(1-p_{2}\right)V_{1}\left(s_{1},s_{2}-1,s_{3}+1\right)\right)$
$\displaystyle+\frac{\left(1-x_{2}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\left(\left(1-p_{1}\right)V_{1}\left(s_{1}-1,s_{2}+1,s_{3}\right)+p_{1}V_{1}\left(s_{1}+1,s_{2}-1,s_{3}\right)\right)$
$\displaystyle+\frac{x_{3}\left(s_{1},s_{2},s_{3}\right)}{3}\left(p_{3}V_{1}\left(s_{1}-1,s_{2},s_{3}+1\right)+\left(1-p_{3}\right)V_{1}\left(s_{1}+1,s_{2},s_{3}-1\right)\right)$
$\displaystyle+\frac{\left(1-x_{3}\left(s_{1},s_{2},s_{3}\right)\right)}{3}\left(\left(1-p_{2}\right)V_{1}\left(s_{1},s_{2}-1,s_{3}+1\right)+p_{2}V_{1}\left(s_{1},s_{2}+1,s_{3}-1\right)\right).$
(8)

For every $\left(s_{1},s_{2},s_{3}\right)\in S_{i}$, the values of the
$\pi_{\left(s_{1},s_{2},s_{3}\right),\mathbf{s}^{\prime}}$ probabilities can
be read from (7); for $\left(s_{1},s_{2},s_{3}\right)\in S_{1}$, the values of
the $\pi_{\left(s_{1},s_{2},s_{3}\right),\mathbf{s}^{\prime}}$ probabilities
can be read from (5)-(6).

The equations (3)-(8) are the _payoff system_ for $\mathbf{V}_{1}$. We have
similar payoff systems for $\mathbf{V}_{2}$ and $\mathbf{V}_{3}$. In the rest
of this section we will focus on $\mathbf{V}_{1}$. Let
$\Pi\left(\mathbf{x}\right)$ be the transition probability matrix with
$\Pi_{\mathbf{s,s}^{\prime}}\left(\mathbf{x}\right)=\pi_{\mathbf{s,s}^{\prime}}\left(\mathbf{x}\right)$
(for all $\mathbf{s,s}^{\prime}\in S$). Then the _payoff system_ can be
written as

$V_{1}\left(K,0,0\right)=1\text{ and
}V_{1}\left(0,K,0\right)=V_{1}\left(K,0,0\right)=0\text{ and
}\mathbf{V}_{1}=\Pi\left(\mathbf{x}\right)\mathbf{V}_{1}\text{. }$ (9)

This is a linear system and can be solved by the standard methods. An
alternative but equivalent form of (9) is the following. Recall that we have
numbered the states $\mathbf{s}\in S$ so that the first state is
$\left(K,0,0\right)$, the second is $\left(0,K,0\right)$ and the third is
$\left(0,0,K\right)$. Now define the matrix
$\widetilde{\Pi}_{1}\left(\mathbf{x}\right)$ and the vector $\mathbf{b}_{1}$
as follows:

$\widetilde{\Pi}_{1}\left(\mathbf{x}\right)=\left[\begin{array}[c]{cccc}0&0&...&0\\\
0&0&...&0\\\ 0&0&...&0\\\ \pi_{4,1}&\pi_{4,2}&...&\pi_{4,N_{K}}\\\
...&...&...&...\\\
\pi_{N_{K},1}&\pi_{N_{K},2}&...&\pi_{N_{K},N_{K}}\end{array}\right],\qquad\mathbf{b}_{1}=\left[\begin{array}[c]{c}1\\\
0\\\ 0\\\ 0\\\ ...\\\ 0\end{array}\right]$

Then (9) is equivalent to

$\mathbf{V}_{1}=\widetilde{\Pi}_{1}\left(\mathbf{x}\right)\mathbf{V}_{1}+\mathbf{b}_{1}\mathbf{.}$
(10)

If the payoff system (10) has exactly one solution
$\overline{\mathbf{V}}_{1}$, then $\overline{V}_{1}\left(s\right)$ is
$P_{1}$’s payoff when the game starts with capitals
$s=\left(s_{1},s_{2},s_{3}\right)$.

###  4.2 Markov Chains

As already mentioned, for every stationary strategy profile $\mathbf{x}$, the
process $\left(\mathbf{s}\left(t\right)\right)_{t=0}^{\infty}$ is a Markov
chain, with transition probability matrix $\Pi\left(\mathbf{x}\right)$.

###### Proposition 4.1

If for all $m,n\in\left\\{1,2,3\right\\}$ we have $p_{mn}\in\left(0,1\right)$
then, for every $\mathbf{x}$, every interior state communicates with all
terminal states.

Proof. Take any state $\mathbf{s=}\left(s_{1},s_{2},s_{3}\right)\in S_{i}$ and
suppose that the game is in $\mathbf{s}$; let $\delta=\min_{m,n}p_{mn}$. Then
we have

$\displaystyle\Pr\left(\text{\textquotedblleft}P_{1}\text{ is selected and he
loses the turn\textquotedblright}\right)$
$\displaystyle\geq\frac{1}{3}\left(x_{12}\left(\mathbf{s}\right)p_{21}+x_{13}\left(\mathbf{s}\right)p_{31}\right)$
$\displaystyle\geq\frac{1}{3}\left(x_{1}\left(\mathbf{s}\right)p_{21}+\left(1-x_{1}\left(\mathbf{s}\right)\right)p_{31}\right)\geq\frac{\delta}{3}.$

In other words, there is a positive probability that the game moves to a state
$\mathbf{s}^{\prime}=\left(s_{1}-1,s_{2}^{\prime},s_{3}^{\prime}\right)$.
Hence there is a positive probability that eventually the game will reach a
boundary state
$\mathbf{s}^{\prime\prime}=\left(0,s_{2}^{\prime},s_{3}^{\prime}\right)$;
either $\mathbf{s}^{\prime\prime}\ $is a terminal state itself, or
$\mathbf{s}^{\prime\prime}\in S\backslash\left(S_{i}\cup S_{\tau}\right)$ and
communicates with both $\left(0,K,0\right)$ and $\left(0,0,K\right)$. Hence
$\mathbf{s}$ communicates with both $\left(0,K,0\right)$ and
$\left(0,0,K\right)$. Repeating the argument for $P_{2}$ we see that
$\mathbf{s}$ also communicates with $\left(K,0,0\right)$.

By Proposition 4.1 and standard Markov chain results [11, 16], every
nonterminal state is transient and the game will reach _some_ terminal state
w.p. 1 and in finite expected time. Furthermore we have the following.

###### Proposition 4.2

If for all $m,n\in\left\\{1,2,3\right\\}$ we have $p_{mn}\in\left(0,1\right)$,
then, for every $\mathbf{x}$, the limit
$\overline{\Pi}\left(\mathbf{x}\right)=\lim_{t\rightarrow\infty}\Pi^{t}\left(\mathbf{x}\right)$
exists.

Proof. Recall that the three terminal states are numbered as first, second and
third. Since they are absorbing and all other states are transient, the
probability transition matrix has the form

$\Pi\left(\mathbf{x}\right)=\left[\begin{array}[c]{cc}I&0\\\
W&U\end{array}\right].$ (11)

Then we have

$\Pi^{t}\left(\mathbf{x}\right)=\left[\begin{array}[c]{cc}I&0\\\
\left(\sum_{i=0}^{t}U^{i}\right)W&U^{t}\end{array}\right]$

By standard Markov chain results [11, 16] $\ \lim_{t\rightarrow\infty}U^{t}=0$
and $\lim_{t\rightarrow\infty}\sum_{i=0}^{t}U^{i}$ exists and equals
$\left(I-U\right)^{-1}$. Hence

$\lim_{t\rightarrow\infty}\Pi^{t}\left(\mathbf{x}\right)=\left[\begin{array}[c]{cc}I&0\\\
\lim_{t\rightarrow\infty}\left(\sum_{i=0}^{t}U^{i}\right)W&U^{t}\end{array}\right]=\left[\begin{array}[c]{cc}I&0\\\
\left(I-U\right)^{-1}W&0\end{array}\right].$

This completes the proof.

###### Proposition 4.3

If the limit
$\overline{\Pi}\left(\mathbf{x}\right)=\lim_{t\rightarrow\infty}\Pi^{t}\left(\mathbf{x}\right)$
exists then

$\forall\left(s_{1},s_{2},s_{3}\right)\in
S:\overline{\Pi}_{\left(s_{1},s_{2},s_{3}\right),\left(K,0,0\right)}\left(\mathbf{x}\right)=V_{1}\left(s_{1},s_{2},s_{3}\right).$

Proof. Recall that

$\forall\left(s_{1},s_{2},s_{3}\right)\in
S:V_{1}\left(s_{1},s_{2},s_{3}\right)=\Pr\left(\text{\textquotedblleft}P_{1}\text{
wins when the game has started in
}\left(s_{1},s_{2},s_{3}\right)\text{\textquotedblright}\right)$

We have the following possibilities.

  1. 1.

If $\left(s_{1},s_{2},s_{3}\right)=\left(K,0,0\right)$, then
$\overline{\Pi}_{\left(s_{1},s_{2},s_{3}\right),\left(K,0,0\right)}\left(\mathbf{x}\right)=1=V_{1}\left(K,0,0\right)$.

  2. 2.

If $\left(s_{1},s_{2},s_{3}\right)=\left(0,K,0\right)$, then
$\overline{\Pi}_{\left(0,K,0\right),\left(K,0,0\right)}\left(\mathbf{x}\right)=0=V_{1}\left(0,K,0\right)$.

  3. 3.

If $\left(s_{1},s_{2},s_{3}\right)=\left(0,0,K\right)$, then
$\overline{\Pi}_{\left(0,0,K\right),\left(K,0,0\right)}\left(\mathbf{x}\right)=0=V_{1}\left(0,0,K\right)$.

  4. 4.

If $\left(s_{1},s_{2},s_{3}\right)\in S\backslash S_{\tau}$, then
$\overline{\Pi}_{\left(s_{1},s_{2},s_{3}\right),\left(K,0,0\right)}\left(\mathbf{x}\right)=\left(\left(\sum_{i=0}^{\infty}U^{i}\right)W\right)_{\left(s_{1},s_{2},s_{3}\right),\left(K,0,0\right)}$.
This is the probability that:
$\left(s_{1}\left(t\right),s_{2}\left(t\right),s_{3}\left(t\right)\right)$
stays in $S\backslash S_{\tau}$ for $i$ steps (for some
$i\in\left(0,1,...\right)$) and then moves into $\left(K,0,0\right)$. In every
such case $P_{1}$ wins.

This completes the proof.

Hence we can compute $\mathbf{V}_{1}$ as the limit of
$\Pi^{t}\left(\mathbf{x}\right)$. From standard MC analysis [11, 16] we can
get estimates of the $\Pi^{t}$ rate of convergence, mean absorption time etc.
Another way to compute $\mathbf{V}_{1}$ is provided by the following.

###### Proposition 4.4

Suppose that $\mathbf{x}$ is such that
$\overline{\Pi}\left(\mathbf{x}\right)=\lim_{t\rightarrow\infty}\Pi^{t}\left(\mathbf{x}\right)$
exists. Choose an arbitrary $N_{K}\times 1$ vector
$\mathbf{U}_{1}^{\left(0\right)}$ and

$\text{For}\ t\in\left\\{0,1,2...\right\\}\text{ let:}\
\mathbf{U}_{1}^{\left(t+1\right)}=\widetilde{\Pi}_{1}\left(\mathbf{x}\right)\mathbf{U}_{1}^{\left(t\right)}+\mathbf{b}_{1}\mathbf{.}$
(12)

The iteration (12) converges and
$\overline{\mathbf{U}}=\lim_{t\rightarrow\infty}\mathbf{U}^{\left(t\right)}$
is a solution of the payoff system (10).

Proof. The key fact here is that, for any solution $\mathbf{V}_{1}$ of the
payoff system:

  1. 1.

when $\mathbf{s\in}S_{\tau}$, $V_{1}\left(s\right)$ is fixed to be either 0 or
1;

  2. 2.

when $\mathbf{s\in}S_{\tau}^{c}$, $V_{1}\left(\mathbf{s}\right)$ is the
weighted average of its neighbors:

$V_{1}\left(\mathbf{s}\right)=\sum_{\mathbf{s}^{\prime}\in
N\left(\mathbf{s}\right)}\pi_{\mathbf{s,s}^{\prime}}V_{1}\left(\mathbf{s}^{\prime}\right).$

Consequently, every solution of the payoff system is a harmonic function.
Hence the payoff system has a unique solution $\mathbf{V}_{1}$ which can be
obtained as the limit of (12).

###  4.3 Stationary Equilibria

We want to show that $\Gamma_{3}\left(\mathbf{p},K\right)$ posseses a Nash
equilibrium (NE), i.e., a strategy profile $\widehat{\mathbf{\sigma}}$ such
that:

$\forall
n,\forall\mathbf{\sigma}_{n}:Q_{n}\left(\mathbf{s}\left(0\right),\widehat{\mathbf{\sigma}}_{n},\widehat{\mathbf{\sigma}}_{-n}\right)\geq
Q_{n}\left(\mathbf{s}\left(0\right),\mathbf{\sigma}_{n},\widehat{\mathbf{\sigma}}_{-n}\right)$
(13)

To this end we introduce an auxiliary _discounted_ game, denoted by
$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$, where
$\gamma\in\left(0,1\right)$.
$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$ is the same as
$\Gamma_{3}\left(\mathbf{p},K\right)$ except for the following.

  1. 1.

In $\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$ the states
$\left(K,0,0\right)$, $\left(0,K,0\right)$, $\left(0,0,K\right)$ are
_preterminal_ and we introduce a new terminal state $\overline{s}$; state
transition probabilities remain the same except that every preterminal state
$s\in S_{\tau}$ transits to $\overline{s}$ with probability one.

  2. 2.

We define _turn payoff_ functions $q_{n}\left(s\right)$:

$\forall n:q_{n}\left(s\right)=\left\\{\begin{array}[c]{rl}1&\text{iff }s\in
S_{n},\\\ 0&\text{else.}\end{array}\right.$

  3. 3.

The total payoff function $\widetilde{\mathsf{Q}}_{n}$ and the expected total
payoff function $\widetilde{Q}_{n}$ are defined as follows:

$\widetilde{\mathsf{Q}}_{n}\left(\mathbf{h}\right)=\sum_{t=0}^{\infty}\gamma^{t}q_{n}\left(s\right),\qquad\widetilde{Q}_{n}\left(s\left(0\right),\sigma\right)=\mathbb{E}_{\mathbf{s}\left(0\right),\mathbf{\sigma}}\left(\widetilde{\mathsf{Q}}_{n}\left(\mathbf{h}\right)\right)$

$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$ is a _discounted_
stochastic game and, according to the following well known theorem, possesses
a stationary NE.

######  Proposition 4.5 (Fink [10])

Every $N$-player discounted stochastic game has a stationary Nash equilibrium.

In the following proposition we strengthen Fink’s theorem for the case of
$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$.

###### Proposition 4.6

For every $\mathbf{p}$, $K$ and $\gamma$,
$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$ has a deterministic
stationary Nash equilibrium. In other words, there exists a
$\widehat{\mathbf{x}}=\left(\widehat{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)$
such that

$\forall n\in\left\\{1,2,3\right\\},\forall\mathbf{s}_{0}\in
S,\forall\mathbf{x}^{n}:\widetilde{Q}^{n}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)\geq\widetilde{Q}^{n}\left(\mathbf{s}_{0},\mathbf{x}_{n},\widehat{\mathbf{x}}_{-n}\right).$
(14)

Proof. According to [10], for a general $N$-player discounted stochastic game,
the following equations must be satisfied for all $n$ and $\mathbf{s}$ at a
Nash equilibrium333We have modified Fink’s notation, so as to conform to our
own.:

$\mathcal{V}_{n}\left(\mathbf{s}\right)=\max_{\mathbf{\sigma}_{n}\left(\mathbf{s}\right)}\sum_{a_{1}}...\sum_{a_{N}}\sigma_{1,a_{1}}\left(\mathbf{s}\right)...\sigma_{N,a_{N}}\left(\mathbf{s}\right)\left[q_{n}\left(\mathbf{s}\right)+\gamma\sum_{\mathbf{s}^{\prime}}\mathcal{P}\left(\mathbf{s}^{\prime}|\mathbf{s},a_{1},...,a_{N}\right)\mathcal{V}_{n}\left(\mathbf{s}^{\prime}\right)\right],$
(15)

where:

  1. 1.

$\sigma_{n}$ is $P_{n}$’s strategy, $\sigma_{n}\left(\mathbf{s}\right)$ is his
action probability vector at state $\mathbf{s}$ and
$\sigma_{n,a_{n}}\left(\mathbf{s}\right)$ is the probability that, given the
current game state is $\mathbf{s}$, $P_{n}$ plays action $a_{n}$.

  2. 2.

$\mathcal{V}_{n}\left(\mathbf{s}\right)$ is the expected payoff to $P_{n}$
obtained at equilibrium, when the game has started at state $\mathbf{s}$ and
the strategy and the strategy profile
$\sigma=\left(\sigma_{1},...,\sigma_{N}\right)$ is used.

  3. 3.

$q_{n}\left(\mathbf{s}\right)$ is $P_{n}$’s turn payoff at state $\mathbf{s}$.

  4. 4.

$\mathcal{P}\left(\mathbf{s}^{\prime}|\mathbf{s},a_{1},...,a_{N}\right)$ is
the probability that, given that the current state is $\mathbf{s}$ and the
player actions are $a_{1},...,a_{N}$, the next state is $\mathbf{s}^{\prime}$.

Let us now consider $\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$.
Since no player has a choice of strategy on boundary states, we only need to
consider interior states $\mathbf{s}=\left(s_{1},s_{2},s_{3}\right)\in S_{i}$.
Letting $n=1$ and taking into account (8), (15) becomes

$V_{1}\left(s_{1},s_{2},s_{3}\right)=\max_{x_{1}\left(s_{1},s_{2},s_{3}\right)}\gamma
G\left(x_{1}\left(s_{1},s_{2},s_{3}\right)\right)$

where

$\displaystyle G\left(x_{1}\left(s_{1},s_{2},s_{3}\right)\right)$
$\displaystyle=x_{1}\left(s_{1},s_{2},s_{3}\right)\frac{p_{1}V_{1}\left(s_{1}+1,s_{2}-1,s_{3}\right)+\left(1-p_{1}\right)V_{1}\left(s_{1}-1,s_{2}+1,s_{3}\right)}{3}$
$\displaystyle+\left(1-x_{1}\left(s_{1},s_{2},s_{3}\right)\right)\frac{\left(1-p_{3}\right)V_{1}\left(s_{1}+1,s_{2},s_{3}-1\right)+p_{3}V_{1}\left(s_{1}-1,s_{2},s_{3}+1\right)}{3}$
$\displaystyle+\text{terms which do not involve
}x_{1}\left(s_{1}s_{2}s_{3}\right)$

Clearly, the maximum is achieved at either
$x_{1}\left(s_{1},s_{2},s_{3}\right)=1$ or
$x_{1}\left(s_{1},s_{2},s_{3}\right)=0$. This holds for every interior state,
hence $P_{1}$’s strategy at equilibrium is deterministic (or can be
substituted by an equivalent deterministic one).

The same analysis can be applied to $P_{2}$ and $P_{3}$ to complete the proof.

###### Corollary 4.7

For every $\mathbf{p}$ and $K$, $\Gamma_{3}\left(\mathbf{p},K\right)$ has a
deterministic stationary NE.

Proof. Let
$\widehat{\mathbf{x}}\mathbf{=}\left(\widehat{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)$
be a a deterministic stationary NE of
$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$. Suppose that, for
some $\mathbf{s}_{0}$ and $t$, we have

$\widetilde{Q}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right)=\left(\widetilde{Q}_{1}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right),\widetilde{Q}_{2}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right),\widetilde{Q}_{3}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right)\right)=\left(\gamma^{t},0,0\right).$

This means that, in $\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$,
$P_{1}$ has won at time $t$. Applying the same $\widehat{\mathbf{x}}$ in
$\Gamma_{3}\left(\mathbf{p},K,\gamma\right)$, we have

$Q\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right)=\left(Q_{1}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right),Q_{2}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right),Q_{3}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right)\right)=\left(1,0,0\right).$

Clearly

$\forall\mathbf{x}_{1}:Q_{1}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{-1}\right)\geq
Q_{1}\left(\mathbf{s}_{0},\mathbf{x}_{1},\widehat{\mathbf{x}}_{-1}\right).$

Also, if there was some $\mathbf{y}_{n}$ (with $n\in\left\\{2,3\right\\}$)
such that

$Q_{1}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)<Q_{1}\left(\mathbf{s}_{0},\mathbf{y}_{n},\widehat{\mathbf{x}}_{-n}\right)$

then $P_{n}$ could win $\Gamma_{3}\left(\mathbf{p},K\right)$ (when starting at
$\mathbf{s}_{0}$) by using $\mathbf{y}_{n}$ against
$\widehat{\mathbf{x}}_{-n}$. But then he could also win
$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$ (when starting at
$\mathbf{s}_{0}$) by using the same $\mathbf{y}_{n}$ against
$\widehat{\mathbf{x}}_{-n}$, so we would have

$\widetilde{Q}_{1}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)<\widetilde{Q}_{1}\left(\mathbf{s}_{0},\mathbf{y}_{n},\widehat{\mathbf{x}}_{-n}\right).$

But this is contrary to the hypothesis. The proof is similar for the case in
which, for some $\mathbf{s}_{0}$ and $t$,

$\widetilde{Q}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right)=\left(\widetilde{Q}_{1}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right),\widetilde{Q}_{2}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right),\widetilde{Q}_{3}\left(\mathbf{s}_{0},\widehat{\mathbf{x}}\right)\right)=\left(0,0,0\right).$

We conclude that:

$\forall n\in\left\\{1,2,3\right\\},\forall\mathbf{s}_{0}\in
S,\forall\mathbf{x}^{n}:\widetilde{Q}_{n}\left(s_{0},\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)\geq\widetilde{Q}_{n}\left(s_{0},\mathbf{x}_{n},\widehat{\mathbf{x}}_{-n}\right)$

and the proof is complete.

###  4.4 Nonstationary Equilibria

So far we have established that $\Gamma_{3}\left(\mathbf{p},K\right)$ has at
least one stationary NE. It is conceivable that the existence of
_nonstationary_ NE can also be established by standard game theoretical
arguments. We will only present some initial ideas on the subject, and
relegate a full analysis to the future.

We limit our discussion to a variant of the discounted game, which we call
$\Gamma_{3}^{\prime}\left(\mathbf{p},K,\gamma\right)$. This is the same as
$\widetilde{\Gamma}_{3}\left(\mathbf{p},K,\gamma\right)$, except in that the
losing players incur a cost of $-1$; hence a player who loses all his capital
at some time $t^{\prime}$, receives payoff $-\gamma^{t^{\prime}}$.

In $\Gamma_{3}^{\prime}\left(\mathbf{p},K,\gamma\right)$ a player wants to win
or, if this is not possible, to lose at the latest possible time. Under the
circumstances, it is conceivable that, for example, $P_{1}$ and $P_{2}$ form
an alliance against $P_{3}$, with the goal of bankrupting him first. For
example, $P_{1}$ and $P_{2}$ might continuously play against $P_{3}$, forming
in effect a “superplayer” with a higher probability of defeating $P_{3}$.
However, what is required is a mechanism to enforce the alliance. This can be
provided by using a “trigger” strategy: $P_{1}$ selects $P_{3}$ as long as
$P_{2}$ does the same; if at some round $P_{2}$ selects $P_{1}$, then $P_{1}$
selects $P_{2}$ in all subsequent rounds. It appears likely that, under
appropriate conditions on $\gamma$, this strategy will be a (nonstationary)
NE. A “tit-for-tat” strategy might work in similar manner.

##  5 Computation of Stationary Equilibria

We now present a very preliminary examination of stationary NE computation (a
more extensive account will be presented at a later time). We want to find a
stationary strategy profile $\widehat{\mathbf{x}}$ such that:

$\forall
n,\mathbf{s},\mathbf{x}_{n}:Q_{n}\left(\mathbf{s},\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)\geq
Q_{n}\left(\mathbf{s},\mathbf{x}_{n},\widehat{\mathbf{x}}_{-n}\right)$ (16)

or, equivalently,

$\forall
n,\mathbf{s},\mathbf{x}_{n}:V_{n,\mathbf{s}}\left(\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)\geq
V_{n,\mathbf{s}}\left(\mathbf{x}_{n},\widehat{\mathbf{x}}_{-n}\right).$ (17)

Now, (17) can be rewritten as

$\forall
n,\mathbf{s}:V_{n,s}\left(\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)=\max_{\mathbf{x}_{n}}V_{n,s}\left(\mathbf{x}_{n},\widehat{\mathbf{x}}_{-n}\right)=\max_{\mathbf{x}_{n}}\left(\left[\widetilde{\Pi}\left(\mathbf{x}_{n},\widehat{\mathbf{x}}_{-n}\right)\mathbf{V}_{n}+\mathbf{u}_{n}\right]_{s}\right).$
(18)

We define

$\forall
n,\mathbf{s}:F_{n,\mathbf{s}}\left(\mathbf{V}_{1}|\mathbf{x}\right)=\max_{\mathbf{x}_{n}}\left(\left[\widetilde{\Pi}\left(\mathbf{x}\right)\mathbf{V}_{n}+\mathbf{u}_{n}\right]_{s}\right)$
(19)

Then we can rewrite (18) as

$\forall
n:\mathbf{V}_{n}\left(\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)=\mathbf{F}_{n}\left(\mathbf{V}_{n}|\widehat{\mathbf{x}}\right),$
(20)

This system of nonlinear equations will, by the previous analysis, have at
least one solution. We can either solve (20) directly or, alternatively,
minimize

$J\left(\mathbf{x}\right)=\sum_{n=1}^{3}\left\|\mathbf{V}_{n}\left(\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)-\mathbf{F}_{n}\left(\mathbf{V}_{n}|\widehat{\mathbf{x}}\right)\right\|^{2}.$
(21)

One possibility is to solve (20) by exhaustive enumeration. For a given $K$ we
have $g\left(K\right)=\frac{\left(K+1\right)\left(K+2\right)}{2}-3K$ states in
which there exist strategy choices and, if we limit ourselves to pure
strategies, for each such state we have $2^{3}=8$ strategy outcome
combinations. Hence there exist $h\left(K\right)=2^{3g\left(K\right)}$
possible overall strategy combinations. In the following table we list the
values of $g\left(K\right)$ and $h\left(K\right)$ as functions of $K$.

$K$ | $3$ | $4$ | $5$ | $6$ | $7$
---|---|---|---|---|---
$g\left(K\right)$ | $1$ | $3$ | $6$ | $10$ | $15$
$h\left(K\right)$ | $2^{3}=8$ | $2^{9}=\allowbreak 512$ | $2^{18}=\allowbreak 262\,144$ | $2^{30}=\allowbreak 1073\,741\,824$ | $2^{45}=\allowbreak 35\,184\,\allowbreak 372\,088\,832$

Table 1

It appears that finding a NE by exhaustive enumeration is feasible for , for
$K<6$; for larger $K$ values the computational burden is probably
unmanageable.

An alternative approach is to use an iterative approach, inspired from _Value
Iteration_ which provably yields a solutin for _two-player zero-sum_ games
[9]. Based on this, we can use the _MultiValue Iteration_ (MVI) defined as
follows.

$\forall
n,s:V_{n}^{\left(t+1\right)}\left(s\right)=F_{n,s}\left(\mathbf{V}_{n}^{\left(t\right)}\left(s|\mathbf{x}^{\left(t\right)}\right)\right).$
(22)

If (22) converges (which is not a priori guaranteed) it can be proved that the
limit will be a solution of (20).

Finally, we can use various optimization algorithms to find a global minimum
(which must be equal to zero) of the function

$J\left(\widehat{\mathbf{x}}\right)=\sum_{n=1}^{3}\left\|\mathbf{V}_{n}\left(\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)-\mathbf{F}_{n}\left(\mathbf{V}_{n}|\widehat{\mathbf{x}}\right)\right\|^{2}.$
(23)

We have applied several optimization algorithms, provided by the Matlab
software system, to the minimization of (23). Most notably, we have used the
following:

  1. 1.

The Matlab function fmincon [17], which performs constrained gradient based
optimization [20].

  2. 2.

The Matlab function particleswarm [18], which implements _particle swarm
optimization_ [31].

We have performed several preliminary experiments and have found out that the
best performance is obtained by the MVI algorithm; hence we only report
results obtained by this particular algorithm. The main question is whether
the algorithm converges. We have run 100 repetitions of the following
experiment.

After randomly selecting a probabilities vector
$\mathbf{p\in}\left(0,1\right)^{3}$ we run MVI for 150 runs for each
$K\in\left\\{3,4,...,9\right\\}$, always initializing with
$\mathbf{x}^{\left(0\right)}=\mathbf{0}$. If a solution $\widehat{\mathbf{x}}$
of the optimality equations (i.e., an equilibrium strategy profile) is
achieved we count this as one succesful run of the MVI algorithm. After the
150 runs are completed, we compute, for each $K$, the proportion of succesful
runs. The results are plotted in Figure 1.

Figure 1: Proportion of succesful MVI runs for 100 randomly selected
$\mathbf{p}$ vectors, as a function of $K$.

Figure 2: Proportion of succesful MVI runs for 100 randomly selected
$\mathbf{p}$ vectors, as a function of $K$.

It can be seen that MVI is “relatively” succesful. That is, the proportion of
convergent runs is a decreasing function of $K$ (i.e., it is harder to find a
solution for larger $K$ values) and we have a “reasonable” probability of
success for $K\leq 7$; furthermore, even for $K\in\left\\{8,9\right\\}$ we
have a 50% or better probability of obtaining a solution. It must be
emphasized that this is a lower bound on the performance of MVI. Running MVI
repeatedly for a specific $\mathbf{p}$, with random initialization of
$\mathbf{x}^{\left(0\right)}$, yields a higher sucess proportion, as our
preliminary experiments (not reported here) indicate.

If we look at the MVI iteration (22) as a dynamical system, parametrized by
$\mathbf{p}$ and $K$, a natural question is this: given some $K$, for which
subset $\mathfrak{P}_{K}$ $\subset\left[0,1\right]^{3}$ does
$\mathbf{p}\in\mathfrak{P}_{K}$ ensure that (22) converges? Roughly speaking,
the results of Figure 1 indicate that, for example, the volume of
$\mathfrak{P}_{1}$ is 1.00, that of $\mathfrak{P}_{2}$ around 0.90 and so on.
To further investigate this point, we repeat the above experiment for a
restricted set of $\mathbf{p}$ values. For example, when we fix $p_{1}=1$ and
choose $p_{2}$ and $p_{3}$ randomly, we obtain the results of Figure 2.
Obviously for $\mathbf{p}\in\left\\{1\right\\}\times\left[0,1\right]^{2}$ the
MVI algorithm has much higher probability of convergence.

We conclude this section by an initial numerical exploration of the following
question:

how much does a player benefit by playing optimally?

To answer this, we perform several experiments of the following type.

  1. 1.

We fix a particular $\mathbf{p}$ vector and, for $K=9$, use the MVI algorithm
to obtain a NE
$\left(\widehat{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)$
and the corresponding
$V_{1}\left(\widehat{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)$.

  2. 2.

We assign to $P_{1}$ a random strategy $\overline{\mathbf{x}}_{1}$ and compute
his payoff
$V_{1}\left(\overline{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)$.

  3. 3.

We compute the difference $\overline{\delta
V}_{1}=V_{1}\left(\widehat{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)-V_{1}\left(\overline{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)$.

  4. 4.

We repeat steps 2 and 3 by assigning the random strategy
$\overline{\mathbf{x}}_{n}$ to $P_{n}$, for $n\in\left\\{2,3\right\\}$.

For $n\in\left\\{1,2,3\right\\}$, $\overline{\delta V}_{n}$ is a measure of
how much $P_{n}$ benefits by using the equilibrium strategy
$\widehat{\mathbf{x}}_{n}$ rather the random strategy
$\overline{\mathbf{x}}_{n}$, given that the other two players use the
equilibrium strategy. Because
$\left(\widehat{\mathbf{x}}_{1},\widehat{\mathbf{x}}_{2},\widehat{\mathbf{x}}_{3}\right)$
is a NE, we know that $\overline{\delta V}_{n}$ will always be nonnegative; a
large $\overline{\delta V}_{n}$ indicates that $P_{n}$ has a large incentive
for using $\widehat{\mathbf{x}}_{n}$.

We also repeat the above suite of experiments comparing the equilibrium
strategy $\widehat{\mathbf{x}}_{n}$ to a uniform strategy
$\widetilde{\mathbf{x}}_{n}$, by which, at every state $\mathbf{s}$, $P_{n}$
selects equiprobably one of the surviving players; now we compute the
quantities $\widetilde{\delta
V}_{n}=V_{1}\left(\widehat{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)-V_{1}\left(\widetilde{\mathbf{x}}_{n},\widehat{\mathbf{x}}_{-n}\right)$.

We perform the above experiments for several $\mathbf{p}$ values and present
our results in the following table.

$\mathbf{p}$ | $\overline{\delta V}_{1}$ | $\overline{\delta V}_{2}$ | $\overline{\delta V}_{3}$ | $\widetilde{\delta V}_{1}$ | $\widetilde{\delta V}_{2}$ | $\widetilde{\delta V}_{3}$
---|---|---|---|---|---|---
$\left(0.10,0.10,0.10\right)$ | 0.2357 | 0.2266 | 0.2072 | 0.1995 | 0.1995 | 0.1995
$\left(0.90,0.00,0.50\right)$ | 0.0619 | 0.0071 | 0.0726 | 0.0643 | 0.5321 | 0.0863
$\left(0.80,0.80,0.50\right)$ | 0.1455 | 0.0339 | 0.0318 | 0.1177 | 0.0462 | 0.0308
$\left(0.3922,0.8932,0.6634\right)$ | 0.0088 | 0.1421 | 0.0084 | 0.0091 | 0.1017 | 0.0069
$\left(0.53,0.20,0.80\right)$ | 0.0025 | 0.0033 | 0.0948$\times 10^{-12}$ | 0.0032 | 0.0026 | 0.0963$\times 10^{-12}$
$\left(0.9000,0.8747,0.2252\right)$ | 0.0616 | 0.0032 | 0.0006 | 0.0519 | 0.0023 | 0.0009

Table 1

Keeping in mind that the quantities $\overline{\delta V}_{n}$ and
$\widetilde{\delta V}_{n}$ are differences between winning probabilities, the
results of Table 1 indicate that in some cases a player has considerable
incentive to use the equilibrium strategy; this is the case for the
$\mathbf{p}$’s in rows one to four of the table. On the other hand, for the
$\mathbf{p}$’s of rows five and six the player does not gain much by staying
at equilibrium.

##  6 Conclusion

We have presented a strategic game version of the Three Gamblers’ Ruin,
formulated it as a stochastic game and proved that it always has at least one
stationary deterministic NE. We have also briefly investigated the
computational aspects of the game. We believe there is scope for much
additional research on strategic variants of the Gambler’s ruin; we conclude
by listing several such variants which we consider worthy of further study in
the future.

  1. 1.

The game is played as before but ends when one player is eliminated. Payoff to
each player is his capital at the end of the game.

  2. 2.

The game is played as previously but the payoff is the _total discounted_
capital $\sum_{t}\gamma^{t}s_{n}\left(t\right)$.

  3. 3.

All of the above games can be generalized to games involving $N$ gamblers.

  4. 4.

The game is played on a graph with a gambler on each vertex; gamblers can only
only play against their neighbors.

## References

  * [1] Amano, K. et al. “On a generalized ruin problem.” _International Workshop on Randomization and Approximation Techniques in Computer Science_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001.
  * [2] Bruss, F. T., Louchard, G. and Turner, J. W. (2003). “On the $N$-tower problem and related problems”. _Adv. Appl. Prob_., vol.35, pp. 278-294.
  * [3] Chang, D. K. (1995). “A game with four players”. _Stat. & Prob. Letters_, vol. 23, pp. 111–15.
  * [4] Cho, D.-H. (1996). “A game with $N$ players”. _J. of the Korean Stat. Soc._ , vol. 25, pp. 185–93.
  * [5] David, G. (2015) “Markov chain solution to the 3-tower problem”. In _Information and Communication Technology: Third IFIP TC 5/8 International Conference_.
  * [6] Edwards, A. W. F. (1983), “Pascal’s problem: the gambler’s ruin”, _Int. Statistical Review_ , vol. 51, pp. 73–79.
  * [7] Engel, A. (1993). “The computer solves the three tower problem”. _Amer. Math. Monthly_ , vol. 100, pp.62-67.
  * [8] Feller, W. (1991), _An introduction to probability theory and its applications_ , Vol. 1. John Wiley & Sons.
  * [9] Filar J. and Vrieze K., (1997), _Competitive Markov Decision Processes: Theory, Algorithms, and Applications_. Springer.
  * [10] Fink, A.M., (1964), “Equilibrium in a stochastic $n$-person game”. _J. of Sci. of the Hiroshima University, Series AI (Mathematics)_ , vol. 28, pp.89-93.
  * [11] Grinstead, C.M., and J.L. Snell, (1997), _Introduction to probability_. American Mathematical Soc.
  * [12] Grigorescu , I. and Yao, Y.C., (2016), “Maximizing the variance of the time to ruin in a multiplayer game with selection”. _Adv. in Appl. Prob._ , vol. 48, pp.610-630.
  * [13] Hashemiparast S.M. , Sabzevar M., (2011), “The asymmetric $n$-player gambler’s ruin problem with ties allowed and simulation”, _J. of the Korean Stat. Soc._ , vol. 40, pp. 267-276.
  * [14] Hussain A., (2021), “A three-player gambler’s ruin problem: some extensions”. _Sci. Inq. and Rev._ , vol. 5, pp. 1-11.
  * [15] Hussain A., (2023), “The ruin time for 3-player gambler’s problem: an approximate formula”, _Com. in Stat.–Simulation and Computation_ , vol. 52, pp. 1651-1659.
  * [16] Kemeny, J. G., and Snell, J.L., (1969), _Finite Markov chains_. Princeton, NJ: van Nostrand.
  * [17] Matlab documentation for fmincon, https://nl.mathworks.com/help/optim/ug/fmincon.html.
  * [18] Matlab documentation for the particle swarm optimization function pso, https://nl.mathworks.com/help/gads/particleswarm.html.
  * [19] Néda Z., Újvári, L.D.S. and Istrate, G., (2017), “Gambler’s ruin problem on Erdős–Rényi graphs”, _Physica A_ , vol. 468, pp. 147–157.
  * [20] Nocedal, J., Öztoprak, F., and Waltz, R.A., (2014), “An interior point method for nonlinear programming with infeasibility detection capabilities”. _Optimization Methods & Software_, vol. 29, pp. 837–854.
  * [21] Read R. C., (1966), “A type of gambler’s ruin problem”, _The Amer. Math. Monthly_ , vol. 73, pp. 177-179.
  * [22] Rocha A. and Stern F., (1999), “The gambler’s ruin problem with $N$ players and asymmetric play”. _Stat. Probabil. Lett_., vol. 44, pp. 87-95.
  * [23] Rocha, A. L., and F. Stern. (2004). “The asymmetric $n$-player gambler’s ruin problem with equal initial fortunes”. _Adv. in Appl. Mathematics_ , vol. 33, pp. 512–30.
  * [24] Ross, S. M. (2009). “A simple solution to a multiple player gambler’s ruin problem”. _Amer. Math. Monthly_ , vol. 116, pp. 77-81.
  * [25] Swan, Y. C. and Bruss, F. T. (2006). “A matrix-analytic approach to the $N$-player ruin problem”. _J. Appl. Prob_. 43, 755-766
  * [26] Sandell, D., (1988). “A game with three players”. _Stat. & Prob. Letters_, vol. 7, pp. 61–63.
  * [27] Song, S. and Song, J. (2013) “A note on the history of the gambler’s ruin problem”. _Comm. Statist. Applic. Methods_ , vol. 20, pp. 1–12.
  * [28] Stirzaker, D. (1994), “Tower problems and martingales”. _Math. Scientist_ , vol. 19, pp. 52-59.
  * [29] Stirzaker, D. (2006), “Three-Handed Gambler’s Ruin”, _Adv. in Appl. Prob._ , vol. 38, pp. 284-286.
  * [30] Takacs, L. (1969). “On the classical ruin problems”. _J. of the Amer. Stat. Assoc._ , vol. 64, pp. 889–906.
  * [31] Wang, D., Tan D., and Liu, L., (2018), “Particle swarm optimization algorithm: an overview.” _Soft Computing_ , vol. 22, pp. 387-408.


numbersnone#1none:
left:
right:

# LLM-Aided Testbench Generation and
Bug Detection for Finite-State Machines

Jitendra Bhandari1, Johann Knechtel2, Ramesh Narayanaswamy3, Siddharth Garg1,
and Ramesh Karri1  1New York University, New York, USA 2New York University
Abu Dhabi, UAE 3Synopsys, Sunnyvale, CA, USA

###### Abstract

This work investigates the potential of tailoring Large Language Models
(LLMs), specifically GPT3.5 and GPT4, for the domain of chip testing. A key
aspect of chip design is functional testing, which relies on testbenches to
evaluate the functionality and coverage of Register-Transfer Level (RTL)
designs. We aim to enhance testbench generation by incorporating feedback from
commercial-grade Electronic Design Automation (EDA) tools into LLMs. Through
iterative feedback from these tools, we refine the testbenches to achieve
improved test coverage. Our case studies present promising results,
demonstrating that this approach can effectively enhance test coverage. By
integrating EDA tool feedback, the generated testbenches become more accurate
in identifying potential issues in the RTL design. Furthermore, we extended
our study to use this enhanced test coverage framework for detecting bugs in
the RTL implementations.

###### Index Terms:

LLM, EDA, Testing, Coverage Analysis, FSM

##  I Introduction

Testbench generation is vital in the integrated circuit (IC) design cycle to
ensure that chips are functional, meet design specifications, and are of high
quality. Testbenches are designed to activate and monitor a wide range of
design behaviors, ensuring that every part of a circuit is exercised during
testing, leaving no function unchecked. This comprehensive testing approach
not only ensures functional correctness but also provides valuable insights
that can lead to design optimizations. Functional bugs tend to occur in a
chip’s control path, which is often implemented via Finite-State Machines
(FSMs). These FSMs orchestrate the sequence of operations within the chip,
making their correct function critical. Thus, achieving full FSM coverage is
often a requirement for compliance with industry standards, particularly in
sectors like aerospace and medical devices etc., where high reliability and
safety are paramount [1].

Large Language Models (LLMs) [2] have revolutionized the way developers
approach coding and testing, including the realm of hardware description
languages (HDL). Recent work has demonstrated the utility of LLMs for various
hardware-related tasks. For example, LLMs have been used for Verilog code
generation [3, 4, 5, 6], where they help in writing and optimizing HDL code.
They have also been employed in generating assertions [7, 8], which are
critical for verifying the correctness of HDL designs. Additionally, LLMs have
shown promise in scripting for electronic design automation (EDA) tools [9,
10], streamlining the design and verification process. These methods either
directly leverage foundation models like GPT, or fine-tune specialized code
generation models on hardware datasets. Results from these studies suggest
that LLMs can effectively understand Verilog code with its syntax, structure,
and functional requirements. This understanding enables LLMs to assist in
various stages of the design and verification process, improving efficiency
and accuracy.

Scope of This Work: First, we explore LLMs for _automated_ testbench
generation of FSMs. Through our case studies, we find that by _using feedback
from commercial EDA simulation tools_ , LLMs can improve FSM test coverage.
Second, we analyze the bug detection capability by _providing output traces
from the tools and utilizing prompting techniques_.

Figure 1: Contribution 1: LLM-aided Testbench Generation. Figure 2:
Contribution 2: LLM-aided Bug Detection.

##  II Background and Related Work

Functional testing of RTL modules is crucial to ensure correct functionality.
State-of-the-art verification techniques include both functional and formal
verification, along with coverage analysis. These techniques rely on the
careful formulation of assertions, often using System-Verilog, and the
generation of comprehensive test patterns. Designers and test engineers find
it especially challenging to create a testbench and generate effective test
patterns. This difficulty increases when the design is still in progress and
involves multiple team members. Testbench compilation requires a thorough
understanding of the RTL code. Designers must meticulously analyze the code to
generate test patterns that achieve complete coverage. Effective coverage
analysis helps identify untested parts of the design, guiding further test
development.

LLMs and their increasing prominence, as highlighted by the developments of
models like GPT-4 [2], have sparked broad interest in various fields.
Specifically, chip design has seen a surge in innovative approaches leveraging
LLMs, such as [11]. Considerable progress has been made in improving the
quality of Verilog code generation [3, 4, 5, 6]. These studies introduce
methodologies to refine the process of generating Verilog code, demonstrating
the potential of LLMs to streamline and improve hardware design workflows.
Furthermore, [12, 13, 14] showcases the effectiveness of prompting strategies
in chip design. They harness the power of LLMs to conceptualize and detail the
intricate aspects of hardware architectures, paving the way for efficient chip
development. The work in [10] extends LLM applications into assistant
chatbots, script generation, and bug analysis. Similarly, [9] explores the use
of LLMs for task planning and execution within the EDA flow, highlighting the
potential for automating and optimizing complex workflows. Finally, the
generation of assertions for verifying the correctness of IC designs, has been
enhanced through LLMs [7, 8].

##  III Methodology

We study the capabilities of LLMs for both _coverage-guided testbench
generation_ and _automated bug detection_.

###  III-A LLM (and coverage)-guided Testbench Generation

Fig. 1 illustrates an LLM-guided methodology for automatic testbench
generation for FSMs. Any LLM can be employed and without loss of generality,
we use GPT3.5 and GPT4. The inputs are: (1) an English-language
specification111specification could be phrased as “ _Write a Verilog module
that detects a 1011 pattern and outputs a 1 anytime the last four inputs match
with this pattern, and 0 otherwise._ ”, and (2) a Verilog RTL description of
design-under-test (DUT). The question we seek to address here is: Can we
automatically generate a high-quality testbench for such DUT Verilog code? We
first need a metric to measure the quality of a testbench. A common metric,
especially for FSMs, is _transition coverage_ , i.e., there should be at least
one set of test patterns that covers all state transitions in the FSM. Several
simulation tools provide _coverage reports_ , including state and transition
coverage. Here, we investigate if we can use such coverage reports as feedback
to iteratively improve coverage of an LLM-generated testbench.

Our method for automatic testbench generation involves several steps to ensure
comprehensive testing of FSMs. First, we prompt an LLM to generate an initial
testbench using the Verilog code of the DUT as input, as shown in Fig. 3(a).
This Verilog code represents the FSM that needs to be tested. The LLM
processes this input and generates a testbench that is intended to verify the
function of the DUT. Next, the generated testbench undergoes a compilation
check using commercial EDA tools. In this step, the testbench is checked for
syntax and logic errors. If any errors are detected during compilation, these
errors are appended to the prompt and fed back to the LLM. The LLM uses this
feedback to refine and correct its output iteratively until an error-free
testbench is produced.

Next, the FSM is simulated in coverage analysis mode. The simulation yields a
report that quantifies how thoroughly the testbench exercises the FSM. The
coverage report identifies any FSM transitions that the testbench has missed,
highlighting areas where the testbench needs improvement. Uncovered
transitions in the coverage report are used as prompts for the LLM, as shown
in Fig. 3(b). These prompts guide the LLM to generate new test cases to cover
missing transitions. By doing so, we ensure that the testbench comprehensively
tests all functional parts of the FSM. Generating new test cases and
performing coverage analysis is repeated, as shown in Fig. 1. The cycle
continues until full transition coverage is achieved or may stop once a user-
defined threshold is met. Fig. 5 shows a testbench that yields 100% coverage.

You are an expert in design verification for Verilog code. Given a Verilog RTL
module, you will write a testbench to simulate it and try to cover all the
possible state transitions. Please follow the below instructions while
providing any response:
1. The testbench should start with module tb(); 2. You will add $fsdbDumpfile, $fsdbDumpvars commands in the testbench at the start of the first initial block. 3. Please use apply_input() format to apply input sequences. 4. You should consider whether it requires an active or high reset from the RTL code provided. 5. At the end of test patterns add $finish. (a) System Prompt for GPT.

The above testbench provided doesn’t cover all the transitions. This is the
list of transitions that were expected but didn’t happen:
”Transition from A to B”
Please consider the RTL Verilog code provided while providing the testbench
and combine the test cases from the above response. You may have to reset a
few times to cover certain transitions. (b) Prompt 1, to guide on some
transitions not covered yet.

We ran the simulation tool with the testbench, this is the value for the state
register variable across the clock cycle, the sequence is provided serially
starting from 0 till the simulation finishes. This also shows the transition
at each clock cycle.
”S0 S1 S2 S3 S1 S5………………………………”
Please use the design specification provided and find out if there is any
mismatch between them. We are looking to see if any transitions are
inconsistent with the design spec. (c) Prompt 2, to verify the test outputs
with the design specification.

Figure 3: Exemplary prompts used with GPT.

###  III-B LLM-guided Automated Bug Detection

RTL may contain bugs, either intentionally inserted or accidental, that need
to be identified and fixed during testing. Given a testbench, we simulate the
FSM and record the results of each test case. These simulation results and the
original design specification in plain English are provided to the LLM. The
LLM is tasked with identifying failing test cases by comparing the simulation
outcomes with the expected behavior described in the specification in Fig. 2.
This capability is powerful because the LLM can operate on less formal,
natural-language descriptions. Creating a formal specification is complex, and
time-consuming. Fig. 3(c) provides prompts.

We use testbenches generated in part 1 as the starting point for bug
detection. Our study shows that, as the FSM becomes complex the number of
input patterns to detect the bugs increases notably. This leads to a large I/O
trace obtained after the simulation, as shown in Fig. 2. GPT cannot comprehend
this, thus missing potential bugs. This naive approach thus does not scale. To
address these challenges, we employ tww improvements to prompting: (1)
Dividing I/O patterns into smaller sets to track states, and (2) Handling
multi-bit inputs and outputs individually to manage sub-circuits (output
cones), as shown in Fig. 4. An analysis is in Section IV(C).

This is the input-output pair for the first 10 clock cycles. Please use the
design specification provided and find out if there is any mismatch between
them. We are looking to see if any transitions are inconsistent with the
design spec. This will be followed up with the next 10 clock cycles and so on.
After every 10th clock cycle please remember the current state which is very
important when we provide new 10 input-output pairs. (a) Prompt 3, sub-divide
all the input/output pairs.

To simplify the mismatch detection, consider the provided input-output pair
for each clock cycle. Start the detection process by focusing on one bit of
output and check for correct values as the input patterns are applied,
followed by checking on other bits of output as well. (b) Prompt 4, handle
multi-bit input and output scenarios separately.

Figure 4: Additional Prompt for GPT during detection step.

⬇

1module tb_fsm();

2 reg clk;

3 reg rst;

4 reg inp;

5 wire out1;

6 wire out2;

7

8 fsm uut(.clk(clk), .rst(rst), .inp(inp), .out1(out1), .out2(out2));

9 // Clock generation

10 always begin

11 #5 clk = ~clk;

12 end

13

14 // Test procedure

15 initial begin

16 // Initialize signals

17 clk = 0;

18 rst = 1;

19 inp = 0;

20 #10 rst = 0;

21

22 // Set up FSDB file for waveform viewing

23 $fsdbDumpfile(”test.fsdb”);

24 $fsdbDumpvars;

25

26 // Test sequence to cover all transitions

27 // S0 -> S1 -> S2 -> S3 -> S4 -> S5 -> S6 -> S7 with inp=1

28 apply_input_sequence(8’b11111111);

29 // Rest of the test patterns

30 // …..

31 $stop;

32 end

33 // Task to apply input and display results

34 task apply_input(input reg in);

35 inp = in;

36 #10; // Wait for one clock cycle

37 endtask

38 // Task to apply a sequence of inputs

39 task apply_input_sequence(input reg [7:0] seq);

40 integer i;

41 for (i = 7; i >= 0; i = i - 1) begin

42 apply_input(seq[i]);

43 end

44 endtask

45

46endmodule

Figure 5: An LLM-generated testbench exercising the design under test, in this
instance an FSM.

##  IV Experiments

###  IV-A Setup

Our study uses GPT(3.5/4), Synopsys VCS U-2023.03-1 and Synopsys Verdi
U-2023.03-1. The latter tools are for compiling and simulating Verilog code,
debugging, and using its coverage reports as feedback. An example VCS report
template is shown in Fig. 6. We automated the framework in Fig. 1 and Fig. 2
in Python, including testbench generation, code compilation, coverage
analysis, and comparison of test cases with natural-language specifications.
For our case studies, we obtained a large number of representative FSMs from
HDLBits [15] and GitHub, with varying complexity in terms of number of states
and transitions. 100 FSMs are used in our study.222We show 50/100 cases,
capturing the complexity of the dataset. Full analysis of the datasets,
including the RTL source code and the testbenches are available at [16]. The
remaining 50 cases are in the appendix, Table II.

FSM Coverage for Module : fsm
---
Summary for FSM :: current_state
Total Covered Percent
States 4 4 100.00
Transitions 8 6 75.00
States Line No. Covered
A 17 Covered
B 29 Covered
C 38 Covered
D 35 Covered
Transitions Line No. Covered
A$\rightarrow$A 17 Covered
A$\rightarrow$B 29 Covered
B$\rightarrow$A 17 Not Covered
B$\rightarrow$C 38 Covered
B$\rightarrow$D 35 Covered
C$\rightarrow$A 17 Not Covered
C$\rightarrow$D 44 Covered
D$\rightarrow$A 17 Covered
Figure 6: FSM coverage report template.

(a)

(b)

Figure 7: State transition diagram for FSM16.  TABLE I: Results on FSMs of
different complexity. All FSMs have natural-language prompts describing the
function. ”Iters” are the number of iterations required to achieve % Cov
(Coverage). ”State Regs”, ”I/O pairs” and ”Fuzzing” denote # input patterns
required to detect a mismatch from the specification by the three methods,
respectively. FSMs are arranged from 1–100. 50 FSMs are reported here, rest
are reported in Appendix A-A. (✓) denotes successful bug detection and (✗)
denotes failed attempt.

Level |  FSMs | Characteristics | LLM (and coverage)-guided Testbench Generation | LLM-guided Automated Bug Detection
---|---|---|---|---
GPT3.5 | GPT4 | GPT3.5+This Work | GPT4+This Work | GPT3.5 | GPT4 | GPT3.5+This Work | GPT4+This Work
i/o |  o/p |  states |  % Cov |  % Cov |  Iters |  % Cov |  Iters |  % Cov |  State Regs |  I/O pairs |  Fuzzing |  State Regs |  I/O pairs |  Fuzzing |  State Regs |  I/O pairs |  Fuzzing |  State Regs |  I/O pairs |  Fuzzing
Easy | 1 | 2 | 1 | 2 | 50 | 50 | 2 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
2 | 6 | 3 | 2 | 75 | 50 | 2 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
9 | 1 | 1 | 3 | 33 | 75 | 3 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
10 | 1 | 1 | 3 | 50 | 50 | 3 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
15 | 3 | 3 | 4 | 75 | 50 | 3 | 100 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
16 | 2 | 2 | 4 | 25 | 50 | 3 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
17 | 2 | 1 | 4 | 25 | 50 | 2 | 90 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
18 | 2 | 8 | 4 | 25 | 50 | 4 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
19 | 5 | 2 | 4 | 25 | 50 | 5 | 90 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
20 | 3 | 3 | 4 | 50 | 50 | 3 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
25 | 1 | 1 | 5 | 25 | 20 | 5 | 90 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
26 | 2 | 8 | 5 | 33 | 50 | 6 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
27 | 1 | 2 | 5 | 25 | 35 | 5 | 100 | 3 | 90 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
28 | 3 | 3 | 5 | 50 | 50 | 4 | 95 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
29 | 2 | 6 | 5 | 50 | 50 | 4 | 90 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
30 | 1 | 1 | 6 | 25 | 25 | 5 | 90 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
31 | 6 | 2 | 6 | 25 | 20 | 6 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
32 | 7 | 3 | 6 | 20 | 25 | 4 | 100 | 4 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
33 | 4 | 4 | 6 | 43 | 37 | 6 | 90 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
34 | 1 | 1 | 6 | 23 | 32 | 6 | 95 | 3 | 95 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
35 | 2 | 4 | 6 | 40 | 35 | 5 | 100 | 3 | 90 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
36 | 1 | 2 | 6 | 21 | 40 | 5 | 90 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
42 | 5 | 5 | 7 | 30 | 19 | 7 | 90 | 5 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
43 | 4 | 4 | 7 | 20 | 50 | 6 | 92 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Medium | 46 | 3 | 7 | 8 | 50 | 33 | 8 | 96 | 6 | 95 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
47 | 3 | 7 | 8 | 12 | 24 | 7 | 90 | 5 | 90 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
48 | 1 | 2 | 8 | 20 | 13 | 7 | 91 | 7 | 95 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
52 | 2 | 2 | 9 | 25 | 15 | 8 | 90 | 5 | 95 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
53 | 2 | 4 | 9 | 10 | 12 | 9 | 92 | 8 | 100 | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
54 | 1 | 1 | 9 | 19 | 33 | 7 | 95 | 6 | 92 | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
59 | 2 | 2 | 10 | 8 | 10 | 9 | 95 | 5 | 90 | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
60 | 1 | 3 | 10 | 11 | 15 | 8 | 100 | 8 | 100 | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
61 | 3 | 3 | 10 | 25 | 20 | 8 | 90 | 8 | 90 | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
62 | 2 | 1 | 10 | 15 | 12 | 8 | 100 | 8 | 100 | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
66 | 6 | 5 | 11 | 13 | 10 | 10 | 90 | 9 | 90 | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
67 | 1 | 1 | 11 | 7 | 11 | 9 | 92 | 9 | 95 | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
71 | 12 | 3 | 12 | 22 | 13 | 12 | 90 | 8 | 90 | ✗ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
72 | 2 | 1 | 12 | 13 | 12 | 9 | 94 | 9 | 95 | ✗ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
75 | 1 | 11 | 13 | 18 | 10 | 13 | 92 | 9 | 90 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
78 | 4 | 16 | 14 | 6 | 7 | 14 | 90 | 10 | 100 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Hard | 82 | 1 | 6 | 16 | 9 | 12 | 15 | 95 | 11 | 95 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓
85 | 1 | 1 | 19 | 7 | 5 | 18 | 91 | 13 | 93 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✓ | ✓
87 | 2 | 2 | 20 | 5 | 6 | 20 | 90 | 13 | 90 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
90 | 1 | 1 | 22 | 7 | 7 | 21 | 90 | 14 | 94 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
92 | 4 | 4 | 23 | 8 | 11 | 22 | 91 | 12 | 93 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
93 | 1 | 2 | 24 | 4 | 10 | 23 | 94 | 13 | 91 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
95 | 2 | 1 | 25 | 8 | 12 | 22 | 90 | 11 | 92 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
96 | 1 | 1 | 25 | 5 | 15 | 23 | 93 | 12 | 100 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
99 | 2 | 2 | 27 | 12 | 9 | 24 | 95 | 13 | 92 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
100 | 6 | 16 | 28 | 6 | 5 | 22 | 95 | 14 | 95 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓

###  IV-B Results: LLM-guided Testbench Generation

To understand the limitations of using LLMs, if any, we have first studied the
obtained testbenches in detail, providing the following important insights.
First, for certain paths and transitions selected for extended coverage, the
model may not be able to figure out the next correct input pattern to move to
the next state. For example, to cover all transitions in LABEL:fig:original
(state transition diagram for FSM16), i.e., A$\rightarrow$A, A$\rightarrow$B,
B$\rightarrow$C, B$\rightarrow$D, C$\rightarrow$D, C$\rightarrow$E,
E$\rightarrow$D, E$\rightarrow$E, D$\rightarrow$F, F$\rightarrow$C,
F$\rightarrow$D, and D$\rightarrow$A, we will require an input pattern that
begins with coverage of state A, like 1000010010101101…. This requirement was
not automatically understood/identified by GPTs, so the model could get stuck
at some state and repeat generating the same test patterns. Second, due to the
context limits of LLM for that matter, the model cannot cover all transitions
in one iteration. Thus, we prompt it to ‘reset’ after certain transitions such
that it can discover all input patterns up to some state transitions and
traverse the rest, as shown in Fig. 3.

Table I provides representative results for our method in Section III. As
indicated, further results are made available at [16]. Our dataset has {Easy,
Medium, Difficult} FSMs, based on their complexity in terms of the number of
states and the number of transitions (which is exponentially related to the
number of states). The dataset showcases the capabilities of LLMs and their
limitations (e.g., due to a lack of domain knowledge). First, we characterized
the FSMs based on the number of inputs (i/p), outputs (o/p), and states.
Iterations relate to our method explained in Section III; each iteration
involves running VCS and collecting key information, as highlighted in Fig. 6,
which includes the percentage of coverage and ’Not Covered’ transitions with
the current test cases. This information is used to provide more context for
the next prompt. Second, we report coverage with no feedback, where we
prompted {GPT3.5, GPT4} to generate a testbench with full coverage.
Correspondingly, {GPT3.5 + This Work, GPT4 + This Work} represents coverage
using feedback with our method. Varying the number of iterations is required
for testbench generation across FSMs. This is expected as the iterative
process depends on the number of states, transitions, and the type of
connections. Due to repetitive responses after some iterations and certain
transitions being very difficult for the LLMs to understand, our aim was to
reach as close to 100% coverage as possible. As shown in Table I, with our
feedback mechanism we were able to achieve that with both GPT3.5 and GPT4.
Still, the number of iterations required to achieve that is less for GPT4
versus GPT3.5, which is expected considering the capabilities of both models.
For example, for FSM16, without feedback, the coverage is 25% for both GPT3.5
and GPT4, whereas for our method it is 100% in both cases.

###  IV-C Results: LLM-guided Automatic Bug Detection

So far, we did not provide natural-language design specifications for any of
the FSMs. Next we investigate automatic comparison of the natural-language
specification against the generated test cases and simulation outputs. Such
capabilities are essential for bug detection. Consider the ‘buggy’ and
incorrect transition in FSM16 in LABEL:fig:bug that occured due to human
designer error.

As shown in Fig. 2, we provide the tool with the test patterns and the VCS
simulation outputs for each clock cycle. We prompt GPT(3.5/4) to
correspond/match these test results with the design specifications and to find
mismatches, if any. The mismatches are highlighted as potential bugs in the
FSM RTL. We compare three scenarios in Table I: (1) State Regs (Registers): We
provide all input patterns and state register values for each clock cycle; (2)
I/O pairs: We provide only iI?O pairs per clock cycle; (3) Fuzzing: We provide
random input patterns. For the Scenarios (1, 2), we applied our framework to
generate test patterns. Scenario (3) is a baseline non-AI approach akin to
hardware _fuzzing_.

Initial Findings: LLMs can help raise warnings for mismatches in an advanced
manner beyond traditional coverage.333100% transition coverage does not
guarantee bug detection. Consider ‘buggy’ transition in FSM16 in
LABEL:fig:bug. A test case reaches the incorrect transition but goes no
further and fails to find the bug. FSM output diverges only a few cycles
later. However, when using large testbenches, it can become difficult for the
model to follow up for longer sequences of input patterns. Looking at each
case in more detail for {GPT3.5, GPT4} in the Table I, we find that in
Scenario (1), providing the state registers value helps the LLM to correlate
with the design specification. That is, the model only needs to check for the
next state based on the input patterns, and any transitions that are not
mentioned/covered would raise a warning of a potential bug. For this scenario,
thus, we can detect incorrect transitions for a few of the Easy and Medium
level FSMs with a reasonable number of input patterns, but not for the Hard
FSMs. This is because of the inability of these models to comprehend a large
input context, with GPT4 performing better compared to GPT3.5. Scenario (2) is
challenging. We had to add some additional input patterns, thus leading to a
bigger output trace to be fed to these models. We observe a similar trend to
Scenario (1) across GPT3.5 and GPT4. Scenario (3), i.e., random test pattern
generation, performs similarly to the other 2 scenarios, because of the
mentioned limitation of these models.

Figure 8: # of input patterns for bug detection for 100 FSMs using fuzzing for
all methods from Table I. Results are arranged as regions of FSM complexity.
For missing points, respective methods could not detect the bug.

Analysis for Bug Detection: We explored other approaches to improve the
result, by adjusting the prompt as shown in Fig. 4. In one technique, instead
of feeding all input-output patterns, we divide them into smaller sets. This
is easier to handle but still allows the LLM to track the state reached at the
end of each set. The next iteration of our method proceeds from there. Another
technique applies to multi-bit inputs and outputs. Instead of considering all
output bits at once, we tackle them individually. That is, we provided all
input patterns for an output bit and repeated this for all outputs. The
rationale is to focus LLMs on manageable sub-circuits (output cones) rather
than “bombarding” them with all information. We provide the natural-language
description with each query to LLM, such that the model does not lose the
overall context. In Table I, the columns corresponding to {GPT3.5 + This Work,
GPT4 + This Work} reports our final results with all these prompting
techniques. With GPT3.5 and our method, we were able to detect the bug in all
of Easy and Medium FSMs across all the 3 scenarios and a few Hard FSMs for
Scenarios (1) and (3). GPT4 combined with our method can detect the bug in all
the 3 level of FSMs and for all scenarios. This shows the effectiveness of our
method to improve the performance of LLMs on this task. Fig. 8 shows the
scaling of input patterns required to detect bugs for the fuzzing approach for
all methods. Clearly, our method combined with GPT3.5 and GPT4 can detect bugs
with fewer patterns and with a higher success rate.

###  IV-D Detailed Case Studies using GPT4

####  IV-D1 FSM22

This FSM has one input, multiple outputs, and 6 states. For Scenarios (1) and
(2), with less number of patterns, it was easy for the model to analyze and
flag the mismatch between the generated output and the design specification.
For Scenario (3), we employ new prompts similar to those shown in Fig. 4. The
mismatch was detected with 64 patterns.

####  IV-D2 FSM34

has 2 inputs, 1 output, and 10 states. For Scenarios (1,2), we detected
incorrect transitions by accessing state register and I/O values,
respectively, for each clock cycle. For Scenario (3) using random patterns,
GPT4 could not comprehend the input sequences. We modified the prompt similar
to Fig. 4, i.e., we iteratively consider subsets of I/O pairs. We begin with
100 random patterns and run the simulator to collect related I/O pairs, which
are then fed to GPT4 in small chunks. GPT4 then detected a mismatch with
$\sim$89 patterns.

####  IV-D3 FSM42

This is a 1-bit input, 1-bit output, and 19 state FSM. For Scenarios (1) and
(2), 73 and 85 patterns, respectively were needed to detect the mismatch. For
Scenario (3), feeding all I/O pairs to GPT4 did not catch the bug. Thus, we
used the prompts from Fig. 4 and increased the random patterns to 200. A
mismatch was detected with $\sim$107 patterns.

####  IV-D4 FSM50

is complex, with multi-bit outputs and 28 states. Our approach of feeding all
the input-output pairs failed for all the cases. Instead, we collected 200
patterns for each case, where GPT4 still failed to comprehend the whole FSM.
We employed both prompt variations in Fig. 4. For Scenario (1), with $\sim$158
test patterns and full access to state register values. For Scenarios (2,3),
for this revised approach, GPT-4 detected the mismatch with $\sim$193 and
$\sim$181 test patterns, respectively.

##  V Conclusions: Key Challenges and Insights

Designs with a large number of states are challenging for LLMs to analyze all
possible transitions. Eventually, such cases lead to a repetition of
responses. Second, fine-tuning an LLM for this work’s scope is challenging as
testbenches depend on RTL codes. Testbenches should be accompanied by the
corresponding RTL, and such combined datasets are not available. From the
prior point, two further challenges follow. Even if we obtain such datasets,
labeling testbenches as ‘good’ versus ‘bad’ in terms of coverage is not easy,
at least not without thoroughly running the EDA tools on all designs in the
first place. Interdependency between regular RTL and testbenches may be
difficult to comprehend for the LLMs, given the syntactic differences in these
two types of HDL files.

To overcome the scalability challenge for the large numbers of states and
transitions, we prompt LLMs with phrases like “reset after X number of
transitions are covered”. The model can then start with a new context to
generate the remaining test patterns without getting stuck at some state.
Furthermore, without access to a golden testbench for few-shot learning, the
feedback from the EDA tools is important as such feedback in the prompt better
guide the model. That is, after achieving some coverage, prompts are modified
with phrases like “Keep the previous test cases but now focus more on the
transitions that are not covered yet”. Once we provide the underlying RTL, the
LLM can follow the context. The interdependency between testbenches and RTL is
better understood throughout the iterative process and evidenced through our
case study on bug detection. Prompts play a crucial role in the output
quality.

##  Appendix A Appendix

###  A-A Result II

Table II reports our results for the rest of the FSMs other than the one we
have mentioned in the Table I.

TABLE II: Remainder of the Result. See also Table I caption.

Level |  FSMs | Characteristics | LLM-guided Testbench Generation | LLM-guided Automated Bug Detection
---|---|---|---|---
GPT3.5 | GPT4 | GPT3.5+This Work | GPT4+This Work | GPT3.5 | GPT4 | GPT3.5+This Work | GPT4+This Work
i/o |  o/p |  states |  % Cov |  % Cov |  Iters |  % Cov |  Iters |  % Cov |  State Regs |  I/O pairs |  Fuzzing |  State Regs |  I/O pairs |  Fuzzing |  State Regs |  I/O pairs |  Fuzzing |  State Regs |  I/O pairs |  Fuzzing
Easy | 3 | 1 | 2 | 2 | 50 | 50 | 2 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
4 | 2 | 2 | 2 | 75 | 50 | 3 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
5 | 2 | 2 | 2 | 50 | 75 | 3 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
6 | 2 | 1 | 2 | 25 | 50 | 2 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
7 | 2 | 2 | 2 | 50 | 75 | 2 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
8 | 2 | 3 | 2 | 50 | 50 | 3 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
11 | 1 | 1 | 3 | 42 | 50 | 3 | 100 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
12 | 1 | 1 | 3 | 50 | 50 | 2 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
13 | 3 | 3 | 3 | 24 | 50 | 4 | 95 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
14 | 1 | 1 | 3 | 33 | 40 | 3 | 100 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
21 | 1 | 2 | 4 | 20 | 45 | 4 | 94 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
22 | 2 | 2 | 4 | 40 | 50 | 5 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
23 | 2 | 2 | 4 | 25 | 25 | 5 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
24 | 1 | 1 | 4 | 32 | 40 | 4 | 97 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
37 | 1 | 1 | 6 | 25 | 50 | 5 | 91 | 3 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
38 | 6 | 2 | 6 | 50 | 50 | 4 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
39 | 3 | 3 | 6 | 50 | 45 | 6 | 100 | 2 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
40 | 1 | 4 | 6 | 25 | 25 | 5 | 93 | 3 | 90 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
41 | 1 | 1 | 6 | 20 | 20 | 5 | 100 | 4 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
44 | 2 | 1 | 7 | 25 | 37 | 6 | 90 | 3 | 95 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
45 | 1 | 4 | 7 | 50 | 50 | 7 | 100 | 4 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Medium | 49 | 1 | 2 | 8 | 25 | 30 | 6 | 90 | 5 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
50 | 2 | 2 | 8 | 20 | 35 | 6 | 95 | 4 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
51 | 1 | 4 | 8 | 15 | 40 | 7 | 91 | 4 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
55 | 2 | 1 | 9 | 25 | 38 | 7 | 93 | 5 | 100 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
56 | 3 | 3 | 9 | 18 | 25 | 6 | 90 | 4 | 95 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
57 | 1 | 4 | 9 | 33 | 25 | 7 | 90 | 6 | 91 | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
58 | 1 | 1 | 9 | 12 | 18 | 5 | 94 | 5 | 95 | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
63 | 5 | 5 | 10 | 15 | 10 | 9 | 96 | 7 | 100 | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
64 | 1 | 1 | 10 | 20 | 45 | 8 | 90 | 5 | 100 | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
65 | 1 | 2 | 10 | 18 | 25 | 8 | 100 | 5 | 93 | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
68 | 2 | 1 | 11 | 10 | 15 | 9 | 100 | 6 | 96 | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
69 | 3 | 1 | 11 | 20 | 20 | 9 | 92 | 7 | 90 | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
70 | 1 | 1 | 11 | 25 | 20 | 8 | 98 | 6 | 100 | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
73 | 2 | 2 | 12 | 35 | 41 | 11 | 90 | 8 | 90 | ✗ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
74 | 3 | 1 | 12 | 17 | 15 | 10 | 95 | 7 | 95 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
76 | 4 | 3 | 13 | 9 | 18 | 11 | 90 | 9 | 90 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
77 | 3 | 3 | 13 | 11 | 10 | 10 | 75 | 8 | 90 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
79 | 1 | 1 | 14 | 25 | 22 | 11 | 91 | 9 | 92 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
80 | 1 | 2 | 14 | 32 | 10 | 12 | 90 | 9 | 100 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Hard | 81 | 1 | 1 | 15 | 13 | 16 | 14 | 100 | 10 | 95 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
83 | 2 | 2 | 17 | 11 | 17 | 16 | 90 | 12 | 96 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓
84 | 1 | 1 | 18 | 6 | 8 | 19 | 95 | 13 | 97 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✓ | ✓
86 | 1 | 2 | 19 | 8 | 5 | 20 | 92 | 13 | 91 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
88 | 1 | 1 | 20 | 9 | 6 | 21 | 91 | 14 | 92 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
89 | 1 | 1 | 21 | 5 | 9 | 21 | 93 | 12 | 95 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
91 | 3 | 3 | 22 | 10 | 11 | 23 | 90 | 12 | 90 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
94 | 1 | 1 | 24 | 4 | 13 | 24 | 96 | 13 | 100 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
97 | 1 | 1 | 26 | 8 | 6 | 23 | 90 | 14 | 90 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
98 | 1 | 1 | 26 | 7 | 3 | 22 | 90 | 14 | 95 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓

## References

  * [1] J. Takahashi _et al._ , “Testing for high assurance system by fsm,” _IEICE TRANSACTIONS on Information and Systems_ , vol. 86, no. 10, pp. 2114–2120, 2003.
  * [2] OpenAI, “GPT-4,” Mar. 2023. [Online]. Available: https://openai.com/research/gpt-4
  * [3] M. Liu _et al._ , “Verilogeval: Evaluating large language models for verilog code generation,” in _2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)_. IEEE, 2023, pp. 1–8.
  * [4] S. Thakur _et al._ , “Autochip: Automating hdl generation using llm feedback,” _arXiv preprint arXiv:2311.04887_ , 2023.
  * [5] Y. Lu _et al._ , “Rtllm: An open-source benchmark for design rtl generation with large language model,” in _2024 29th Asia and South Pacific Design Automation Conference (ASP-DAC)_. IEEE, 2024, pp. 722–727.
  * [6] S. Thakur _et al._ , “Verigen: A large language model for verilog code generation,” _ACM Transactions on Design Automation of Electronic Systems_ , 2023.
  * [7] R. Kande _et al._ , “Llm-assisted generation of hardware assertions,” _arXiv preprint arXiv:2306.14027_ , 2023.
  * [8] W. Fang _et al._ , “Assertllm: Generating and evaluating hardware verification assertions from design specifications via multi-llms,” _arXiv preprint arXiv:2402.00386_ , 2024.
  * [9] H. Wu _et al._ , “Chateda: A large language model powered autonomous agent for eda,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 2024.
  * [10] M. Liu _et al._ , “Chipnemo: Domain-adapted llms for chip design,” _arXiv preprint arXiv:2311.00176_ , 2023.
  * [11] R. Zhong _et al._ , “Llm4eda: Emerging progress in large language models for electronic design automation,” _arXiv preprint arXiv:2401.12224_ , 2023.
  * [12] J. Blocklove _et al._ , “Chip-chat: Challenges and opportunities in conversational hardware design,” in _2023 ACM/IEEE 5th Workshop on Machine Learning for CAD (MLCAD)_. IEEE, 2023, pp. 1–6.
  * [13] Y. Fu _et al._ , “Gpt4aigchip: Towards next-generation ai accelerator design automation via large language models,” in _2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)_. IEEE, 2023, pp. 1–9.
  * [14] K. Chang _et al._ , “Chipgpt: How far are we from natural language hardware design,” _arXiv preprint arXiv:2305.14019_ , 2023.
  * [15] “Problem sets - HDLBits,” 2023. [Online]. Available: https://hdlbits.01xz.net/wiki/Problem_sets
  * [16] Anon. (2024) LLM-Aided-Testbench-Generation-for-FSM. [Online]. Available: https://anonymous.4open.science/r/LLM-Aided-Testbench-Generation-for-FSM-802C/