Modifying ranking to suit our use cases

[pranny]

Hi,

We have a game (online, social and RPG) developed on top of App
Engine. Inside the game, a player can be ranked upon fields, called as
ranking parameter - count of missions done, count of fights done,
count of fellow friends. Then we have a global (game wide, portals
wide) "men of honor" where we show the top people. As of now, what we
do is that we keep a datastore entity which maintains top 20 players
in each field, everytime a player's ranking parameter changes, we
compare it with the values in the top_20_list, and update the list
accordingly. Now this works great if we only have to show top 20
players across the game.

A new idea here is to show a player - his rank globally (portal wide,
game wide) as well as his rank locally (amongst his friends). Our
previous approach wont work here. So, i am looking forward to use
Google App Engine Ranklist as one of the most favored alternative way
of figuring these details out.

So, what i plan is to give every player a certain point/score on each
of the ranking parameter. And when we have to show his rank, we will
use the library to fetch his rank locally as well as globally.

I would like to know if there are any issues with my proposed
approach? How do i mould the existing library to better suit my needs?

[Bartholomew Furrow]

I think the library does what you want out of the box.  You'll have one ranker per dimension you want to score them on (times one per portal plus one global), and pretty much use it as the comments say.

Out of curiosity, how did you learn about the library?

--
You received this message because you are subscribed to the Google Groups "Google App Engine Ranklist" group.
To post to this group, send email to google-app-en...@googlegroups.com.
To unsubscribe from this group, send email to google-app-engine-r...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-app-engine-ranklist?hl=en.

[Michael Robellard]

On my implementation I currently only have a ranker for a players
cashOnHand. It ranks everyones cash on hand.

To display only friends ranks, I first do a datastore query to get the
persons friends ordered by descending cashOnHand and using a cursor
with a pagesize of 20. I then use the ranklist FindRanks(self, scores)
with a list of the scores returned from my query to get the ranks.

This ends up showing you the persons absolute rank in the game, but
only showing the users that are your friends, and shows them in the
proper order.

[Bartholomew Furrow]

To display only friends ranks, I first do a datastore query to get the
persons friends ordered by descending cashOnHand and using a cursor
with a pagesize of 20.

Tangentially, it sounds like you could do this more efficiently (though I'm guessing about your implementation).  The key thing here is that you never have to do a Query.  Queries are slower than Gets, and don't scale as well (though really only if you're going past, like, 100QPS on a particular index).

Here's how we do it in Code Jam:

1. Each person has a "friends" Entity that has just one entry: a list of user_ids.  Note that you want the user_id rather than the email or the users.User, because user_ids are permanent and the same user might start appearing with a different email if she adds a gmail address to her google account.  users.User objects compare using email, so you don't want that either.

2. Our friends/scoreboard page sends off javascript requests saying "Give me the scoreboard rows for the current user's first 30 friends."  The server side gets the "friends" Entity, pulls out the first 30 entries, Gets what it needs to out of the datastore, then runs FindRanks.  We limit to 30 at a time because the "what it needs... out of the datastore" is pretty big for each one.

3. Repeat step 2 for the next 30 friends, etc. until done.  The javascript will need to know how to sort them.

Unsolicitedly,

Bartholomew

[pranny]

This is exactly what we plan to do in our case, as well.
As far as your first question of 'how did i came to know about this
library' is concerned, even i am not sure how i came to it the "fist"
time perhaps i read about it somewhere.. But while we were discussing
our approaches, i said to myself that i know a library where something
of this sort has been implemented.

What we need to do is to make six different lists, on the basis of six
different ranking parameters. So, it looks like we have to make six
different Rankers and get them accordingly.

Thanks for this great library. I will post my queries further to the
group, in case i have some !!

[pranny]

There is one tiny problem. The players in our game have friends count
of more than 1000, on an avg 1000. Storing the list of friends (as
mentioned in 1.) will have a list of (avg) 1,000 ID. Each ID has a
size of 36Bytes. So, this makes the size of entity as 36KBytes on an
avg. Fetching of 36KBytes makes the .get() operation slow. We can
implement the concept of shrad counters in here, but that will involve
reading in batches of 500. So i was really looking forward if there is
a way which we can get all the users in comparatively cheaper manner?

On Jul 22, 9:58 pm, Bartholomew Furrow <fur...@gmail.com> wrote:

[Robellard, Michael]

What you can do is have a separate entity that has only the list of friends in it that is a child entity of the user entity, that way you don't need to load the list every time. For a good overview of this technique, check out the 2009 Google I/O topic:

http://www.youtube.com/watch?v=AgaL6NGpkB8

--
You received this message because you are subscribed to the Google Groups "Google App Engine Ranklist" group.
To post to this group, send email to google-app-en...@googlegroups.com.
To unsubscribe from this group, send email to google-app-engine-r...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-app-engine-ranklist?hl=en.

--
Michael Robellard
(216)288-2745
Play my game Railroad Empire http://apps.facebook.com/railroadempire

[Bartholomew Furrow]

I think the problem is that pranny doesn't even want to load the whole list of friends every time.  Pranny, I'd suggest the following:

1. Re-examine whether any user really wants to see data for 1000 individual people, and whether you actually want this page.  Failing that,

2. Go with a design like the following:

- In your user-info entity (or in a wholly new entity), add a 'num_friends' field.

- Pick a number K on the order of 100.

- When a user goes to add a friend, it is added to an entity parented to the user-info entity with key 'friend', name 'page%d' % (num_friends_so_far / K).  Note that these "pages" are only internal to your server, and don't have anything to do with what gets displayed to the user.

- When a user goes to get his friends list, you return the number of friends pages ((num_friends+K-1)/K).  Then, for i in range(num_pages), the client asks "server, give me friend page i".  The server then returns the friends indicated by key name 'page%d' % i.

- When a user deletes a friend, assuming this is an uncommon operation, just delete it from its list and don't decrement the counter.  If it's a common operation, that might require a slightly different design.

With this design:

Adding a friend requires a transaction that contains, sequentially: (1xGet), (1xGet), (2xPut).

Getting your friends list requires one Get (to get the #), followed by num_friends/K separate javascript requests, each of which performs 1 Get.

Removing a friend requires a transaction that contains, sequentially, (1xGet), (1xPut).

Of course I don't know all your specs, so this might be inappropriate and Michael's suggestion might well be better.

Cheers,

Bartholomew

[pranny]

Michael,
Thanks for your input. But, creating a list of friend_ids won't be
much of a help, owing to its serialization, deserialization costs.
In one of your previous comments, you have mentioned

"""To display only friends ranks, I first do a datastore query to
get the
persons friends ordered by descending cashOnHand and using a cursor

with a pagesize of 20. I then use the ranklist FindRanks(self,
scores)
with a list of the scores returned from my query to get the ranks.
"""

Can you help me with a data model for that?

Bartholomew,
Thanks for your detailed analysis and solution. It fits to a great
extent to our needs.

However, the problem that i see goes something like :

class Player(db.Model):
name = db.StringProperty()
total_friends = db.IntegerProperty()
k = db.IntegerProperty(default = 100)
rank = db.IntegerProperty()

class PlayerFriends(db.Model):
fr_list = db.ListProperty(str)

So, when a Player adds a friend, we store friend's ID in an entity of
type PlayerFriends for a particular page, parented to Player entity.
Now, using ranklist, i update the player's rank every-time he performs
an action. So, if i have to find the rank of all my friends,
i need to (a) Fetch all my friends (b) batch get their rank (c) Sort
that rank and (d) Display that to the user

On Jul 26, 10:56 pm, Bartholomew Furrow <fur...@gmail.com> wrote:
> I think the problem is that pranny doesn't even want to load the whole list
> of friends every time.  Pranny, I'd suggest the following:
>

> 1. Re-examine whether any user *really* wants to see data for 1000

> individual people, and whether you actually want this page.  Failing that,
> 2. Go with a design like the following:
>
> - In your user-info entity (or in a wholly new entity), add a 'num_friends'
> field.
> - Pick a number K on the order of 100.

> - When a user goes to *add* a friend, it is added to an entity parented to

> the user-info entity with key 'friend', name 'page%d' % (num_friends_so_far
> / K).  Note that these "pages" are only internal to your server, and don't
> have anything to do with what gets displayed to the user.

> - When a user goes to *get* his friends list, you return the number of

> friends pages ((num_friends+K-1)/K).  Then, for i in range(num_pages), the
> client asks "server, give me friend page i".  The server then returns the
> friends indicated by key name 'page%d' % i.

> - When a user *deletes* a friend, assuming this is an uncommon operation,

[Bartholomew Furrow]

So, when a Player adds a friend, we store friend's ID in an entity of
type PlayerFriends for a particular page, parented to Player entity.
Now, using ranklist, i update the player's rank every-time he performs
an action.

If I understood that, it sounds like a bug.  If I'm in first place and someone passes me, I should be in second place; but until I do something, my rank won't be updated and I'll appear to be in first.

 

So, if i have to find the rank of all my friends,
i need to (a) Fetch all my friends (b) batch get their rank (c) Sort
that rank and (d) Display that to the user

I believe that is the only correct way of solving the problem.  What I'm proposing in particular is that steps (a) and (b) are performed in multiple asynchronous javascript requests, and that the javascript then does (c) and (d), either as results come in or when they're all there.

This has the potential to be slightly incorrect: if Alice is 1st and on my first page, and I go fetch her, and Bob is 2nd and on my second page, and he passes her before I fetch him, they'll both appear to be in 1st place.  But unless you have a lot of rapid score updates (which I'm guessing you don't, since you're on App Engine) it's probably good enough.  You could even munge the results in javascript to make them look good.

[pranny]

Cool, i will proceed with this method! Thanks Furrow.