Squirrel Virtual Libraries

[gaynorg]

How do you get at them specifiacally the math

[Zutty]

What do you mean?

The NoAI libraries are all on the content service. There ARE no Squirrel libraries; its all in one API...

http://squirrel-lang.org/doc/squirrel2.html

You don't need to download or include anything.

[gaynorg]

these libraries
http://squirrel-lang.org/doc/sqstdlib2.html

Does it this allow you access the math functions

How ?

I've tried sqrt() it dosn't seem to work

[Zutty]

Oh I see. Not as far as I know. I think the OpenTTD devs would have to add them.

[Bilbo]

Hmm.... while some of these libraries should probably not be available (like the file I/O library, allowing AI's to mess with files on disk), I think the Math library should be exported completely to squirrel. The String library (manipulations with strings and regular expressions) could be perhaps also useful (maybe in Load() when parsing stuff created with Save()....) so I'd export it as well.

The rest of the libraries may be too dangerous to export.

I tried it and neither Math.sqrt(x), nor sqrt(x) works. So I think the libraries are not exported currently.

[Morloth]

The libraries are not included explicitly. The fear at the time (if I recall it correctly) is that sqrt operations require quite a substantial amount of CPU power to compute. The way Squirrel is integrated into the game now is by checking the amount of op codes squirrel performs and after X opcodes the Squirrel VM is put on hold while other AIs or the main game loop gets all the CPU power. The idea is that this way the AIs get enough CPU power to do the computations without slowing down the game to much. If sqrt operations are allowed these will be executed with a small number of opcodes (i.e. putting parameters on the stack and perform the sqrt function) while the actual time needed to computer the sqrt is not proportional to the number of opcodes required and if handled incorrectly could actually affect the user experience...

That's the story in a nutshell. Now on the actual subject, why do you need sqrt in the first place? Tiles are of the same hight, so just calculate the diagonal length offline and use it as a parameter in your program. All vehicles will follow these paths and will not 'cut corners' on tiles. So for calculations about path length, cargo income, etc. you won't need a sqrt function. Otherwise simply use the A^2 + B^2 = C^2 and don't apply the sqrt function if you want to compare distances between tiles.

Hope this helps .

[Yexo]

The speed is not really a issue, calling an api function can much more expensive then sqrt. The second point is the real reason: There should be no need to use sqrt at all.

[Bilbo]

The speed is not really a issue, calling an api function can much more expensive then sqrt. The second point is the real reason: There should be no need to use sqrt at all.

There is no way to compute sigmoidal transfer function without exp(x).
And you need this for neural networks for example... sqrt may be used to calculate euclidean distance for example (sqrt(x*x+y*y)). And these functions are not THAT expensive, they eat more than single CPU cycle, but unless you have really ancient computer, it is maybe 10 or 20 cycles at most. Most api calls are more expensive than that.

Once you want some smart AI that can learn from its mistakes, you WILL need some math functions. Not only neural networks need them, but other AI lerning methods need them too.

[Bilbo]

As for the instructions used by math functions - look at one of Intel's manuals:

http://download.intel.com/design/proces ... 248966.pdf - Page C-25

* Cost of fsqrt is exactly same as fdiv (about 40 ticks), therefore calling x=y/z costs the same amount of cpu cycles as x=sqrt(y) - note that integer division is also quite expensive, usually half of the floating point division cost.
* Multiplication is much faster (latency 8, throughput 2 ticks), addition is even cheaper.
* sin/cos/tan/exp cost between 100 and 300 cycles. While it is relatively expensive when compared to sqrt/division, it is still less than some more complex API calls.

Page C-26 lists the same for newer cores. The figures are lower, but the relative difference is same (tan/atan being the most expensive, about 10 times the cost of division/sqrt)

So unless you plan to forbid division with floating point parameters, I think adding "advanced" mathematical (sin/cos/exp....) functions won't do much harm and may actually help the AIs that needs them.

[Zutty]

There is no way to compute sigmoidal transfer function without exp(x).

So use a different transfer function! Given the number of neurons you'd need to make a workable NN that could play this game I'd say you'd be glad of a simple threshold function.

Frankly though I think this is just clutching at straws. No-one is ever going to make a NN-based AI for this game. It would be an enormous waste of time. A NN is a model for machine learning, so before you could even start you'd need some way to capture the way a human plays the game. Even if you managed to collect lots of training data though, there would be far better ways to model it IMHO.

[Yexo]

Well said Zutty. I still haven't seen compelling reasons to enable the squirrel standard libraries.

[Bilbo]

There is no way to compute sigmoidal transfer function without exp(x).

So use a different transfer function! Given the number of neurons you'd need to make a workable NN that could play this game I'd say you'd be glad of a simple threshold function.

Frankly though I think this is just clutching at straws. No-one is ever going to make a NN-based AI for this game. It would be an enormous waste of time. A NN is a model for machine learning, so before you could even start you'd need some way to capture the way a human plays the game. Even if you managed to collect lots of training data though, there would be far better ways to model it IMHO.

Yes. Machine learning. No need for human there, I plan to use it for profit estimation function.

Given variables:
* Distance between industries
* Speed of engine
* Power of engine
* Capacity of train
* "Mountainousness" of track between the industries
* Number of competitors trying to snatch goods from the same industry
* Cargo payment per unit (this will be tougher, at it is a function, but I think sampling it at 3 or 4 points may be enough)
* Some settings like cargo wieght multiplier

Estimate:
* Expected profit per month if the route would be built.

This is not calculatable, but with NN you can usually get better estimate than by trying to write some complex equation to calculate estimated profit.

And how to check how good was the estimate? Actually build the route and monitor the performance. Simple and it can be automated, so no need for human intervention :)

Training is quite slow, but once you have trained network, you can just use the resulting neuron weights and the evaluation is quite fast (maybe thousands of routes per second can be evaluated).

[Morloth]

I don't really think the calculation is *that* difficult. I'm not really sure about trains as i don't use them as of yet. But for all other types of transport this is quite easy to do. Like I said before all vehicles travel from the middle of one tile to the other so the distance can be calculated without resorting to sqrt functions.

What you do: plan the route of the connection, simulate driving your vehicles over this route and take care of all negative and positive effects (turning corners, climbing up hills, etc). So you get the travel time if we assume no down time. Add to this number the time it takes - on average - for a vehicle to get in positions to load / unload and the actual time it takes to load / unload. Now, I'm not aware how the reliability of a vehicle effects the over al travel time, but I'm sure this isn't anything complicated to take into account .

So I don't really see where the complexity comes from, the calculations I do (discounting vehicle breakdown) are quite accurate and don't need any fancy techniques like NN and I see little benefit for the overhead by introducing NN, but prove me wrong .

On a side not, my discussing about the 'it's to CPU expensive' was more for historical background. I think that's what TrueBrain gave as a reason for not including it, I'm well aware that Validate functions calls can be way more expensive .

Love to see some progress on your AI Bilbo, sounds rather promising.

[Bilbo]

I don't really think the calculation is *that* difficult. I'm not really sure about trains as i don't use them as of yet. But for all other types of transport this is quite easy to do. Like I said before all vehicles travel from the middle of one tile to the other so the distance can be calculated without resorting to sqrt functions.

What you do: plan the route of the connection, simulate driving your vehicles over this route and take care of all negative and positive effects (turning corners, climbing up hills, etc). So you get the travel time if we assume no down time. Add to this number the time it takes - on average - for a vehicle to get in positions to load / unload and the actual time it takes to load / unload. Now, I'm not aware how the reliability of a vehicle effects the over al travel time, but I'm sure this isn't anything complicated to take into account ;).

So I don't really see where the complexity comes from, the calculations I do (discounting vehicle breakdown) are quite accurate and don't need any fancy techniques like NN and I see little benefit for the overhead by introducing NN, but prove me wrong :).

On a side not, my discussing about the 'it's to CPU expensive' was more for historical background. I think that's what TrueBrain gave as a reason for not including it, I'm well aware that Validate functions calls can be way more expensive ;).

Hmm ... I forgot to take breaking down into account. Well, you can simplify the equation (from train parameters and parameters of track you can just compute quite good estimation of travel time), but one "uknown" still remains - the competition! You can't compute the competition behavior (extremely hard with other AI's, impossible with humans), so here you need some good estimate, telling you how many good will be taken by competitioon and how many will be left for you. That's the main thing where NN may be useful.

As for the "advanced math functions eat toop juch power" - sqrt cost szame number of CPU cycles as division. Other cost at most 8times the cost, so why just don't add 8 ops to the ops counter for AI when invoking one of these expensive functions?

Cheap ones (I suggest 1 op as it is now) for CPU: abs,ceil,fabs,floor,rand,sqrt,srand
Expensive (Suggested adding 5-8 ops): acos,asin,atan,atan2,cos,exp,log,log10,pow,sin,tan

The "cheap" ones are at most as expensive as simple floating point division in term of CPU cycles. The expensive are between 3 and 8 times the cost in terms of CPU cycles.

Love to see some progress on your AI Bilbo, sounds rather promising.

Currently the AI writing is often interrupted by me stumbling upon things not possible with the API calls (FS#2776) or things that are possible, but can be done more effectively (FS#2784 or the requet to get list of vehicles in rectangular area) and reporting them to the bug tracker or complaining here in NoAI Discussion.

[Yexo]

As for the "advanced math functions eat toop juch power" - sqrt cost szame number of CPU cycles as division. Other cost at most 8times the cost, so why just don't add 8 ops to the ops counter for AI when invoking one of these expensive functions?

Please see my reply above, the speed is not the issue.

Cheap ones (I suggest 1 op as it is now) for CPU: abs,ceil,fabs,floor,rand,sqrt,srand

abs is already available, floor is the same as converting to an integer, ceil = floor(val + 0.9999) (yes, not perfect, but should do for AIs), rand is already available in AIBase, sqrt won't happen (no need for it), srand won't happen (no need for it).

Expensive (Suggested adding 5-8 ops): acos,asin,atan,atan2,cos,exp,log,log10,pow,sin,tan

I see no use for any of these.

Currently the AI writing is often interrupted by me stumbling upon things not possible with the API calls (FS#2776)

As I said in my reply to that request, it may happen in the future, but it's difficulty to fit nicely in the current design.

or things that are possible, but can be done more effectively (FS#2784 or the requet to get list of vehicles in rectangular area)

That's just shifting the FOR_ALL_VEHICLES loop from your AI code to the API, so I see no use in adding an api function for that.

[Zutty]

It sounds interesting and I don't wish to discourage you, but honest to god I think you'd be better off using AICargo.GetCargoIncome() for this and focus your efforts elsewhere.

Presumably you want to use this to find the best service between two industries. A faster best-guess would allow you to explore more options in the same amount of time, which would probably end up yielding higher profits in the end.

[Bilbo]

sqrt won't happen (no need for it)

Someone already asked for sqrt, so I won't say "no need for it".

(FS#2784 or the requet to get list of vehicles in rectangular area)

That's just shifting the FOR_ALL_VEHICLES loop from your AI code to the API, so I see no use in adding an api function for that.

Actually... it is not just shifting, as the code have some hashtable to retrieve only vehicles actually visible in the viewport to speed drawing up. If the same hashtable is to be used for these requests, you can get your list of vehicles much faster than by looping over all vehicles (especially with large maps and many vehicles). I'd have to look closer at the code on how it is implemented to see if my request is actually possible, but I think it should be, at least within certain limits (the area to query not being larger than standard viewport seen by humans :)

[Bilbo]

It sounds interesting and I don't wish to discourage you, but honest to god I think you'd be better off using AICargo.GetCargoIncome() for this and focus your efforts elsewhere.

Presumably you want to use this to find the best service between two industries. A faster best-guess would allow you to explore more options in the same amount of time, which would probably end up yielding higher profits in the end.

Trained NN is pretty fast. And for simple tasks (estimating profit given few input variables) some simple NN is enough.

Also, while there are other transfer functions that do not need exp(x), the sigmoidal is usually the best performing one.

[gaynorg]

Look i think having these functions available is no harm. if people want to make use of any of these for experimenting with statistics, neural networking,modeling or whatever then they should be able to. if it makes their ai slower then it will be reflected in the performance. is it that much work to include the squirrel bundled libraries ? if its anything like c++ or java then it shouldn't be too bad but obviously i don't know.

[Zutty]

You can just write this stuff yourself if you really want it...

Code: Select all

/*
 * Square root using Newton's iteration. Got this from codecodex.com.
 */
function sqrt(num) {
    if (0 == num) {
    	return 0;
    }
    
    local n = (num / 2) + 1;
    local n1 = (n + (num / n)) / 2;
    
    while (n1 < n) {
		n = n1;
		n1 = (n + (num / n)) / 2;
    }
    
    return n;
}

/*
 * Iterative power.
 */
function pow(num, x) {
	local n = 1;

	for(local i = 0; i < x; i++) {
		n *= num;
	}

	return n;
}

/*
 * Recursive power.
 */
function pow(num, x) {
	return (x == 0) ? 1 : num * pow(x - 1);
}

/*
 * Exponential function
 */
function exp(x) {
	return pow(2.71828183, x);
}

/*
 * Taylor series approximation of sine. Works between -π and +π, which is all you need.
 */
function sin(x) {
	return x - (pow(x, 3) / fac(3)) + (pow(x, 5) / fac(5)) - (pow(x, 7) / fac(7));
}

/*
 * Taylor series approximation of cosine. Works between -π and +π, which is all you need.
 */
function cos(x) {
	return x - (pow(x, 2) / fac(2)) + (pow(x, 4) / fac(4)) - (pow(x, 6) / fac(6));
}

/*
 * Taylor series approximation of natural logarithm. Only works up to 1.
 */
function ln(x) {
	return (x - 1) - (pow(x - 1, 2) / 2) + (pow(x - 1, 3) / 3) - (pow(x - 1, 4) / 4) + (pow(x - 1, 5) / 5);// etc...
}

/*
 * Factorial (for taylor series stuff)
 */
function fac(n) {
	return (n <= 1) ? 1 : n * fac(n - 1); 
}

The log function could be improved, but I'm sure theres something out there somewhere.

Maybe these imlementations wont be as fast as one exposed by the Squirrel libraries, but they'll work. You can worry too much about performance IMHO.