Deadloop in trueskill.lua with 16 players

[Uveso]

Deadloop in "\lua\ui\lobby\trueskill.lua"
function Matrix:getDeterminant() calls Matrix:getCofactor() and this function recalls Matrix:getDeterminant()
So these functions are playing pingpong forever (with 16 players.)

How to reproduce:

Use a map with 16 players slots
Select option Spawn to Random - Unbalanced
Select Option Auto Teams to Manual Select
Assign all open slots to an AI
Be sure no player/AI has a team.

Click on Launch Game, and the game should freeze.

More Information:
https://forums.faforever.com/viewtopic.php?f=3&t=18990

[Garanas]

This isn't a deadlock, its an inherent problem to the math that is being used. I cannot find a source on it, but I believe the complexity of the current computation of the co factor matrix of a matrix is factorial - which is bad. The steps taken in the time calculations of Davax in the topic you mention (https://forums.faforever.com/viewtopic.php?f=3&t=18990) supports this.

To get an idea of the number of computations that are required when it is factorial:
10! = 3628800
11! = 39916800
12! = 479001600

That being said, there are better ways of doing this:

• https://scicomp.stackexchange.com/questions/34480/calculate-cofactor-matrix-efficiently

But its best to find a math library with a license that allows us to copy the code from that library directly. This type of code is extremely error prone.

[Benzi-Junior]

I did a little testing and found that with a 8x8 matrix the time it took to compute was already perceptible, and with 10x10 it was a couple of seconds, Garanas is correct that it the method used grows superexponentially.
I had a look around and found this

Without analyzing the code he uses for determinant to closely I tried hacking it naively into trueskill.lua and tested it witha 16x16 matrix (that couldn't be left as all zeros since the speedup is obtained specifically from pruning all 0 branches from he computation tree) and it returned instantaneously, question is do we want to add that library as a dependency or just that specific function, and trim the fat of it (the library is written to handle non-numeric matrices as well)

A thing to note is that if I understand the comments the author made to the function, it approximates the result rather than computing it fully (which would explain how I got a non integer result from a integer matrix) but I believe it should be close enough for our purposes

[Garanas]

That is a great find - the license (MIT) is perfect too.

We should not promote doing mathematical operations in Lua - that is not what Lua should be used for in this game. I suggest to just take the bits we need for this specific task. I am not familiar enough with the math whether an approximation is fine - but if it still creates reasonable teams then I don't see why not.

[Benzi-Junior]

I had checked the license and determined we'd be good to go with that.
One thing that occurred to me as I was working on integrating the new code, what is the determinant used for in the system?

The main issue I see is that, if I understand the comments correctly, the matrix being worked on is a players×(teams-1) matrix, but in order for the determinant to give you any meaningful information the matrix should be a square, and in fact the function from the library assumes it is.

I don't have a proper test environment set up to check what a typical matrix looks like but if I understand the code correctly the important case (2 teams) should be a 1 or 2 column matrix.

And just as I write this I realized another thing, if we are just using this to assign teams, then we don't need to work on a 16×16 matrix, since anything to do with trueskill is only meaningfull if the teams all have the same number of players, if all teams have 1 player I don't see a reason to check the matrix at all just give everyone their own team, the next case is 2 players per team which would give us a 16×8 matrix.
For computing the determinant that should be equivalent to 8×8 matrix which using the current implementation takes less than a second even when I test it with my decade old celeron processor.

So we might be able to sidestep this issue by just checking if the number of teams (columns) is greater than 8, if yes then we don't compute the determinant (either sidestep the part of the code that uses it or have the function return some "default" value).

[Garanas]

I'll answer in full later, but there are maps with 8 - 16 player slots, resulting in 8 - 16 teams if played as FFA. Therefore a case, say, 10 players with 10 teams is possible. Or am I misreading your post?

[Benzi-Junior]

My point was that in the FFA case we don't want to do the calculation since everyone get's their own team anyways (there is nothing to balance) and the next biggest case is 8 pairs (two player teams) which already drops tthe matrix size down to 16×8 which should be equivalent to computing 8×8 determinant which, although slow (it's definetly tens of milleseconds) is manageable.

[Garanas]

You're right - silly me. When it is FFA it doesn't particularly matter. I'm fine with the solution to skip the procedure all together in the case of pure FFA. What are opinions of other people on this matter?

[Benzi-Junior]

@Uveso What made you think that the issue came from getDeterminant in trueskill.lua ?
Was there something in the logs ?(I can't check them myself since the attachments where lost in the forum upgrade)
As far as I can tell "trueskill.lua" is only used to display the quality in the lobby, it isn't called when a game is launched.

[Uveso]

@Benzi-Junior
I added my own debug prints into every function and saw both functions endless printing into the log.
Endless means in this case 1-2 minutes.

[Garanas]

@Benzi-Junior If you're still up for it - I think not using this system when you have more than eight teams is the right choice.

[Benzi-Junior]

@Garanas I think it's stronger than that, since the trueskill system isn't meant to tackle anything other than 2 teams going at it.
#3461 I submitted a pull request that should fix the issue, please test and confirm