New algorithm for autobalance=auto

[pkk]

QUOTE (the.ynik @ Jul 31 2010, 12:22 PM) pkk: hmm, how newbies are handled is a problem. Also, see my post above for why I wouldn't want the playing time to be part of the calculation.
Your calculation isn't really correct because you're just ignoring sigma. What TrueSkill does is not simply balancing mu; but balancing the probability of a draw, where both mu and sigma of both teams play a part.

σ is only a indicator, how exact μ is. A player which hasn't played has a 50% chance to win or loose, because system doesn't how to rank that player. It's like in ELO, where players start with 1500 points.

Player has a 50% win probability:
μ = 25

Player has a 0% win probability:
μ = 0

Player has a 100% win probability:
μ = 50

Over the time, the player played some games, the system know more about the players win probability and the sigma goes down.

QUOTE (the.ynik @ Jul 31 2010, 12:22 PM) Still, TrueSkill assumes each player starts with a fixed skill (which only varies slowly) and TrueSkill just doesn't know it yet. That's simply not true for Allegiance, where new players have almost no "skill" at all because they need to learn the game first. Assuming that a new player has average skill with high uncertainty, even if it works for ranking purposes (though not everyone agrees on that), could pose problems for autobalance.
Conservative rank might be better (or might not, I'm completely unsure at the moment).

You're right, Allegiance isn't Halo or any other 3D shooter.

If you're new to Allegiance, you need 30-50 hours to understand the basics of game. During that time your σ already dropped down to 4. If you were lucky and joined the winning team, your μ increased, if not your μ gone downwards. AllegSkill/TrueSkill thinks, it knows your win probability, but it doesn't.

As long you learn the game, keep out of rankings. You should enable the ranking system (ASGS question every 10 games/website) manually.

Some graphics:

Current ranks and stack rating:

17% Newbies
43 % Novice
31% Inter.
11% Veterans
1% Experts

31% of players are protected by Newbie protection rules

Current ranks to time:


Current σ to time:


Current μ to time:

[sgt_baker]

I didn't read the whole thread because I, frankly, can't be arsed with the perpetual bull@#(! that comes with any discussion in this area. Put quite simply, the matter of passing mu and sigma to AllSrv or the client is merely a matter of appending those values to the callsign when a player is handed over to the lobby. Like this: sgt_baker(14) -> sgt_baker(14)26.28,1.32

The funny thing is that we've known how to do this FOR YEARS. The funny thing is that I've even tested AllSrv with additional bits and bobs on the end of the callsign string and everything works as it does now WITHOUT having to meddle with any other code. Thus AllSrv can access both mu and sigma with MINIMAL changes to ASGS's SQL and AllSrv's C++. At no point does anyone need to touch the closed-source bits of ASGS designed and protected (to the death) by Pook.

The approach taken by the community here is ludicrous. You've worked up 100 different ideas, all of which don't really solve the problem with any sense of elegance. Why? Because nobody bothered to ask. If you think I'm going to trawl the forum for every rank-related thread and post, think again. WTF happened to "Duh.... maybe Baker and Co have.... OMG already thought of this?"

I'd be quite happy to help get this situation solved once and for all. Trust me, I've been waiting years just to FINISH AllegSkill. What I'm not going to do is read 100 posts blithering on about this and that. I have neither the time nor will to debate relatively simple subjects and concepts ad infinitum.

If you want my help, come and find me on IRC. Come and find me on Teamspeak. Anything to avoid having to read the endless drivel on these forums.

[MrChaos]

pkk

see pg 35 of the second link for the autobalance algorithm we used. I checked with Baker to be sure and you can see why I just couldn't rattle it off. Also be aware this is pre-game only and what Baker was discussing is the balancing during actual game play. Be aware that unless your algorithm has "memory" the in game balancing becomes exponential harder. The issue is wtf do you do when you have a sudden shift in teams rank and a NOAT full of poo. Or worse what happens if you have the opposite. What like tocall it mid day Euro and the Champy conundrum. There is not an easy solution and what you do in each situation is complicated.

MrChaos


edit:
My bad the.ynik TE (TigerEye) holds the data. I removed it from my HD as promised upon ending my day to day efforts regarding AS. My word is my bond. PM him and DON'T let him know I told you

[sgt_baker]

Just to give you an idea of how long we've been working in this area....

QUOTE (sgt_baker @ Aug 15 2007, 11:16 AM) Here is the code developed for pre-game balancing. A well-defined pick-pool is obviously required, as CPsychic.cs failed to compile under .NET 2.0 . This has already been implemented and tested using Pook's semi-ASGS database. I'll post some examples of this algorithm in action shortly.

Regards,

Baker

CODEusing System;
using System.Collections.Generic;
using System.Text;

namespace AllegStatsDataAbstraction
{
public class CTSAutoBalance
{
private CAllegGame game;
public CAllegTeam pickPool;
public CAllegTeam TeamA, TeamB;
private double kFactor; //For computing conservative rank estimates. Rank = Mu - kFactor * Sigma.
private double sysVariance; //The matching algorithm needs to know the beta[0] value

public CTSAutoBalance(double KFactor, double Variance)
{
game = new CAllegGame();
pickPool = new CAllegTeam();
TeamA = new CAllegTeam();
TeamB = new CAllegTeam();
kFactor = KFactor; //Usually set to 3 for 99% confidence.
sysVariance = Variance;
}

public void GetPickPoolFromGameIndex(int GameIndex)
{
//For testing we pull a game from the DB and attempt to divide all
//players into two well-matched teams.

pickPool.Players.Clear();
TeamA.Players.Clear();
TeamB.Players.Clear();

game.GetTeamsByIndex(GameIndex);

foreach (CAllegTeam team in game.Teams)
{
foreach (CAllegPlayer player in team.Players)
{
pickPool.Players.Add(player);
}
}
}

CAllegPlayer GetHighestRankedPlayer()
{
//Retrieves the 'top dog' from the pick pool.

double tempRank = -9999999999.0;
CAllegPlayer highestRankedPlayer = null;

foreach (CAllegPlayer player in pickPool.Players)
{
if (player.TSConRank(kFactor) > tempRank)
{
tempRank = player.TSConRank(kFactor);
highestRankedPlayer = player;
}
}

return highestRankedPlayer;
}

CAllegPlayer GetHighestMatchPlayer(CAllegPlayer PlayerToTest)
{
//For any given player this function iterates over the pick pool and
//returns the player who has the best skill match.

double tempMatch = 0;
CAllegPlayer highestMatchPlayer = null;

foreach (CAllegPlayer player in pickPool.Players)
{
double qual = MatchQuality(PlayerToTest.TSMu(), PlayerToTest.TSSigma(), player.TSMu(), player.TSSigma(), sysVariance);
if (qual > tempMatch)
{
tempMatch = qual;
highestMatchPlayer = player;
}
}

return highestMatchPlayer;
}

public double MatchQuality(double WMu, double WSigma, double LMu, double LSigma, double variance)
{
//The trueskill function for calculating player match quality.

double csquared = (2 * Math.Pow(variance, 2)) + Math.Pow(WSigma, 2) + Math.Pow(LSigma, 2);
double bSq = Math.Pow(variance, 2);
double d = (2 * bSq) / csquared;
double expBit = Math.Exp(-1 * (Math.Pow(WMu - LMu, 2) / (2 * csquared)));
double Match = expBit * Math.Sqrt(d);
return Match;
}

public void BalanceTeams()
{
//Assume we already have commanders!!!
while (pickPool.Players.Count > 1) //We can't perform a match with only one player!;
{
CAllegPlayer plyHighRank = GetHighestRankedPlayer();
pickPool.RemovePlayerByAccountID(plyHighRank.AccountID());


CAllegPlayer plyBestMatch = GetHighestMatchPlayer(plyHighRank);
pickPool.RemovePlayerByAccountID(plyBestMatch.AccountID());

//Check which team has the lowest conservative rank,
//add the highest ranked player to that team.
if (TeamA.TSConservativeRank(kFactor) > TeamB.TSConservativeRank(kFactor))
{
TeamB.Players.Add(plyHighRank);
TeamA.Players.Add(plyBestMatch);
}
else
{
TeamA.Players.Add(plyHighRank);
TeamB.Players.Add(plyBestMatch);
}
}


//Make sure we assign any orphan player to a team
if (pickPool.Players.Count == 1)
{
foreach (CAllegPlayer player in pickPool.Players)
{//Using foreach because we've removed players and have 'empty' indeces. Why does .NET allow this?!

if (TeamA.TSConservativeRank(kFactor) > TeamB.TSConservativeRank(kFactor))
{
TeamB.Players.Add(player);
}
else
{
TeamA.Players.Add(player);
}
}
}

//All done!
}
}
}

Edit: orking -> working

[sgt_baker]

Here's an image I found knocking around on my server.

AB based on real data

So does anyone want to talk?

[the.ynik]

QUOTE (sgt_baker @ Jul 31 2010, 03:38 PM) Just to give you an idea of how long we've been orking in this area....

Interesting, your "MatchQuality" is the q_draw function I suggested above (well, it's what TrueSkill proposes for balancing).
Looking at your code, isn't it likely that the 'matching' player (plyBestMatch) is the player with the second-highest rank? In that case, for small games (say, 3vs3), I see the problem that you'll assign the best, 3rd and 5th player to team A, and the 2nd, 4th and 6th to team B; leading to a slight stack. This becomes less of an issue with larger games (where good matches are available), but wouldn't it be better to balance the whole teams instead of matching individual players?

Anyways, for pre-launch balance that seems good enough; but what were your ideas about post-launch?

For post-launch, I'd like to restrict ourselves to online algorithms: the algorithm can only look at the teams and the player trying to join. It shouldn't force anyone to wait. It shouldn't guess who might be joining next (it won't be able to tell if people sit on NOAT because they want to join a game or because they want to chat).
I'd allow "memory" of past join/leave actions, but I don't see how we could profit from that information.

The reduction to online algorithms dramatically reduces the design space and makes implementation and testing easier. We don't need to consider stuff like letting one player wait until a good match for him wants to join, too.
It comes with the disadvantage that balancing is impossible in some scenarios (like the 'Champy conundrum', thanks MrChaos) - but again, this is mostly a problem for small games, not for the usual 120 vs 170 AS stack games.

Edit: Talk? sure. Umm... where? IRC server/channel? Sorry, I've got no clue where you guys meet.

[Orion]

QUOTE (the.ynik @ Jul 31 2010, 10:28 AM) Edit: Talk? sure. Umm... where? IRC server/channel? Sorry, I've got no clue where you guys meet.

server: irc.quakenet.org
channel: #freeallegiance

[sgt_baker]

See you've not read the code and don't understand what was going on there. IT IS NOT the player with the next highest rank. Read, mark, learn and inwardly digest before posting, please.

Edit: P.S. I'm in no mood to spoon-feed this to you.

[MrChaos]

Sure the.ynik glad to "help", it's a deeper problem then one think at first blush. How you handle draws is part of the whole thing tbs.

Im not sure you have the full measure of things is what Baker is saying, words in post are hard to hear "tone" come over to IRC AND it's so static. Word of warning we are working on something completely unrelated to Allegiance, but can discuss this with you if you so wish.

I'd like to say this; remember you aren't the only clever monkey in the tribe and we've got a head start

No matter what the other chimps may think of MrFartInHisPants


edit: spelling ><

[BetaTester]

wasn't fwiffo archiving asgs stats pages? couldn't allsrv fetch the players sigma and mu from this?

fwiffos schema looks like this:

Code: Select all

DROP TABLE IF EXISTS `stats`;
SET @saved_cs_client     = @@character_set_client;
SET character_set_client = utf8;
CREATE TABLE `stats` (
  `id` int(10) NOT NULL auto_increment,
  `place` int(11) NOT NULL,
  `callsign` varchar(20) NOT NULL,
  `mu` decimal(11,2) NOT NULL,
  `sigma` decimal(11,2) NOT NULL,
  `rank` decimal(11,2) NOT NULL,
  `wins` int(11) NOT NULL,
  `losses` int(11) NOT NULL,
  `draws` int(11) NOT NULL,
  `defects` int(11) NOT NULL,
  `stack_rating` decimal(11,2) NOT NULL,
  `cmd_mu` decimal(11,2) NOT NULL,
  `cmd_sigma` decimal(11,2) NOT NULL,
  `cmd_rank` decimal(11,2) NOT NULL,
  `cmd_wins` int(11) NOT NULL,
  `cmd_losses` int(11) NOT NULL,
  `cmd_draws` int(11) NOT NULL,
  `kills` int(11) NOT NULL,
  `ejects` int(11) NOT NULL,
  `drn_kills` int(11) NOT NULL,
  `stn_kills` int(11) NOT NULL,
  `stn_caps` int(11) NOT NULL,
  `kills_per_ejects` decimal(11,2) NOT NULL,
  `hrs_played` decimal(11,2) NOT NULL,
  `kills_per_hr` decimal(11,2) NOT NULL,
  `timestamp` timestamp NOT NULL default CURRENT_TIMESTAMP,
  `status` int(1) NOT NULL,
  `lgp` int(8) NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `index` (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=932403 DEFAULT CHARSET=latin1;
SET character_set_client = @saved_cs_client;

if it can't find it here fail-over somehow either using the ASGS rank or defaults for the sigma/mu

this is just a suggestion to see us though in R6 until R7/CSS. If this is feasible, then am i right in understanding that allsrv would have the required info. necessary to perform autobalance "bakers way"?