Lila: try blossom algorithm for tournament matching

[ornicar]

https://github.com/antma/scala-tools

https://en.wikipedia.org/wiki/Blossom_algorithm

[antma]

Library usage example:
WMMatching.minWeightMatching(fullGraph(n, pairScore)).mateToEdges

I recommend use this piece of code, since in situation when graph edges comes in random shuffle order, program runs a little bit slower.

After switching from exponent complexity algorithm to polynomial it is possible to calculate more difficult penalties for played recently players.
For example, LastOpponents could be replaced by RecentOpponents(https://github.com/antma/scala-tools/blob/master/RecentOpponents.scala). This could fix situation when same pairing occurring for 3-4 top players again and again.
Usage notes:
1) start from value RecentOpponents.empty
2) use updated method inside Iteratee.fold in PairingRepo.scala.
3) result score could be converted by expression (recentPlayers.score() * 8e6).toInt

Note that result score >= 1.0 if and only if when one of the players play with other in his last game.

[ornicar]

done

[ornicar]

Just a heads up @antma, I'm now using this algorithm for pools as well. It does wonders.

Thank you very much for it!

[antma]

For pools, I propose drop edges with high score from the source Graph (input), not from Matching (output). In the case if performance matter.
Helper function for that case could look like this:
private def buildGraph(nvertex: Int, pairScore: (Int, Int) => Option[Int]): Array[(Int, Int, Int)] =
(for (j <- 1 until nvertex; i <- 0 until j; p <- pairScore(i, j)) yield (i, j, p)).toArray
Where pairScore returns Some if we want include edge into the Graph when pairScore(i, j) < maxPairScore.

[ornicar]

I see what you mean. That's very interesting, yes. Perf is very good but I've seen some rare spikes:

Colors represent the different pools. The 5+0, in pink, is the most busy.
Could be indicating the JVM is struggling, though, not the algorithm. Here's the max players it was pairing:

I'll apply your suggestion right now.

[ornicar]

It is, unsurprisingly, measurably faster. Awesome!

Would you recommend using this https://github.com/antma/scala-tools/blob/master/RecentOpponents.scala for tournaments? It looks like a lot of data to keep/load in memory. Especially for lichess marathons with close to 5,000 participants https://en.lichess.org/tournament/summer16

[antma]

I'm not complete sure. I'm closer to not recommend. Don't think about marathon case and memory consumption. Only try to fix the "small private tournaments with about 20 players" case, for avoid play with same opponent again and again.
3 months ago, I commit something to my branch, but now it isn't auto-mergeable. As far as I can remember, difference between lastOpponents and recentOpponents computation is negligible to matching algorithm itself.

Now, I'm more interested how color distribution works. Last hourly tournament I played 4 games with white and 7 with black.

[ornicar]

I was explaining color distribution on #lichess IRC channel on freenode recently:

@ornicar each DB user has a "color" integer field
@ornicar when you get white, it's incremented. You get black, it's decremented.
@ornicar When you get a lobby random color game, or a tournament pairing, the user with lowest value gets white
ilevy__ yeah that was about what I was thinking. makes sense
ilevy__ I was imagining each player had a ratio of white games
ilevy__ but same idea
ilevy__ yours is more efficient
@ornicar https://github.com/ornicar/lila/blob/master/modules/user/src/main/UserRepo.scala#L104-L114
ilevy__ side note about colors: aborted games are still counted in this -- intended behavior at this point? When playing a single opp repeatedly sometimes you have to
but then the next rematch has the opposite color
@ornicar it's handled https://github.com/ornicar/lila/blob/master/modules/lobby/src/main/AbortListener.scala#L14-L19
@ornicar yes the rematch gets opposite color; it's by design
@ornicar but your counter is incremented
@ornicar and later on the colors are compensated
ilevy__ k, thanks
@ornicar my solution ensures that players get 50% white, in general; but not against that one opponent
@ornicar because it would be too damn expensive

[antma]

https://github.com/antma/scala-tools/blob/master/src/test/scala/WMMatchingTest.scala

I saw that matching code was ported for Scala 2.13. So I add some testing code for matching algorithm (answers were generated by DP-like bruteforce algorithm). Additional testing time ~11 seconds.