Looking at the card game thread I remembered about a card game I was making a looooong time ago, and I needed to check all possible ways to play a hand. At the time, I was programming in a 386 with Clipper :rolleyes:, and the combinations were too many for the 386 (and Clipper :) ) (13!, the factorial of 13 = 6,227,020,800). Anyway, at the time I came up with an algorithm that would take two parameters, an array and a number n (0 <= n < factorial (len (array)), and would return in another array the nth combination of the array's elements.
I looked again at this algo and converted it to assembly, and it seems that 13! is still too much... The speed-limiting part of the algo is the following:
Let's say, for example, that we have an original array of 4 letters:


A B C D

Now, I want to fill another array with another arrangement of these letters. My algo comes to a point where I have 4 numbers, like this:


1 2 1 0

These numbers represent the FREE position of the result array that each letter will go. Since the first number is 1, and assuming we start from 0, the letter A will go to the 2nd FREE position of the new array:


A
- - - -

The second number is 2, so letter B will go to the 3rd FREE position of the new aray:


A B
- - - -

The 3rd number is 1, so letter C will go to the 2nd FREE position:


A C B
- - - -

The last number is always 0 (since at the end there is only 1 free position), so the result aray will finally look like this:


D A C B
- - - -


I currently fill the result array with an empty-indicating value, and then I search for the appropriate empty place. Since this involves memory access, slows down my algo. So, I thought someone might know how to convert these numbers that indicate the FREE position to FIXED array positions without scanning the array (I am trying, but haven't managed it yet :( ) Another idea would be to use a couple of registers as a map of the array, but I have to think it better...
Also, someone may already have a very fast algo for returning all possible combinations of an array's elements.
If I don't find a solution to this problem, I'll post the algorithm "as is" in a few days...
Posted on 2002-03-22 02:19:55 by micmic
Damn, you lost me when you were explaining which number goes with which letter goes with which position....
Posted on 2002-03-22 05:18:29 by sluggy
Afternoon, micmic.

You've totally lost me:confused:.
I needed to check all possible ways to play a hand

ummm. What have those arrays got to do with finding out which card to play from a hand?

Cheers,
Scronty
Posted on 2002-03-22 05:43:59 by Scronty
I guess I didn't describe it well...
Well, I'm trying to optimize an algorithm that returns all possible combinations of an array's elements. It could have a lot of applications, I originally used it in a card game. My cards were represented by an array, like 1, 33, 12, 51... Each number was a card, for example 1 was the Ace of Hearts, 13 was the King of Hearts, and so on. The player played the cards in the order they appeared in the array. If you were playing a bridge game against AI, you may ask what would be the absolutely best way to play my 13 cards ? In order to find this, you should rearrange the array of your cards in every possible way, and then simulate a bridge game for every combination. This is just an example, there are a lot of applications that could use such an algo.

My previous post explains just a problem I encountered while trying to optimize my algo, I'll try to explain it again:
I have to place A, B, C, D in an array. But where ? The positions are given by the numbers 1, 2, 1, 0. The problem is that these numbers indicate FREE positions in the array, and I want to have the ABSOLUTE positions, but without scanning the array (because memory access is slow)
In the previous example, the absolute positions are 1, 3, 2, 0, so if we have an array of bytes, I would store the letters like this:
mov eax, offset Array
mov byte ptr , 'A'
mov byte ptr , 'B'
mov byte ptr , 'C'
mov byte ptr , 'D'

The array may be of any length I just used 4 letters as an example, so I need a general way of doing it...
I know I'll get to it, as soon as there are no women around to distract me :)
Posted on 2002-03-22 06:32:36 by micmic
If you sort the hand that should limit the way the hand matches. I think making the bottom two bits indicate the suit (hearts, spades, clubs, diamonds) would work better as well - because usually there are two classes of hands - those that match a suit and those that don't. For those that don't, you could just mask off the suit bits, and compared against the sorted data. This will be very fast. :)
Posted on 2002-03-22 10:05:55 by bitRAKE
If you sort the hand that should limit the way the hand matches

Correct, the Bridge example was not very good. But there are lots of other card games where suit is irrelevant when you play a card, but has a meaning in scoring... or other games where suit has a completely different meaning... There are a lot of strange card games (Truco, Klaverjassen, Skat...). In every case, you can probably develop an algorithm that will be faster than a generic one. But my purpose is to create a generic algorithm, that will be useful for more things. Another game comes to mind: This was a very old TV game here in Greece (some decades ago...): Players were presented with 6 numbers (1-99) and they should use all of them (but only once each) to get as close as possible to another number (1-999). All 4 operations (+, -, *, /) are allowed, as long as all intermediate results are integers. I think you need an algo that returns all possible combinations of these 6 numbers if you want to create a program that finds the best possible solution.
Posted on 2002-03-22 12:48:26 by micmic
This reminds me of a hashing problem.

Try this:

If number of slots is odd
for all slots, 0<=x<n
for all slots, 0<=y<n
for all slots, 0<=z<n
A = S[(x+y*z) mod n]
?else number of slots is even
? for all slots, 0<=x<n
? for n-1 slots, 0<=y<n, y!=x
? for n-1 slots, 0<=z<n, z!=x
? A = S[(x+y*z) mod n]

Well it is close, Let's say that we want

n = 5

A[1][2][0] = S[(1+2*0) mod 5] = S[1]
A[1][2][1] = S[(1+2*1) mod 5] = S[3]
A[1][2][2] = S[(1+2*2) mod 5] = S[0]
A[1][2][3] = S[(1+2*3) mod 5] = S[2]
A[1][2][4] = S[(1+2*4) mod 5] = S[4]
Posted on 2002-03-22 13:11:11 by bdjames
This reminds me of a hashing problem

This is relevant to the way I calculate the "free positions" numbers, but I'm afraid it won't help with the particular problem...
Shouldn't it be A = S[(x*y+z) mod n] instead ?
Posted on 2002-03-22 13:57:43 by micmic
IMO, an optimized general solution would require an additional level of abstraction that processes the rules for the particular game. General solutions have large search spaces - you need a way to break down that space based on the rules of the game. :)
Posted on 2002-03-22 14:07:18 by bitRAKE
Not really,

void test(&int);

int main(){
int S[] = {1, 2, 3, 4, 5};
int n = 5;
int a;
for(int x = 0, x<n, x++)
for(int y = 0, y<n, y++)
for(int z = 0, z<n, z++)
a = S[(x+y*z) mod n];
for(int x = 0, x<n, x++)
for(int y = 0, y<n, y++)
test(a); <**************
}
Posted on 2002-03-22 14:26:59 by bdjames