Hi all, I'm developing a board game similar to Scrabble, but with mathematics operations. For example, a player can have these tokens: 1 3 6 + - = 2 He has to build a valid operation with them ( and using the tokens placed in the board ), for example '3-2=1'. Now I'm facing the AI of this game. My main concern about this is how to find valid operations in a fast way. Currently I have achieved this using brute force ( just using the tokens of the computer, ignoring the tokens placed on board ). I check for every combination of the tokens if the operation is a valid one. It works pretty well, but terribly slow ( of course ). I'm thinking to minimize the possibilities. The first thing I can think is that I know that two operators can't appear together ( like '1+*2' ), so I can cut down a lot of possibilities. However I feel that it won't be that fast ( maybe I'm wrong, but I'd like to ask here first ). I tried to google but I didn't found any topic on this or something similar. Does anyone knows if any work about this exists? Thanks a lot for your help. Carlos

The way you are doing it should be pretty darn quick.

In your game is there a lot more tokens than that or is it really something along the lines of 3 numbers and 2 operators?

If it isn't a huge amount of numbers and operators this should run really really fast.

If it is just that and running slow you should post your code, there's probably some very big optimizations waiting for you (:

Wow, quick response =)

Yes, sorry. I should say that I have to do the search with up to 10 tokens, and after that I have to add the tokens placed on board to the search.

Currently I'm using std::next_permutation, so my current code is just a 'while' with a call to this function =)

I can think on an example that I can't find a good solution. I have the next tokens:

1 2 4 5 + + 6 7 9 =

I think that if I do the search as I explained before, the program will be searching for operations that can't be correct. For example:

1 + 2 = 79 + 54
1 + 2 = 97 + 45
1 + 2 = 95 + 47
1 + 2 = 59 + 74
...

I'm really lost about this subject. I'm starting to think to create a separate thread to do the search so that the game doesn't hang up and don't break my head too much with this...

Thanks a lot for your help =)

Carlos

Just set some rules such as:

1. All should start with a number.
2. Then you need a operation token.
3. Then you need another number.
4. Then you need a operation token OR a "=" token.
5. Repeate 3. 4. untill a "=" Token
6. Then you need another number.

Now to reduce the results values:

1. Calculate the whole result and search for it ;D

With this you should have little problems with speed.

Edit: well, you posted while i was writting.. your problem seens a lot more problematic now ;D

a "One Digit Number" Plus a "One Digit Number" can result only in a "Two Digit Number" or a "One Digit Number". so:

1 + 2 = "One Digit Number" or "Two Digit Number"
then
1 + 2 = 3 + 5 (That is a "One or Two Digit Number" result) is OK
1 + 2 = 34 + 56 (That is a "Two or Three Digit Number" result) is NOT OK. even if both 1 + 2 and 34 + 56 shares the possibility of "Two Digit Number", 1 + 2 will at maximum give a result of 18 (in a 9 + 9 combination) and any 34 + 55 shall give at least 20 (in a 10 + 10 combination) so they not fit!

you can also when you try for 1+2 get the result of 3, and then try to make a "3" so you will always skip any combination that is bigger than 3!

[Edited by - Guedez on May 27, 2009 11:08:56 AM]

Hi Guedez,

Thanks for your suggestions =)

I didn't think about what you say, and it's quite interesting.

The problem I see is if I have the next operation, I don't know how the solution would fit:

9 + 9 = 3 * 7 - 3

I mean, ? + ? can't be more than 18, so I would see 3 * 7 as incorrect, but after that I can found a - 3, which gives me the correct result. I don't see how I could predict something like that.

Do you have any idea?

Carlos

Avaliable tokens: 9 9 + 3 7 * 3 =

|xxxxx| = xxxxx -> empty
|9 + 9| = xxxxx -> use first 3 tokens.
|18| = |3 * 3| -> too low, not avaliable increasing value tokens.
|18| = |3 * 7| -> too high
|18| = ||3 * 7| - 3| -> correct
18 = 3 * 7 - 3 -> correct

Avaliable tokens: 3 + - * 7 9 9 3

xxxxx = xxxxx -> empty
|3 + 7| = xxxxx -> use 3 first tokens.
|3 + 7| = |9 - 9| -> too low
|3 + 7| = |9 - |9 * 3|| -> |9 - 27| = 18 -> incorrect.

|7 + 9| = |3 - 9| -> too low
|7 + 9| = ||3 * 3| - 9| -> too low.
|7 + 9| = ||3 * 9| - 3| -> too low. -> incorrect.

|9 + 9| = |3 - 7| -> too low.
|9 + 9| = ||3 * 3| - 7| -> too low.
|9 + 9| = ||3 * 7| - 3| -> correct. << supose it was not like this.
18 = 18 -> correct

Suposition:
|9 + 9| = |3 - |3 * 7|| -> correct.
18 = 3 - 21 -> 18 = -18 -> reverse minus parameters.
|9 + 9| = ||3 * 7| - 3| -> correct
18 = 18 -> correct

something like this :D

Why not create a small grammar to help?

So, instead of blindingly trying all combinations you could simply recognise that each valid operator (+, -, *, /) requires two valid numbers on either side.

You can parse your set of tokens beforehand to identify the valid numbers and simply build the set of all operations using each permutation of 2 numbers on the available operators. You can reduce the generated operations by half in some cases by recognising that some operations are equivalent if the left and right numbers are reversed (+ and * in particular).

If you allow parentheses then you can use a recursive approach to generate the set of all valid parse trees based on the number of parenthesis and operators available.

Yes. In fact I ended doing it that way. It gave me very good results, but I'll work on a couple more of optimizations ( in terms of discarding possibilities ).

Thanks to all for your help =)

Carlos