wump: incorrect wumpus movement probability

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

wump: incorrect wumpus movement probability

David Fifield
The computation of wumpus movement probability in games/wump/wump.c has
a parenthesis problem that causes it not to work the way it evidently is
meant to. It raises this warning in gcc 8.2.0 with -Wall:
        warning: ?: using integer constants in boolean context [-Wint-in-bool-context]
           if (arc4random_uniform(level) == EASY ?
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
               12 : 9 < (lastchance += 2)) {
               ~~~^~~~~~~~~~~~~~~~~~~~~~~

This is the body of the condition:
        arc4random_uniform(level) == EASY ? 12 : 9 < (lastchance += 2)
It is probably meant to be this instead:
        arc4random_uniform(level == EASY ? 12 : 9) < (lastchance += 2)
i.e., choose a random number in the range [0, 12) or [0, 9) depending on
whether level is EASY or HARD, and bump lastchance unconditionally.

As currently written, when level == EASY (1), the code reduces to
        9 < (lastchance += 2)
And when level == HARD (2), it reduces to
        (arc4random_uniform(2) == 1) || (9 < (lastchance += 2))
Short-circuiting means that lastchance is bumped only half the time.

These are the probability distributions that are probably intended for
each value of lastchance, judging by the comment "each time you shoot,
it's more likely the wumpus moves":
  - don't move, bump lastchance
  + move, bump lastchance
  # move, don't bump lastchance
    EASY                                      HARD
 2  ++++++++++++------------------------   2  ++++++++++++++++--------------------
 4  ++++++++++++++++++------------------   4  ++++++++++++++++++++++++------------
 6  ++++++++++++++++++++++++------------   6  ++++++++++++++++++++++++++++++++----
 8  ++++++++++++++++++++++++++++++------   8  ++++++++++++++++++++++++++++++++++++
10+ ++++++++++++++++++++++++++++++++++++  10+ ++++++++++++++++++++++++++++++++++++

And these are the distributions the code produces currently:
  - don't move, bump lastchance
  + move, bump lastchance
  # move, don't bump lastchance
    EASY                                      HARD
 2  ------------------------------------   2  ##################------------------
 4  ------------------------------------   4  ##################------------------
 6  ------------------------------------   6  ##################------------------
 8  ++++++++++++++++++++++++++++++++++++   8  ##################++++++++++++++++++
10+ ++++++++++++++++++++++++++++++++++++  10+ ##################++++++++++++++++++

The following patch makes the code match its evident intent, and moves
the side effect on lastchance out of the conditional.

Index: wump.c
===================================================================
RCS file: /cvs/src/games/wump/wump.c,v
retrieving revision 1.33
diff -u -p -u -r1.33 wump.c
--- wump.c 7 Mar 2016 12:07:57 -0000 1.33
+++ wump.c 20 Dec 2018 07:00:13 -0000
@@ -535,8 +535,8 @@ into room %d!\n", arrow_location, next,
  /* each time you shoot, it's more likely the wumpus moves */
  static int lastchance = 2;
 
- if (arc4random_uniform(level) == EASY ?
-    12 : 9 < (lastchance += 2)) {
+ lastchance += 2;
+ if (arc4random_uniform(level == EASY ? 12 : 9) < lastchance) {
  move_wump();
  if (wumpus_loc == player_loc) {
  wump_walk_kill();

I traced the logic error back to a rewrite in 1990:
https://github.com/dspinellis/unix-history-repo/commit/3aa00eb936d97f768fbe9965912e19e348573181#diff-409a29a394ee2c20f1e62433b44d1b4aR447
The version it replaced was from 1982. That version had a fixed 75%
(NTUNN/(NTUNN+1)) movement probability.
https://github.com/dspinellis/unix-history-repo/commit/3481c4a066f9ca0a3f89ff484e47688b31d5e146#diff-409a29a394ee2c20f1e62433b44d1b4aR276

Reply | Threaded
Open this post in threaded view
|

Re: wump: incorrect wumpus movement probability

Ingo Schwarze
Hi David,

thanks for the extensive analysis, explanation, and research
and for the patch.  It is now committed.

Yours,
  Ingo



CVSROOT: /cvs
Module name: src
Changes by: [hidden email] 2018/12/20 02:55:44

Modified files:
        games/wump     : wump.c

Log message:
Move a badly positioned parenthesis that caused nonsensical movement
properties for the Wumpus.  The bug has been present since 4.3BSD-Reno
and was introduced by Keith Bostic on February 14, 1990 when committing
the major rewrite from Dave Taylor.

Patch (accompanied by a detailed functional and historical analysis)
from David Fifield <david at bamsoftware dot com> on bugs@.

With all the bats in these caves, how could a bug possibly survive
for twenty-eight years?



David Fifield wrote on Thu, Dec 20, 2018 at 12:11:25AM -0700:

> Index: wump.c
> ===================================================================
> RCS file: /cvs/src/games/wump/wump.c,v
> retrieving revision 1.33
> diff -u -p -u -r1.33 wump.c
> --- wump.c 7 Mar 2016 12:07:57 -0000 1.33
> +++ wump.c 20 Dec 2018 07:00:13 -0000
> @@ -535,8 +535,8 @@ into room %d!\n", arrow_location, next,
>   /* each time you shoot, it's more likely the wumpus moves */
>   static int lastchance = 2;
>  
> - if (arc4random_uniform(level) == EASY ?
> -    12 : 9 < (lastchance += 2)) {
> + lastchance += 2;
> + if (arc4random_uniform(level == EASY ? 12 : 9) < lastchance) {
>   move_wump();
>   if (wumpus_loc == player_loc) {
>   wump_walk_kill();