Shuffling a deck of cards in as few queries as possible

[Jessica]

I have a program which uses a deck of cards (not a standard deck of 52, more like the cards in a game like Dominion). Each card has a row in the DB, and a column for it's current deck_spot. When the card gets used, the deck_spot is set to 0. When the number of cards left in the deck (ie, have a spot > 0) is under a set point (4 for now), I need to shuffle the deck. I want to keep the remaining 3 cards in the "top" of the deck so they are used first, then the freshly shuffled deck is used, rather than the 3 being put in the shuffle. Here's what I have now.

 

function shuffleDeck(){
	//Get the cards which are still in the deck
	$sql = "SELECT user_sail_card_id FROM user_sail_cards WHERE deck_spot != 0 ORDER BY deck_spot ASC";
	$rows = $this->getRows($sql); //This gets an array of all the rows
	//Build an update statement to put the remaining cards in order.
	$update = "UPDATE user_sail_cards SET deck_spot = ( CASE ";
	foreach($rows AS $k=>$row){
		$update .= " WHEN user_sail_card_id = {$row['user_sail_card_id']} THEN ".($k+1);
	}
	$update .= " ELSE 0 END)  WHERE deck_spot != 0";
	$total_cards = $k+1;
	/*At this point update statement looks like:
	UPDATE user_sail_cards SET deck_spot = ( CASE  WHEN user_sail_card = 3 THEN 1 WHEN user_sail_card = 2 THEN 2 ELSE 0)
	*/

	//Update those cards, then select the cards which will be shuffled. 
	if(dbUp($update)){
		$sql = "SELECT user_sail_card_id FROM user_sail_cards WHERE deck_spot = 0 ORDER BY deck_spot ASC";
		$rows = $this->getRows($sql);
		//Shuffle the deck
		shuffle($rows);
		$update = "UPDATE user_sail_cards SET deck_spot = ( CASE ";
		foreach($rows AS $row){
			//Put these cards AFTER the other cards
			$update .= " WHEN user_sail_card_id = {$row['user_sail_card_id']} THEN ".($total_cards++); 
		}
		$update .= " ELSE 0 END)  WHERE deck_spot = 0";
		return dbUp($update);
	}
}

^{I'm using the ADODB library with a few custom wrapper functions.}

 

 

Is there a more efficient way to do this? Right now I'm making 4 queries to do it. I was hoping to do it in 1 or 2 if possible.

 

Edit: fixed typos.

[Barand]

I'd read he cards into an array and use the array in your program rather than repeatedly updating the DB table. Use array_slice() and shuffle to preserve the top 3 cards

[fenway]

Yeah -- do you really need to keep the state in the DB?

[Jessica]

Yeah -- do you really need to keep the state in the DB?

Yes, it's persistent.

[ignace]

Use a procedure/function to shuffle the cards for you in the DB. I don't see anything particular difficult in your function that may be hard to port to a procedure/function.

[Barand]

Yeah -- do you really need to keep the state in the DB?

Yes, it's persistent.

Implement a "Save game" function?

[Jessica]

Looks like I need to learn how to use procedures then

[gizmola]

I have to agree with the others, and from a relational design point of view, the shuffle state of the deck is not a direct attribute of the deck, so that should not be a column in the database.  To keep it in the database, you could have a "shuffledDeck" table that relates to the Deck table. 

 

If you have any concern about scalability, then you would probably want to investigate what all the cool kids are doing, which is something like Redis to maintain state.  Redis can be used to cache like memcache, but it also has a lot of extensions to it, and has a persistence mode that will save data to disk if you absolutely can't abide the infintessimal chance that your whole server shuts down and you might lose the state of the current games.  These scenarios are over thought a lot of times, because people never test them or come up with any code that would handle the recovery of a situation like that anyways.  Redis has some neat stuff in it like ZSCORE where you could use to represent your shuffled deck.  Items are placed in the cache key in sorted order and can be retrieved using ZRANGEBYSCORE in sorted order.

 

 

[Jessica]

To add more infomation, each player has their own deck of cards. They are playing against a computer, not another player, so they can leave an come back to their same game at any time.

Why is the spot in the deck not related to the User_card?

There's a cards table which holds all cards, then a user_cards which holds user id, card id and deck spot. What is wrong about that? They don't all have the same cards and can have multiples of a card.

If I don't store the new order in the db, how do I prevent someone from simply restarting until they get a shuffle they like?

User should have about 50 or more cards so the shuffle will happen for each user after they have played 50 cards.

[Jessica]

I was on my phone for that, decided it was too much work to keep typing on there

 

Anyway I think maybe the table structure wasn't clear, and the point of the game. it's sort of a mini-game within the game, and it's not something users can just quit the mini-game and start over, if they leave, when they come back their deck needs to be in the order they left it, so I feel like I need to store the state of their deck. Each player can have 0-many of any given card, and buy/sell cards (when they are NOT playing the mini game). The shuffle happens automatically when they are playing the mini game and the count of cards that have a deck_spot is < 4.

 

Tables:

sail_cards: sail_card_id, title, card_text, action, rarity, sail_card_type_id

user_sail_cards: user_sail_card_id, user_id, sail_card_id, deck_spot

 

If you guys still think I am going about it completely wrong with the new info, then I guess I am confused about how to do it at all I will look into Redis.

[gizmola]

To add more infomation, each player has their own deck of cards. They are playing against a computer, not another player, so they can leave an come back to their same game at any time.

Why is the spot in the deck not related to the User_card?

There's a cards table which holds all cards, then a user_cards which holds user id, card id and deck spot. What is wrong about that? They don't all have the same cards and can have multiples of a card.

If I don't store the new order in the db, how do I prevent someone from simply restarting until they get a shuffle they like?

User should have about 50 or more cards so the shuffle will happen for each user after they have played 50 cards.

 

Ok, that is equivalent to what I was thinking, so I retract my prior statement.  You could still do this in Redis, but if you want to stay with storing everything in mysql, then you are probably alright with your design.  I'm not a huge fan of stored procedures on mysql -- they were more of an afterthought and performance wise, aren't the major boon that they are in other relational databases.  In general mysql is optimized towards selects and inserts.  Updates and deletes are not as good. I would definately suggest you use the innodb engine for this application if for no other reason that at least you will have row level locking.

[Jessica]

Thanks, I double checked and I am already using innodb.

[Barand]

To shuffle, update a column with random values and select ordered by that column

[Jessica]

To shuffle, update a column with random values and select ordered by that column

How is that different than what I'm doing? Except that it could cause two cards to be at the same spot?