>Number:         9651
>Category:       bin
>Synopsis:       unbalanced and inefficient draw algorithm in fish(6)
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    bin-bug-people (Utility Bug People)
>State:          open
>Class:          change-request
>Submitter-Id:   net
>Arrival-Date:   Tue Mar 21 16:09:01 2000
>Last-Modified:
>Originator:     John Darrow
>Organization:
	This was on my own time after hours, my employer had nothing to
	do with this :)
>Release:        all
>Environment:
System: NetBSD jdarrowpiii.wheaton.edu 1.4V NetBSD 1.4V (JDARROW) #0: Tue Mar 21 15:04:28 CST 2000 jdarrow@jdarrowpiii.wheaton.edu:/var/src/sys/arch/i386/compile/JDARROW i386


>Description:
	The card drawing algorithm in fish(6) is unbalanced and
	inefficient.  It picks a random rank, and then returns that rank
	if there are any cards of that rank left in the deck.  This means
	that, for example, if there are three 3's left, but only one 6,
	the routine has an equal chance of drawing either 3 or 6, rather than
	the "ideal card deck" 75% to 25% probability.  (It also may take a
	number of random guesses before it gets either 3 or 6, thus the
	inefficiency part...)

>How-To-Repeat:
	Get bored while waiting for a compile to complete, play fish for
	a while.  Decide to look at code for explanation of "The computer
	cheats only rarely." (see fish(6)).  Notice card drawing routine
	problems.
>Fix:
	This fix replaces the old routines with a standard pre-shuffled
	deck, using an equal-probability single-draw shuffle.

--- /var/src/games/fish/fish.c	Thu Sep 23 13:18:26 1999
+++ /var/src/games/fishy/fish.c	Tue Mar 21 18:05:48 2000
@@ -65,6 +65,7 @@
 #define	RANKS		13
 #define	HANDSIZE	7
 #define	CARDS		4
+#define	TOTCARDS	RANKS * CARDS
 
 #define	USER		1
 #define	COMPUTER	0
@@ -77,8 +78,9 @@
 #define	PRC(card)	(void)printf(" %s", cards[card])
 
 int promode;
-int asked[RANKS], comphand[RANKS], deck[RANKS];
+int asked[RANKS], comphand[RANKS], deck[TOTCARDS];
 int userasked[RANKS], userhand[RANKS];
+int curcard = TOTCARDS;
 
 void	chkwinner __P((int, const int *));
 int	compmove __P((void));
@@ -170,7 +172,7 @@
 			continue;
 		if (buf[0] == '\n') {
 			(void)printf("%d cards in my hand, %d in the pool.\n",
-			    countcards(comphand), countcards(deck));
+			    countcards(comphand), curcard);
 			(void)printf("My books:");
 			(void)countbooks(comphand);
 			continue;
@@ -270,9 +272,7 @@
 {
 	int card;
 
-	while (deck[card = nrandom(RANKS)] == 0);
-	++hand[card];
-	--deck[card];
+	++hand[card = deck[--curcard]];
 	if (player == USER || hand[card] == CARDS) {
 		printplayer(player);
 		(void)printf("drew %s", cards[card]);
@@ -423,19 +423,21 @@
 void
 init()
 {
-	int i, rank;
+	int i, j, temp;
 
-	for (i = 0; i < RANKS; ++i)
-		deck[i] = CARDS;
-	for (i = 0; i < HANDSIZE; ++i) {
-		while (!deck[rank = nrandom(RANKS)]);
-		++userhand[rank];
-		--deck[rank];
+	for (i = 0; i < TOTCARDS; ++i)
+		deck[i] = i % RANKS;
+	for (i = 0; i < TOTCARDS - 1; ++i) {
+		j = nrandom(TOTCARDS-i);
+		if (j == 0)
+			continue;
+		temp = deck[i];
+		deck[i] = deck[i+j];
+		deck[i+j] = temp;
 	}
 	for (i = 0; i < HANDSIZE; ++i) {
-		while (!deck[rank = nrandom(RANKS)]);
-		++comphand[rank];
-		--deck[rank];
+		++userhand[deck[--curcard]];
+		++comphand[deck[--curcard]];
 	}
 }
 
>Audit-Trail:
>Unformatted: