Cards Monte-Carlo little problem but not in computer chess.

[Solitaireman]

What happens when you run out of cards in the deck but have dealt just 1 or 2? Do you get to place them if possible?

I'm not sure if i understand you correctly.
If in a round you have dealt only 1 or 2 then no problem, you continue normally by taking all the dealt cards and dealing them again 3 by 3 always.

Or do you ask if you have left with only 2 cards? That of course is not a problem. Since every card you deal(3-3 always) and has a suit, you place it and if the card below it that is being revealed has a suit too then you place it too, and if the card below it too has a suit then you place it too etc....

Or perhaps you are asking if you have left with 2 cards while you are dealing? I.e you dealt 3 by 3 all the cards and now in the last deal of the round you don't have 3 to deal but only 1 or 2. Well easy. If you have 2 you deal these 2, if you have one you deal the 1.

Please clarify if you don't mean that.

[Solitaireman]

If a card X is represented by a number from 0 to 51, then its suit is X&3 which returns a value from 0 to 3. For the rank, use X>>2 which returns a value from 0 to 12.

Thanks clever things. I will try to make them work.

[Solitaireman]

I see the heavy emphasis on "C code" but it really is trivial transforming the problem to C++. When you do that it's just a few lines of code to define the structure of the game. For example:

Code: Select all

struct Card {
    int number;
    int suit;
    int placement; // [0-51]
};
vector<struct Card> Deck(52);

or something like that


Using vectors, C++ would also allow you to shuffle or sort the deck with one line of code. After that, the elements of Deck could be accessed as if they were ordinary array elements (of structures), for example, Deck[3].number

King and Ace stacks would look something like: vector<Card> KingStack(4). For every third card, you would cycle through the top cards of all eight stacks to see if you can place them. You'd also need one more vector for holding the 3 cards that you flipped.

I hope that is helpful

It would be if i new C++. The emphasis on C is because i only know C and not that i hate C++ or something.

From what you are saying in C++ doing what i want would be extremely easy, so i guess i have to learn some C++, i think it's not that different to C so let's see.

But is C++ so much powerful to C that in C we can't solve this problem trivially while in C++ is so easy to do like you described?? I mean doesn't C have any easy way also?

[Solitaireman]

I am struggling to understand what you mean. In general, if the 'pack' is composed of N groups with {n1, n2, ..., nN} elements in each group then you will have a pack whose size is S = n1 * ... * nN. (In the cards case N=2, n1=4, n2=13, and S=52). Is that what you mean?

No, if i understood you correctly, no this is not what i mean.
Here is simply what i mean:
A deck contains 52 cards.

Each card holds 2 pieces of information:
1)A number from 1 to 13 for representing the rank(A,2,3,...,Q,K).
2)A number from 1 to 4 for representing the suit (♥,♦,♣,♠).

What i want is to have an object (i would like an array, e.g A[], to be able to do that but as it seems an array in C can only store one piece of information i.e a single number(ok we can do some tricks as i've said to make it hold via this single number, 2 numbers so 2 pieces of information but i don't like tricks and i want a general way)) that can store these 2 pieces of information.

So i would be able to compare them easily, for example if:
A[2]= 4♠ and A[45]= Q♥ with a representation of an 1x2 array like:
A[2] = [4,4] and A[45] = [12,1] i can easily see that A[2] and A[45] cards are not adjacent to each other(the one 4 and the other 5 for example nor have the same suit since the element (1,2) of their array is not the same).

While the A[2]= 4♠ and A[45]= 5♠ with a representation of an 1x2 array like:
A[2] = [4,4] and A[45] = [5,4] i can easily see that A[2] and A[45] cards
are adjacent to each other since 5-4=1(consecutive numbers) and 4-4=0(same suit).


So if cards would hold more information also like:
1)A number from 1 to 13 for representing the rank(A,2,3,...,Q,K).
2)A number from 1 to 4 for representing the suit (♥,♦,♣,♠).
3)A number from 0 to 30 for representing the temperature they have in degrees Celcius.
4)A number from 5 to 10 for representing the weight they have in grams.

So it would be handy if i could represent a card y with a 1x4 array of the kind: A[y] = [12,4,28,6] for saying that this card has the properties:
It's a Q♠ with 28 °C temperature and 6 grams weight.

In order to compare different cards.

[Don]

I whipped together a program to count how many of these are solvable.

With 1 million trials I get 22.691 % of them are solvable.

It's likely there are bugs in the program - hopefully someone else will verify this.

Can you share the program or you want to keep it private? It would be a good start for me to understand how it is done and apply it to other Solitaire games also.
Thanks.

I'll pm you on it. It's a quick hack and ugly code

[Don]

What happens when you run out of cards in the deck but have dealt just 1 or 2? Do you get to place them if possible?

I'm not sure if i understand you correctly.
If in a round you have dealt only 1 or 2 then no problem, you continue normally by taking all the dealt cards and dealing them again 3 by 3 always.

No, if you near the bottom and deal only 2 cards (instead of the required 3) do you get to see if the top card plays or is this forbidden because you didn't first lay off exactly 3 cards? But I think you answered my question.

Or do you ask if you have left with only 2 cards? That of course is not a problem. Since every card you deal(3-3 always) and has a suit, you place it and if the card below it that is being revealed has a suit too then you place it too, and if the card below it too has a suit then you place it too etc....

Or perhaps you are asking if you have left with 2 cards while you are dealing? I.e you dealt 3 by 3 all the cards and now in the last deal of the round you don't have 3 to deal but only 1 or 2. Well easy. If you have 2 you deal these 2, if you have one you deal the 1.

Please clarify if you don't mean that.

[gaard]

I see the heavy emphasis on "C code" but it really is trivial transforming the problem to C++. When you do that it's just a few lines of code to define the structure of the game. For example:

Code: Select all

struct Card {
    int number;
    int suit;
    int placement; // [0-51]
};
vector<struct Card> Deck(52);

or something like that


Using vectors, C++ would also allow you to shuffle or sort the deck with one line of code. After that, the elements of Deck could be accessed as if they were ordinary array elements (of structures), for example, Deck[3].number

King and Ace stacks would look something like: vector<Card> KingStack(4). For every third card, you would cycle through the top cards of all eight stacks to see if you can place them. You'd also need one more vector for holding the 3 cards that you flipped.

I hope that is helpful

It would be if i new C++. The emphasis on C is because i only know C and not that i hate C++ or something.

From what you are saying in C++ doing what i want would be extremely easy, so i guess i have to learn some C++, i think it's not that different to C so let's see.

But is C++ so much powerful to C that in C we can't solve this problem trivially while in C++ is so easy to do like you described?? I mean doesn't C have any easy way also?

Here is the quick-and-dirty C++ implementation. I ended up packing the Cards into unsigned ints, [0,51], using the lower 2 bits as the suit.

Code: Select all

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

int main()
{
	unsigned int KingStacks[4];
	unsigned int AceStacks[4]; 
	unsigned int card;
	
	vector<unsigned int> Hand;
	vector<unsigned int> Deck;
	
	int i; 
	int solved;
	int tried;
	int deck_size;
	bool play;
	
	for (tried=0, solved=0; ; tried++) {
		if (tried) 
			cout << solved << " of " << tried << endl;
		
		for (i=0; i<4; i++) {
			KingStacks[i]=12;
			AceStacks[i]=0;
		}
		
		// initialize deck
		Hand.clear();
		Deck.clear();
		for (i=0; i<52; i++) Deck.push_back(i);

		// shuffle
		random_shuffle(Deck.begin(), Deck.end());
		
		// cycle through deck 3 cards at a time
		play = false;
		while (true) {
			deck_size = Deck.size();
			
			for (i = 0; i < min(deck_size, 3); i++) {
				Hand.push_back(Deck.back());
				Deck.pop_back();
			}
			
			while (Hand.size() > 0) {
				card = Hand.back();
				if (AceStacks[card&3] == (card>>2)) {
					AceStacks[card&3]++;
					Hand.pop_back();
					play = true;
				}
				else if (KingStacks[card&3] == (card>>2)) {
					KingStacks[card&3]--;
					Hand.pop_back();
					play = true;
				}
				else break;
			}

			if (!Deck.size()) {
				if (!Hand.size()) {
					solved++;
					break;
				}
				if (play) {
					Deck = Hand;
					Hand.clear();
					reverse(Deck.begin(), Deck.end());
					play = false;
				}
				else break;
			}
		}
	}
}

Solves 22.85% of games, which is very close to Don's 22.691%. I am not quite sure if the difference is significant.

Using only C, you'd have to implement your own stack. It's not very difficult but it's a dozen or so lines of code that you don't have to write if you use the STL that comes with C++, with functions like pop_pack, push_back, random_shuffle, back, reverse, etc.

[Don]

I see the heavy emphasis on "C code" but it really is trivial transforming the problem to C++. When you do that it's just a few lines of code to define the structure of the game. For example:

Code: Select all

struct Card {
    int number;
    int suit;
    int placement; // [0-51]
};
vector<struct Card> Deck(52);

or something like that


Using vectors, C++ would also allow you to shuffle or sort the deck with one line of code. After that, the elements of Deck could be accessed as if they were ordinary array elements (of structures), for example, Deck[3].number

King and Ace stacks would look something like: vector<Card> KingStack(4). For every third card, you would cycle through the top cards of all eight stacks to see if you can place them. You'd also need one more vector for holding the 3 cards that you flipped.

I hope that is helpful

It would be if i new C++. The emphasis on C is because i only know C and not that i hate C++ or something.

From what you are saying in C++ doing what i want would be extremely easy, so i guess i have to learn some C++, i think it's not that different to C so let's see.

But is C++ so much powerful to C that in C we can't solve this problem trivially while in C++ is so easy to do like you described?? I mean doesn't C have any easy way also?

Here is the quick-and-dirty C++ implementation. I ended up packing the Cards into unsigned ints, [0,51], using the lower 2 bits as the suit.

Code: Select all

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

int main()
{
	unsigned int KingStacks[4];
	unsigned int AceStacks[4]; 
	unsigned int card;
	
	vector<unsigned int> Hand;
	vector<unsigned int> Deck;
	
	int i; 
	int solved;
	int tried;
	int deck_size;
	bool play;
	
	for (tried=0, solved=0; ; tried++) {
		if (tried) 
			cout << solved << " of " << tried << endl;
		
		for (i=0; i<4; i++) {
			KingStacks[i]=12;
			AceStacks[i]=0;
		}
		
		// initialize deck
		Hand.clear();
		Deck.clear();
		for (i=0; i<52; i++) Deck.push_back(i);

		// shuffle
		random_shuffle(Deck.begin(), Deck.end());
		
		// cycle through deck 3 cards at a time
		play = false;
		while (true) {
			deck_size = Deck.size();
			
			for (i = 0; i < min(deck_size, 3); i++) {
				Hand.push_back(Deck.back());
				Deck.pop_back();
			}
			
			while (Hand.size() > 0) {
				card = Hand.back();
				if (AceStacks[card&3] == (card>>2)) {
					AceStacks[card&3]++;
					Hand.pop_back();
					play = true;
				}
				else if (KingStacks[card&3] == (card>>2)) {
					KingStacks[card&3]--;
					Hand.pop_back();
					play = true;
				}
				else break;
			}

			if (!Deck.size()) {
				if (!Hand.size()) {
					solved++;
					break;
				}
				if (play) {
					Deck = Hand;
					Hand.clear();
					reverse(Deck.begin(), Deck.end());
					play = false;
				}
				else break;
			}
		}
	}
}

Solves 22.85% of games, which is very close to Don's 22.691%. I am not quite sure if the difference is significant.

I'm using the MT19937 RNG - sometimes that can be an issue. I did several runs and never got quite as high as your 22.85 percent. I looks slightly suspicious, I'll check for bugs in my implementation.

Using only C, you'd have to implement your own stack. It's not very difficult but it's a dozen or so lines of code that you don't have to write if you use the STL that comes with C++, with functions like pop_pack, push_back, random_shuffle, back, reverse, etc.

[gaard]

From 10,000,000 simulations I get 2,268,527 for 22.685%, very close to your 22.691%. From this sample, I'd chalk it up to random noise.

[Don]

From 10,000,000 simulations I get 2,268,527 for 22.685%, very close to your 22.691%. From this sample, I'd chalk it up to random noise.

Sounds good to me! Thanks for the double check (no pun intended.)