Re: Seeking an algorithm

On 25 Jun 2006 07:01:28 -0700, AaronJSherman@xxxxxxxxx wrote:


Thad Smith wrote:
AaronJSherman@xxxxxxxxx wrote:
I have a problem, and I'm not quite sure of the appropriate algorithm.

In your problem statement you said that each container has a list of
variables. I presume that the various colors listed in the example are
variables.

Correct.

"Each variable has a numerical value and an overall value". Is the
number listed for each color the "numerical value" or the "overall
value". If one, why isn't the other shown?

That was a mis-statement on my part. Each variable has a numerical
value. Each container has an overall value (the result of some function
that takes all variables in the container as parameters).

What I'd like to determine is a scaling factor for each variable to
determine its "cost" with respect to raising the overall value.

What is the criteria or significance of a scaling factor? of cost? of
color? of overall value? of containers?

I need to be able to say "given red=3, blue =2, what do I have to set
green to in order to have overall=4?" It's not quite an optimization
problem, as someone else stated. I don't, for example, want to answer
"in order to have overall as high as possible", but rather a specific
value.

The real-world problem that I'm working on is a game. In the game,
there are hundreds of arbitrary factors that can be applied, and a
"difficulty" of an opponent. The arbitrary factors are sometimes binary
and sometimes associated with an integer value. The difficulty is my
"overall" value from my example previously. There are hundreds of
examples of opponents, and each has a difficulty, but there is no
well-defined function for mapping a given factor or set of factors to a
difficulty. What I want to do is to be able to say, "factor x has a
cost, scaling it up or down will incur this cost by changing the
difficulty according to function f(x,...) where the rest of the factors
involved constitute the '...' paramters"

Without doing this, it is very difficult to create new opponents in an
automated version of the game.

Is this a pipe-dream? Would I have to write code that can essentially
guess, or is there some algorithmic technique to derive such complex
relationships?

The bad news is that given a finite set of points in a
multi-dimensional space then there are an infinite number of functions
that pass through all the points. If you want to find a single
solution then you have to assume the kind of function you want and
solve for that. One way to check your guess is to solve for a subset
of the points and then check your solution against the rest of your
full set.

The first thing to try would be a linear function of n variables,
where n is the number of colours:

overall = A * red + B * blue + C * green

With three colours you will need three points to determine the values
of A, B and C. Four colours need four points etc. Look up "Gaussian
Elimination" if you want to solve the equations automatically.

If your problem does not have a linear solution then the next thing to
look at is a polynomial in powers of the different variables, which
are more complex to solve. Best to try a linear solution first.

The major problem is likely to be that the function contains
non-linear elements like "if red > 7 then overall <- overall + 1"
which will throw off most of the standard purely mathematical ways to
find a solution. You may have to settle for an approximation to the
actual function.

Another alternative would be to disassemble the code and try to
determine the required function that way.


rossum


.

Relevant Pages

  • Re: Seeking an algorithm
    ... Each container has an overall value (the result of some function ... determine its "cost" with respect to raising the overall value. ... The real-world problem that I'm working on is a game. ... examples of opponents, and each has a difficulty, but there is no ...
    (comp.programming)
  • Re: Opinions needed.. restore or money pit
    ... Sounds like you want a new game. ... What is a SBM worth to you? ... getting it to play. ... Now I've got a great player that cost me $0 ...
    (rec.games.pinball)
  • Re: Dawn of War: Winter Assault
    ... It's clearly a deliberate cost minimisation measure at the ... the game over time. ... there already existing an original DoW Space ... with the expected and predictable expansion than it was ever intended ...
    (comp.sys.ibm.pc.games.strategic)
  • Re: Trib cans Get Fuzzy on Dec. 1
    ... loses a game it should have won. ... "What cost us the game? ... recruiting at a small, Division II engineering school (Colorado School ... But at least I got to write the word "bullshit" in the newspaper. ...
    (rec.arts.comics.strips)
  • Re: Is Microsoft dumping?
    ... > Microsoft Corp loses at least US$153 on each Xbox video-game ... > console it sells, based on just the cost of components and assembly, ... which has spent more than US$12 billion developing its game ... > machines, released the Xbox 360 on Tuesday, in time for the holiday ...
    (soc.culture.china)