New algorithm for autobalance=auto

[lexaal]

QUOTE (Adaven @ Apr 23 2012, 05:32 AM) Oh I definitely expected a fair amount of processing to be needed before putting something out in the wild. Depending on how the db looks, there may even need to be restructuring of the data to help focusing in on certain problems / questions. I mainly just thought that as a recent Computer Science student, I would have been much more interested in ranking players of an online game than classifying mollusks for my school projects.

One part of the database must look like S:={playerID,mu,sigma²}.

But I shutup since all my approaches to autobalance didn't work good in simulations so they probably won't work in reality.

The most sick part is that you don't have a fixed group of players and you split them into two equal groups based on mu and a little bit of sigma... it is dynamic join/leave.. that makes it funny.

[Imago]

the latest fsmission afaik contains the following "code" for function CFSMission::GetSideRankSum, every player on a side gets this run:

Code: Select all

float fRank = ((pfsPlayer->GetPersistPlayerScore(NA)->GetMu() - (pfsPlayer->GetPersistPlayerScore(NA)->GetSigma() * g.balance.kFactor)) * g.balance.RankScaleFactor);

then when Weighted balance mode is selected, all join requests are handled with the CFSMission::CheckWeightedPR(CFSPlayer * pfsPlayer, SideID sideID, float fRank) function which is pasted below

Code: Select all

    float PlayerRank = (fRank == 0.0f) ? pfsPlayer->GetPersistPlayerScore(NA)->GetRank() : fRank;
    //End Imago

    //the.ynik/Turkey 7/10
    float nHighestTeamRank = 0;
    float nLowestTeamRank = 2147483646.0f;
    int nHighestPlayerCount = 0;
    int nLowestPlayerCount = 2147483646;
    float nHighestAvgRank = 0;
    float nLowestAvgRank = 2147483646.0f;

    int nPlayers = 0;
    int nTeams = 0;

    // Grab lowest and highest team ranks, player counts, etc
    for (SideLinkIGC*  psl = m_pMission->GetSides()->first(); (psl != NULL); psl = psl->next())
    {
        IsideIGC*   pTempSide = psl->data();
        if (pTempSide->GetActiveF())
        {
            float nTempSideRank = GetSideRankSum(pTempSide, false);

            // Store lowest teamrank
            if (nTempSideRank < nLowestTeamRank)
                nLowestTeamRank = nTempSideRank;

            // Store highest teamrank
            if (nTempSideRank > nHighestTeamRank)
                nHighestTeamRank = nTempSideRank;

            int nTempPlayerCount = GetCountOfPlayers(pTempSide, false);

            // Store lowest player count
            if (nTempPlayerCount < nLowestPlayerCount)
                nLowestPlayerCount = nTempPlayerCount;

            // Store highest player count
            if (nTempPlayerCount > nHighestPlayerCount)
                nHighestPlayerCount = nTempPlayerCount;

            nPlayers += nTempPlayerCount;
            nTeams++;

            float nTempAvgRank = (float)nTempSideRank / (float)nTempPlayerCount;

            // Store lowest avg rank
            if (nTempAvgRank < nLowestAvgRank)
                nLowestAvgRank = nTempAvgRank;

            // Store highest avg rank
            if (nTempAvgRank > nHighestAvgRank)
                nHighestAvgRank = nTempAvgRank;
        }
    }

    float imbalanceAvgRank = (nHighestAvgRank + 1)/(nLowestAvgRank + 1);
    float imbalanceTotalRank = (float)(nHighestTeamRank + 1)/(float)(nLowestTeamRank + 1);
    float imbalancePlayerCount = (float)(nHighestPlayerCount)/(float)(nLowestPlayerCount);

    //weighted average imbalance of teams before this player joins
    float oldImbalance = ((imbalanceAvgRank * g.balance.AvgRankWeight) + (imbalanceTotalRank * g.balance.TotalRankWeight)
        + (imbalancePlayerCount * g.balance.PlayerCountWeight)) / 
        (g.balance.AvgRankWeight+g.balance.TotalRankWeight+g.balance.PlayerCountWeigh
t);

    //initialise this here
    float newImbalance = 0;
        
    //When teams are approximately even, it is useful to allow players to join both sides.
    float Flexibility = (g.balance.FlexGamePercent / 100) * pow(g.balance.FlexDecay,(1 - oldImbalance - (nPlayers/nTeams/g.balance.AvgPlayerCountDivisor)));

    float lowestNewImbalance = (float)2147483646;
    //OK this is hideous... need to find the lowest newImbalance of all the sides the player could join
    //so do the same thing as above only with an extra loop layer.
    for (SideLinkIGC*  psl1 = m_pMission->GetSides()->first(); (psl1 != NULL); psl1 = psl1->next())
    {
        IsideIGC*   pPossibleSide = psl1->data();
        if (pPossibleSide->GetActiveF())
        {
            //running out of names for these variables
            float nPossibleHighestTeamRank = 0.0f;
            float nPossibleLowestTeamRank = 2147483646.0f;
            int nPossibleHighestPlayerCount = 0;
            int nPossibleLowestPlayerCount = 2147483646;
            float nPossibleHighestAvgRank = 0;
            float nPossibleLowestAvgRank = (float)2147483646;
            for (SideLinkIGC*  psl2 = m_pMission->GetSides()->first(); (psl2 != NULL); psl2 = psl2->next())
            {
                IsideIGC*   pTempSide = psl2->data();
                if (pTempSide->GetActiveF())
                {
                    float nTempSideRank = GetSideRankSum(pTempSide, false);
                    int nTempPlayerCount = GetCountOfPlayers(pTempSide, false);
                    if (pPossibleSide->GetObjectID() == pTempSide->GetObjectID())
                    {
                        nTempSideRank += PlayerRank;
                        nTempPlayerCount++;
                    }

                    // Store lowest teamrank
                    if (nTempSideRank < nPossibleLowestTeamRank)
                        nPossibleLowestTeamRank = nTempSideRank;

                    // Store highest teamrank
                    if (nTempSideRank > nPossibleHighestTeamRank)
                        nPossibleHighestTeamRank = nTempSideRank;
                            
                    // Store lowest player count
                    if (nTempPlayerCount < nPossibleLowestPlayerCount)
                        nPossibleLowestPlayerCount = nTempPlayerCount;

                    // Store highest player count
                    if (nTempPlayerCount > nPossibleHighestPlayerCount)
                        nPossibleHighestPlayerCount = nTempPlayerCount;

                    float nTempAvgRank = (float)nTempSideRank / (float)nTempPlayerCount;

                    // Store lowest avg rank
                    if (nTempAvgRank < nPossibleLowestAvgRank)
                        nPossibleLowestAvgRank = nTempAvgRank;

                    // Store highest avg rank
                    if (nTempAvgRank > nPossibleHighestAvgRank)
                        nPossibleHighestAvgRank = nTempAvgRank;
                }
            }//end nested for loop

            float PossibleImbalanceAvgRank = (nPossibleHighestAvgRank + 1)/(nPossibleLowestAvgRank + 1);
            float PossibleImbalanceTotalRank = (float)(nPossibleHighestTeamRank + 1)/(float)(nPossibleLowestTeamRank + 1);
            float PossibleImbalancePlayerCount = (float)(nPossibleHighestPlayerCount)/(float)(nPossibleLowestPlayerCount);

            float PossibleImbalance = ((PossibleImbalanceAvgRank * g.balance.AvgRankWeight) + (PossibleImbalanceTotalRank * g.balance.TotalRankWeight)
                + (PossibleImbalancePlayerCount * g.balance.PlayerCountWeight)) / 
                (g.balance.AvgRankWeight+g.balance.TotalRankWeight+g.balance.PlayerCountWeigh
t);

            //find the minimum imbalance of all join conditions
            if (PossibleImbalance < lowestNewImbalance)
                lowestNewImbalance = PossibleImbalance;

            //the imbalance after the player joins the team they want
            if ((SideID)pPossibleSide->GetObjectID() == sideID)
                newImbalance = PossibleImbalance;
        }
    }//thank God that's over
        
    //The fail condition
    if ((newImbalance >= oldImbalance) && ((newImbalance/lowestNewImbalance) > (1+Flexibility)))//end #192
        return DPR_TeamBalance;

    return (DelPositionReqReason)NA; //Imago functionalized 8/10

thanks

[Imago]

trip down memory lane: http://trac.alleg.net/browser/allegsvn/bra...ion.cpp?rev=993

[MrChaos]

QUOTE (Adaven @ Apr 22 2012, 11:32 PM) Oh I definitely expected a fair amount of processing to be needed before putting something out in the wild. Depending on how the db looks, there may even need to be restructuring of the data to help focusing in on certain problems / questions. I mainly just thought that as a recent Computer Science student, I would have been much more interested in ranking players of an online game than classifying mollusks for my school projects.

Makes sense and don't let my jokes stop you... just trying to make a clever.... ish joke was all

[the.ynik]

QUOTE (cashto @ Apr 10 2012, 02:22 AM) It turns out we don't know how many (0)s equal a single (15).

We don't know that and we likely won't ever know. And even if we did know this, a game of 2 vets against the appropriate numbers of newbies still wouldn't be fun - it's much better to put the vets onto different teams.

QUOTE (cashto @ Apr 10 2012, 02:22 AM) Until we get that figured out this idea is DOA. Either we have an autobalance that makes team sizes unbalanced, and all the attendent problems that creates -- or we have an autobalance that prevents newbies from joining the smaller team.

The basic idea behind my algorithm was do balance so that the games are balanced and fun (in my opinion): try to make the number of vets on both sides equal, and try to make the number of newbies on both sides equal.
This way we can balance without having to answer the question above. If you look at my algorithm, it can say a game is unbalanced without having know which team is favored.
If there are 5 (0)s vs. a single (15), I don't know which side will win, but I know that additional (0)s should join the (15), and an additional (9) should join the zeros. (anyone from rank 1 to 8 gets free choice of team in my implementation)
In fact the (9) joining the zeroes probably makes the game more unfair in the short term, but additional players joining later will balance it out so that both teams can have both skilled and unskilled players.

This is what makes this algorithm work so well (IMHO) without any of the complexity of AllegSkill - it defines a useful measurement for balance without having to tackle the hard problem of guessing the game's outcome. (which AllegSkill does a good job of for the purpose of skill updates, but that doesn't lead to a good balance algorithm when players join already running games)
I think my algorithm should be re-added to R6 (as an option, not replacing anything existing).