My take on the reproducibility of academic papers

In these days I am reviewing CIG papers. At the moment, I am not active in academia, but I enjoy being around in the community. Even if only with this “simple” tasks.

This, however, makes me think about the state of scientific work in academia. At least in the computer science field. Something bothered me during my Ph.D. and I am sure it is related to that. (Note: I am talking about what I know, that is, the computer science and AI community) In general, researchers are evaluated on the number of publications. The number of publications is a proxy variable for measuring “quality”. Unfortunately, researchers know that and started to game the system. They try to publish more and to do that they need to lower the “quality” of their work. Because the medium used to communicate your work is a plain PFD file, the obvious way to cut work is to cut the implementation part.

Continue reading “My take on the reproducibility of academic papers”

[Link] Go: the Good, the Bad and the Ugly

My opinion is that talking about languages is usually a very unproductive use of time. If these discussions are just cat fights, then it is even worse. Unless you are a language designer, you are writing a language or study a language, you should just use a language and nobody should care.

But good articles on language pro and cons are always nice. They may be helpful to choose the right tool for the problem. For this reason I link a good article on Go. And that’s the last time I’ll talk about Go.

Go: the Good, the Bad and the Ugly by Sylvain Wallez

Game Design: Taxonomy of Fishing Mini-games

Fishing is probably the most common mini-game in gaming history. Before I started working on this article,  I never realized how many games include a fishing as mini-game. The list is huge. Fishing is everywhere. It seems that it is not possible to have a game without the possibility for character to have a relaxing time fishing in a pond.

Everybody loves fishing! At least in games. We can imagine a deep reason for that. There must be something that attract designers, gamers and human in general to the ancient art of fishing. However, for the time being, we are not interested in this question. Instead, we want to explore the huge design space of “fishing games”.

In fact, the action of fishing has been dissected for decades by game designer. It is fascinating to see how many implementations exist for the same real-life action. So, it is time to see what they produced, what are the possibilities and how we can do something new in this domain.

Continue reading “Game Design: Taxonomy of Fishing Mini-games”

The State of Game Development in Rust

Game Development is one of the fields in which Rust can gain a lot of traction. As a modern compiled language with performances comparable to C++, Rust can finally free us from the tyranny of C++ bloated feature set, hard-to-link dependencies, and header/implementation file double-madness (I am obviously exaggerating, btw).

However, if this freedom arrive, it will be a very slow process. To make it slower, the feature of memory safety in videogames is not a huge priority compared to the ability to quickly prototype. The borrow-checker and the strict compiler are an obstacle in this regard. On the other hand, memory safety also means easier multi-threading. And this is sweet!

Fortunately, the annoyances of borrow-checker will get less in the way while people becomes more confident with the language, and while tooling gets better and better. I am confident we may see Rust carve out its space in this domain.

But this is the future. What about now?

Continue reading “The State of Game Development in Rust”

MovingAI pathfinding benchmark parser in Rust

You know I worked a lot with pathfinding. In academia, the MovingAI benchmark created by the MovingAI Lab of the University of Denver is a must for benchmarking pathfinding algorithms. It includes synthetic maps and maps from commercial videogames.

Parsing the benchmark data, the maps, creating the map data structure and more, is one of the most boring thing I needed to do for testing my algorithms. For this reason, I think a common library for working with the maps specifications it is a must.

For this, and because I enjoy a lot coding in Rust, I did a MovingAI map parser for rust.

Repository is here. The library is also on crates.io. It is still unstable because I want to be sure that the public AI is consistent with the requirements. I also not very solid on the needs of Rust APIs. So, I welcome some help here. :)

Example

However, look how it is convenient for writing pathfinding algorithms! All the important stuff (neighbors, map, and so on) are just out of the box. This is an A* algorithm I wrote in literally 5 minutes.

// A* shortest path algorithm.

fn shortest_path(map: &MovingAiMap, start: Coords2D, goal: Coords2D) -> Option<f64> {

    let mut heap = BinaryHeap::new();
    let mut visited = Vec::<Coords2D>::new();

    heap.push(SearchNode { f: 0.0, g:0.0, h: distance(start, goal), current: start });

    while let Some(SearchNode { f: _f, g, h: _h, current }) = heap.pop() {

        if current == goal { return Some(g); }

        if visited.contains(&current) {
            continue;
        }

        visited.push(current);

        for neigh in map.neighbors(current) {
            let new_h = distance(neigh, goal);
            let i = distance(neigh, current);
            let next = SearchNode { f: g+i+new_h, g: g+i, h: new_h, current: neigh };
            heap.push(next);
        }
    }

    // Goal not reachable
    None
}

 

GameDesign Math: RPG Level-based Progression

Level-based progression is an extremely popular way of providing the player with the feeling of “getting stronger”. The system is born with Role-Playing Games (RPG), but it is nowadays embedded in practically every game; some more, some less. Even if it is perfectly possible to provide progression feeling without levels and experience points, level-based progression is easy, direct, linear and fits well in many (too many?) game genres.

But designing a good experience-level progression is important. Many games do that without much thinking. They just slap experience points and level and that’s it. The general idea is that the more your level is big, the more experience you need to advance. This is true, but it is just a small part of the design. Because in game design, you must keep in mind the effect of your gameplay element on the player and must be useful to convey the emotion you want to convey. Not the other way around.

I cannot give a full analysis of level-based progression system, but I can use simple math to explore the effects, limits and the design space of it.

Why using a level-based progression system?

Judging from the amount of games that have a level-based progression system in place, the real question is “why not?”.  However, whenever we see something extremely successful we should ask ourselves why it is so popular.

The reason is: to give the player a sense of progression. Players want to see that they are getting stronger. And there is no better way than see “numbers getting bigger”: levels, damage, HPs. The player has spent hours playing to become powerful and these big numbers are here to prove it!

In many games, our skill is cannot be directly measured. Sure, we can feel this warm sense of progression in Super Mario Bros when we go back to the first level and we can go blazing fast. But this is nothing respect to the feeling of going back to the starting place and dealing ONE MILLION DAMAGE to that level 1 monster that gave us so many troubles.

Flow is the core concept of game design. You need to keep your player in the flow balancing difficulty. Levels and experience point are a great way to do this (sometime, a lazy way).

But there is also another reason designers like to introduce levels in their game. They are a handy way for the designers to control the flow of the game. And they offer to the player a clear indicator of this too. Nothing stops a player from rushing through the game like slamming a monster several levels higher than the player on the player’s way. This kind of artificial difficulty can be done extremely badly and when it does games can be screwed by this. But if well-tuned, it is really effective.

Another question is: if we like big number, why use levels in the first place? Why we do not just use experience points and offer a “smooth” progression? Because it’s not satisfying! We want to see number get bigger, but we want to perceive the change. That’s the reward after the “work”.

It is just like eating a pizza. We can eat a pizza on the week-end after a week of strict diet, or we can have just a couple bites of pizza every day. At the end, we will probably eat the same amount of pizza, but I think one solution is definitely more satisfying than the other.

Understanding the progression mechanics

Now that we know why we use level-based progression, it is time to play with some number. Note that this is not necessary, but understanding the math behind gameplay elements is a pet peeve of mine, and I think is helpful to understand better what and how to change something to achieve a particular goal. Also, because if you don’t do the math, your player will do it for you.

At the basis of level-based progression there are experience points. Mathematically speaking, level progression is a function mapping a certain amount of experience to a certain level.

L = f(E)

When designing the level progression, we are designing this function. How much experience (ad so time) players have to invest into the game to gain a level?

In practice, however, when designing a level-based progression, it is easier to find the inverse function: that is a function that, given a leve, tell use how much experience we need for this. This is usually called experience curve.

Linear, logarithmic, quadratic and exponential progressions.

We can already have some intuition. If our experience curve is linear, then every level need the same extra amount of experience: 10 for Level 2, 20 for Level 3, 30 for Level 4 and so on. If our experience curve is exponential, we need always more experience, and therefore we level-up slower at the end game. If our experience curve is logarithmic instead we need always less experience and, therefore, we level-up faster the more we play. They are all valid experience curves, everything depends on what kind of game you want.

Here, we will explore the most famous experience curve, the exponential one. The exponential curve is constructed starting from a single concept. Suppose you have a first amount of experience at level 1: a. In order to reach level 2 you want the player to double, triple, etc., your initial experience. So

E(2) = a + ba

That is, the experience at level 2 should be the starting experience plus b times that. For level 3, we do the same, we wont to have b times the increment at level 2.

E(3) = (a+ba) + b(ba) = a + ba + b^2a

In general, at level L:

E(n) = a + ba + b^2a + \ldots + b^L

That is a geometric succession, that can be luckily be expressed in closed form.

E(L) = a \frac{1-b^L}{1-b}

See? A nice exponential experience curve. But this time you know why it is like this. You know the meaning of the parameters and how to tweak them in order to obtain what you want.

Given an experience curve, one of the importan properties we can infer is the level progression over time. How fast a player will travel along the level progression from the bottom to the top? How much time the player need to put into the game for leveling up from 10 to 11? And from 79 to 80? How can I tune the experience of a certain area?

These are all interesting question. We can find an answer by looking at the experience curve. First step is to invert the function to obtain the level progression function, that is, how level advances given the experience.

L(E) =\frac{1}{log(b)} \log(\frac{a + (b - 1) E}{a})

Who. That’s ugly. But there is just some parameter noise. For the sake of the discussion, we assume b = e (that’s not unreasonable) and a=1.

L(E) = \log(1+ (e - 1) E)

Much better. Now, we need to consider the experience a function of time. Obviously, we cannot know a real function for that, but we can general idea of “how much experience we expect the player to collect at each time”. Do we expect the player to get always the same experience over time? Do we expect to get always more experience? This is very common and implemented  with high level monsters or quests giving more experience points.

Then, we can derive some kind of leveling speed function.

\frac{\partial L}{\partial t} =  \frac{(e-1)}{(1 + (e-1) E)} \frac{\partial E}{\partial t}

And here I stop for now. I like this stuff but, more than this is probably unnecessary. The important thing is that you try to model your progression in function of time by inverting the experience curve and plugging in some “experience function”. This will help you in having a rough estimate of the time and effort needed for leveling up in your game.

Real Case Examples

How are experience curves for real cases? Pretty much similar. I’ll give you the example of RuneScape.

E(L) = floor \left(  \frac{\sum_{n=1}^{L-1} floor \left( n + 300 \cdot 2^{\frac{n}{7}} \right)}{4} \right)

That’s definitely a more complex formula. Why is done like this? No idea. However, we can identify that it is an exponential function, in the same spirit of the one discussed above.

World of Warcrat legacy formula instead is not analytic. Instead, we have a formula for the experience required to level up at a certain level.

\Delta E(L) = ((8 \times L) + Diff(L)) \times MXP(L) \times RF(L)

Where Diff if a difficulty factor, MXP is the basic experience given by a monster of level L and RF is a generic scaling factor. This formula start as a quadratic experience curve and then explode into exponential (thanks to the Diff formula). Giving us this strange shape (note that this is the derivate of the experience curve).

In Diablo 3, instead the formula is a nightmare (there is a typo in the formula, but I do not want to rewrite this in LaTeX on WordPress…).

Where y is the \Delta E(L) and x is L. Why are this constants chosen in this way. I don’t know. Probably a fine tuning.

Conclusion

In the end, I hope you have fun with experience curves. There are thousands of different way to do them. Just remember that it is not just and always an exponential curve. Time and experience are linked together and modeling the experience curve can give you a lot of insight on how to avoid “grindy” parts in you game and keep the player in the flow.

Small rant about “blockchain” overuse

A lot of startups are using “blockchain” as a replacement hyped word for “distributed database”. Well, a blockchain is the most inefficient and slow “distributed database” ever created. Blockchain strength is not in being a database! Stop doing that!

The blockchain power is in avoiding divergent transactions, and guarantee a not falsifiable and immutable history. That is, no node in the system can alter the past of the chain. That’s it. They are huge and specific problems.

Nevertheless, there are industry people saying that “blockchain immutability” is the biggest problem of a blockchain.

And so we have tons of blockchain/alter-coins, but “centralized” or “owned” by someone. But if I need to trust “someone”, why using a blockchain system in the first place! Just use a damn distributed database!

(Originally on Twitter)

How to add a logo in Rust documentation

One of the feature I like the most on Rust is automatic documentation. Documentation is a pillar in language ergonomic, and I love that Rust spend so much time into making documentation and documenting code a much pleasant experience.

Rust autogenerated documentation (with cargo doc) looks good, every crate on crates.io get its documentation published on docs.rs, and, most important, every code example in the code is compiled and run as a “unit test” making sure that all the examples are up-to date!

I love that. But what if we want to customize a bit the documentation? For instance, by uploading a crate logo or a custom favicon? Googling this does not provide a lot of information. That’s why I am writing this small how to.

Continue reading “How to add a logo in Rust documentation”

Questions about Deep Learning and the nature of knowledge

Rush of Knowledge

If there is something that can be assumed as a fact in the AI and Machine Learning domain is that the last years had been dominated by Deep Learning and other Neural Network based techniques. When I say dominated, I mean that it looks like the only way to achieve something in Machine Learning and it is absorbing the great part of AI enthusiasts’ energy and attention.

This is indubitably a good thing. Having a strong AI technique that can solve so many hard challenges is a huge step forward for humanity. However, how everything in life, Deep Learning, despite being highly successful in some application, carries with it several limitations to that, in other applications, makes the use of Deep Learning unfeasible or even dangerous.

Continue reading “Questions about Deep Learning and the nature of knowledge”