Squirrel Virtual Libraries

[Bilbo]

Well, that would be many times slower. Maybe 20 or more times. And the most important (for me) function exp(x) that you have posted work only for x being positive integer, which unfortunately useless for sigmoidal transfer function, as x gets there usually "somewhere between -1 and 1, occasionally higher or lower".

Well, if it won't be exported, I'll have to calculate exp(x) somehow else. Possibly using some precomputed tables, storing exp(x) for x from -10 to 10 in increments of 1.

Since e^(x+y)=e^x*e^y, you can lookup for nearest e^x in the table, then get remainder y, multiply it by 10, lookup again and divide the result by e^10. With reasonably large table (~200 entries) you can compute exp(x) with relatively good precision with just 4 or 5 lookups. But it will be still slower than just handing the task to the FPU :)

[Xander]

Surely it would make a lot more sense to write the "heavy" functions (like exp) in AI code - that way they only tie up the system for the standard AI time slot and never affect the user experience.

I do appreciate where you're coming from Bilbo - any mature intelligence is going to need to do a lot of sums but if your sums are so demanding they affect the users play experience the first thing they're going to do is make a stupid topic on the forums bitching and then they're going to turn your AI off when they're told that's the problem.

[Yexo]

Surely it would make a lot more sense to write the "heavy" functions (like exp) in AI code - that way they only tie up the system for the standard AI time slot and never affect the user experience.

No, that doesn't make sense, since AI code is a lot slower than c++ code.

I do appreciate where you're coming from Bilbo - any mature intelligence is going to need to do a lot of sums but if your sums are so demanding they affect the users play experience the first thing they're going to do is make a stupid topic on the forums bitching and then they're going to turn your AI off when they're told that's the problem.

I have no idea what point you're trying to make here.

[cirdan]

Well, if it won't be exported, I'll have to calculate exp(x) somehow else. Possibly using some precomputed tables, storing exp(x) for x from -10 to 10 in increments of 1.

If you want an efficient formula to compute exp(x), you should use its power series expansion, which is

Code: Select all

exp(x) = 1 + x + x^2/2 + x^3/6 + x^4/24 + ... + x^n/n! + ...

It converges extremely fast, particularly for values of x close to 0 (due to the mean value theorem and the fact that n! grows even faster than exp(n)). If you are interested in values of x for which |x| < 1, then the Taylor polynomial of order 4

Code: Select all

exp(x) ~ 1 + x + x^2/2 + x^3/6 + x^4/24

gives you an error of less than e/120; using order 5, the error is less than e/720, and so on (order n has error bound by e/(n+1)!). If your values were |x| < 1/2, errors would be considerably smaller. On the other hand, convergence when |x| > 1 can be slower at first; from what you say, this may not be a problem for you, but otherwise you can use e^{2x} = (e^x)^2. I'd suggest halving x until it is less than, say, 1/4, then using an appropriate polynomial, then squaring the result as many times as you halved it in the first place.

Of course, you should not use those polynomials directly, but instead use Ruffini's rule for efficient polynomial evaluation:

Code: Select all

1 + x + x^2/2 + x^3/6 + x^4/24 = 1 + x ( 1 + x ( 1/2 + x ( 1/6 + 1/24 x ) ) )

This gives you the result with n additions and n multiplications--no powers involved. This is true for any polynomial of degree n, and it is provably the most efficient way to evaluate any polynomial.

[AndersI]

Instead of using the mathematically correct infinite series expansion, you should decide your input range and acceptable error and compute 'optimized polynomials' for only that domain. For example, an acceptable sine() can be achieved with only three terms in the expansion (4 multiplications, 3 additions).

There's a bit (theory) about that (and other things) here: http://www.research.scea.com/research/p ... _GDC02.pdf - and in many other places too.

Then there's the old, proven, CORDIC concept but that's maybe not so well suited for OTTD-AI Sqirrel as it results in a larger number of simple operations (is the AI allotted actual time, a number of program lines, or a number of 'Squirrel primitive operations' in each 'time slice'?)

[cirdan]

Instead of using the mathematically correct infinite series expansion, you should decide your input range and acceptable error and compute 'optimized polynomials' for only that domain. For example, an acceptable sine() can be achieved with only three terms in the expansion (4 multiplications, 3 additions).

Err, that's exactly what I suggested, although perhaps I did not make it clear enough. In fact, I even gave some error estimations for the Taylor polynomials of orders 4 and 5. I mentioned the power series just because the previous suggestion had been to compute exp(x) as pow(e,x), and because all those 'optimised polynomials' are simply truncated versions of the infinite series.

[AndersI]

No, as far as I can see, you are talking about truncated Taylor series. By calculating optimal coefficients for the terms you include, you can get a better approximation with fewer terms, especially if you know you will be using a limited input range. Those coefficients will not be integers, as in your examples.

[cirdan]

Perhaps I'm just being thick, but 1/2, 1/6, 1/24... are not integers in my book...

And the Taylor polynomial method can't be that wrong if the MPFR library uses it.

[AndersI]

Sorry, I don't have any good links. The best I could find quickly is this discussion on Stackoverflow, http://stackoverflow.com/questions/3450 ... tions-work, I'm mostly thinking of Chebyshev polynomials, as Jason S (about at the middle of that page) is talking about. Some of his examples:

Code: Select all

[...sin and cos ...]

Range = -pi/2 to +pi/2, degree 5 (3 terms)

    * Taylor: max error around 4.5e-3, f(x) = x-x3/6+x5/120
    * Chebyshev: max error around 7e-5, f(x) = 0.9996949x-0.1656700x3+0.0075134x5

Range = -pi/2 to +pi/2, degree 7 (4 terms)

    * Taylor: max error around 1.5e-4, f(x) = x-x3/6+x5/120-x7/5040
    * Chebyshev: max error around 6e-7, f(x) = 0.99999660x-0.16664824x3+0.00830629x5-0.00018363x7

Range = -pi/4 to +pi/4, degree 3 (2 terms)

    * Taylor: max error around 2.5e-3, f(x) = x-x3/6
    * Chebyshev: max error around 1.5e-4, f(x) = 0.999x-0.1603x3

where you can see that by using Chebyshev (Minimax) polynomials, you can drop one term (or even two!) in the expansion and still have better accuracy than the Taylor expansion. I don't know if the same goes for the Exp() function, though - the most important thing for simplifying that is to reduce the range, I think.

[...some more searching...]

Ah, here's a textbook link that actually works: http://books.google.se/books?id=-rCodwZ ... t&resnum=2

It seems the Exp() function is well suited for Chebyshev approximation too.

[gaynorg]

Maybe we could throw these into a library as a stopgap until they include the ones from squirrel. Any takers ?

[Bilbo]

Perhaps it would be easier to create a patch that will add these functions instead of trying to create an approximative library...

[Zutty]

Perhaps it would be easier to create a patch that will add these functions instead of trying to create an approximative library...

Since 0.7.0 has only just gone out you're unlikely to get a patch in a release any time soon EVEN IF the OpenTTD devs like it. An AI that requires a patch isn't going to have very many followers and kinda defeats the point of NoAI.

[id10terror]

Bilbo, i'd just use the 'heavy' library for the moment, then when you have your ai to a point where it starts outperforming others but drags the performance of ottd down you will be in a good position to 'ask' for the math lib to be included. Even if you don't succeed with you request, people like a good ai and will ask why its so slow and then you'd be able to tell them why and further your case for inclusion.

[Dustin]

Perhaps it would be easier to create a patch that will add these functions instead of trying to create an approximative library...

Since 0.7.0 has only just gone out you're unlikely to get a patch in a release any time soon EVEN IF the OpenTTD devs like it. An AI that requires a patch isn't going to have very many followers and kinda defeats the point of NoAI.

I don't know about that. Being able to write a really cool NN AI, even if you are working off a private binary might be enough by itself. I know all the AI writers would probably want to check it out. And if we all though it was cool then we would recommend people get the patch and so on. In other words, if you write a killer app on a private patch, then the chances of talking the devs into taking the patch into main goes up.

I have toyed with the idea of farming off my pathfinding stuff to some sort of cloud computing. That would required a totally custom version of the game. But my pathfinder would be able to solve all the paths at once! (mmmm.)

In other news, I can promise that anyone can write an AI that will slow the game down noticeably right now. I have written some buggy loops that did just that. So having your AI impact the game isn't a really good reason to forbid any library calls. If your AI makes the game sluggish, no one will play with it.

-D