I have trouble coming up with a system of assigning a rating to player's performance. Well, technically there is is a trivial rating system, but I don't like it because it would mean assigning negative scores, which I think most players will be discouraged by.

The problem is that I only know the ideal number of actions to get the desired result. The worst case is infinite number of actions, so there is no obvious scale. The trivial way I referred to above is to take score = (#optimal-moves - #players-moves), with ideal score being zero. However, psychologically people like big numbers. No one wants to win by getting a mark of 0. I wonder if there is a system that someone else has come up with before to solve this problem?

Essentially I wish to score the players based on:

1. How close they've come to the ideal solution.
2. Different challenges will have different optimal number of actions, so the scoring system needs to take that into account, e.g. Challenge 1 -> max 10 points, Challenge 2 -> max 20 points.
3. I don't mind giving the players negative scores if they've performed exceptionally badly, I just don't want all scores to be <=0