[ ivan.a @ 18.06.2013. 20:43 ] @
Već par dana pokušavam da napravim dobar sistem za balansiranje igrača koji su raspoređeni u 2 tima u odnosu na ukupan broj njihovih pobeda/poraza.
Potrebno je balansirati timove i smestiti igrače tako da ukupan odnos pobeda/poraza bude 50/50% (ili približno). Maksimalan broj igrača je 10 (5v5) i treba uzeti odnos "pobede/porazi" od svakog igrača (npr. 33, 45, 80, 60, 55% VS 30, 50, 70, 75, 50% ).

Sledeći kod je žešće "hard-code"-ovan:

Code:
void CBaseGame :: OHBalanceSlots( )
{
// all values
bool AllRanked = false; bool order1 = false; bool order2 = false; uint32_t x = 1; uint32_t y = 1; 
float SentTeam = 0; float ScouTeam = 0; float l = 0; float j = 0; float h = 0; float g = 0; float f = 0; float e = 0; 
float d = 0; float c = 0; float b = 0; float a = 0;
 
        //Main beginning
        if( !( m_Map->GetMapOptions( ) & MAPOPT_FIXEDPLAYERSETTINGS ) )
        {
                CONSOLE_Print( "[GAME: " + m_GameName + "] error balancing slots - can't balance slots without fixed player settings" );
                return;
        }
        CONSOLE_Print( "[OHBalance] Starting balancing..." );
 
        vector<string> PlayerWins;
        for( vector<CGamePlayer *> :: iterator i = m_Players.begin( ); i != m_Players.end( ); ++i )
        {
                float Win = 0;
                if( (*i)->GetGames( ) >= 10 )
                        Win = (*i)->GetWinPerc( );
 
                PlayerWins.push_back( UTIL_ToString( Win, 2 ) + " " + (*i)->GetName() + " " + UTIL_ToString( GetSIDFromPID( (*i)->GetPID( ) ) ) );
        }
        CONSOLE_Print( "[OHBalance] Ordering..." );
        sort( PlayerWins.begin( ), PlayerWins.end( ) );
 
        //find best ordering
        for( vector<string> :: iterator i = PlayerWins.begin( ); i != PlayerWins.end( ); ++i )
        {
                string wins;
                stringstream SS;
                SS << *i;
                SS >> wins;
                if( x == 1 )
                        l = UTIL_ToUInt32( wins );
                else if( x == 2 )
                        j = UTIL_ToUInt32( wins );
                else if( x == 3 )
                        h = UTIL_ToUInt32( wins );
                else if( x == 4 )
                        g = UTIL_ToUInt32( wins );
                else if( x == 5 )
                        f = UTIL_ToUInt32( wins );
                else if( x == 6 )
                        e = UTIL_ToUInt32( wins );
                else if( x == 7 )
                        d = UTIL_ToUInt32( wins );
                else if( x == 8 )
                        c = UTIL_ToUInt32( wins );
                else if( x == 9 )
                        b = UTIL_ToUInt32( wins );
                else if( x == 10 )
                        a = UTIL_ToUInt32( wins );
                else
                        CONSOLE_Print( "[OHBalance] Error. Too many slots" );
                x++;
        }
        // find best ordering
        //bad way, lol
        if( (a+c+e+g+j) > (b+d+f+h+l) )
        {
                if( (a+d+e+h+j) > (b+c+f+g+l) )
                {
                        if( ( (a+c+e+g+j)-(b+d+f+h+l) ) < ( (a+d+e+h+j)-(b+c+f+g+l) ) )
                                order1 = true;
                        else
                                order2 = true;
                } else {
                        if( ( (a+c+e+g+j)-(b+d+f+h+l) ) < ( (b+c+f+g+l)-(a+d+e+h+j) ) )
                                order1 = true;
                        else
                                order2 = true;
                }
        } else {
                if( (a+d+e+h+j) > (b+c+f+g+l) )
                {
                        if( ( (b+d+f+h+l)-(a+c+e+g+j) ) < ( (a+d+e+h+j)-(b+c+f+g+l) ) )
                                order1 = true;
                        else
                                order2 = true;
                } else {
                        if( ( (b+d+f+h+l)-(a+c+e+g+j) ) < ( (b+c+f+g+l)-(a+d+e+h+j) ) )
                                order1 = true;
                        else
                                order2 = true;
                }
        }
        if( order1 )
                CONSOLE_Print( "[OHBalance] Choosing Order 1" );
        else
                CONSOLE_Print( "[OHBalance] Choosing Order 2" );
 
        CONSOLE_Print( "[OHBalance] Starting swapping..." );
        for( vector<string> :: iterator i = PlayerWins.begin( ); i != PlayerWins.end( ); ++i )
        {
                string swinperc;
                string soldpid;
                string name;
                stringstream SS;
                SS << *i;
                SS >> swinperc;
                SS >> name;
                SS >> soldpid;
                uint32_t oldpid = UTIL_ToUInt32( soldpid );
                float fwinperc = UTIL_ToUInt32( swinperc );
                oldpid = oldpid;
                uint32_t newpid;
                if( order1 )
                {
                        if( y == 1 )
                                newpid = 10;
                        else if( y == 2 )
                                newpid = 5;
                        else if( y == 3 )
                                newpid = 9;
                        else if( y == 4 )
                                newpid = 4;
                        else if( y == 5 )
                                newpid = 8;
                        else if( y == 6 )
                                newpid = 3;
                        else if( y == 7 )
                                newpid = 7;
                        else if( y == 8 )
                                newpid = 2;
                        else if( y == 9 )
                                newpid = 6;
                        else if( y == 10 )
                                newpid = 1;
                        else
                                CONSOLE_Print( "Something is wrong here O_o" );
                }
                else
                {
                        if( y == 1 )
                                newpid = 10;
                        else if( y == 2 )
                                newpid = 5;
                        else if( y == 3 )
                                newpid = 4;
                        else if( y == 4 )
                                newpid = 9;
                        else if( y == 5 )
                                newpid = 8;
                        else if( y == 6 )
                                newpid = 3;
                        else if( y == 7 )
                                newpid = 2;
                        else if( y == 8 )
                                newpid = 7;
                        else if( y == 9 )
                                newpid = 6;
                        else if( y == 10 )
                                newpid = 1;
                        else
                                CONSOLE_Print( "Something is wrong here O_o" );
                }
 
                if( newpid <= 5 )
                        SentTeam += fwinperc;
                else if( newpid > 5 )
                        ScouTeam += fwinperc;
 
                if( newpid != oldpid )
                        SwapSlots( (unsigned char)oldpid, (unsigned char)newpid-1 );
                y++;
        }
        SendAllChat( "[Sentinel combined rating: " + UTIL_ToString( SentTeam, 2 ) + "]" );
        SendAllChat( "[Scourge combined rating: " + UTIL_ToString( ScouTeam, 2 ) + "]" );
        SendAllChat( "[Team diffrence: " + UTIL_ToString( (ScouTeam - SentTeam), 2 ) + "]" );
        SendAllChat( "[Win Chance (Sentinel: " + UTIL_ToString( ( ( SentTeam*100 ) / ( SentTeam + ScouTeam ) ), 2 ) + "%) 
(Scourge: " + UTIL_ToString( ( ( ScouTeam*100 ) / ( SentTeam + ScouTeam ) ), 2 ) + "%)]" );
}


Mislio sam prvo da rešim ovo po sistemu najbolji+najgori igrač (po win/lose odnosu) - korak po korak, ali nikako mi ne uspeva, a verujem da postoji bolje rešenje.
[ Mihajlo Cvetanović @ 18.06.2013. 23:58 ] @
Sa samo 10 igrača možda je najjednostavnije da provrtiš sve moguće kombinacije, kojih ima samo (10 nad 5) = 252. Svaka kombinacija predstavlja pripadnike prvog tima, a preostalih 5 su pripadnici drugog. Kako da vrtiš kombinacije? Probaj da guglaš sa "C++ loop through all combinations", ili "C++ iterate all combinations", ili slično.
[ ac1bd4 @ 19.06.2013. 01:03 ] @
Problem nije baš tako jednostavan.
http://en.wikipedia.org/wiki/Job_Shop_Scheduling
[ Mihajlo Cvetanović @ 19.06.2013. 09:37 ] @
Pošto algoritam ima sve podatke već na samom početku problem se zapravo svodi na neke jednostavnije probleme, tipa knapsack. Ali sa samo 10 elemenata ovo nije zapravo nikakav problem, jer se brzo mogu proveriti sve moguće kombinacije. Da je N=1000, ili milion, to bi već bila druga priča.
[ ac1bd4 @ 19.06.2013. 11:11 ] @
Pošto ima sve podatke svodi se na offline job shop scheduling, a ako mu je baš stalo da bude brz i efikasan nek potraži literaturu na tu temu. Verujem da je i sam znao da može da izvrti sve kombinacije ali da mu je cilj nešto brže od toga. Šta ako reši da njegov sistem treba da izbalansira igrače za dva fudbalska tima?
[ ivan.a @ 19.06.2013. 11:16 ] @
Hvala na odgovoru. Već sam čitao o "Knapsack problem".

Takođe, razmišljao sam da rešim na sledeći način:
Proveriti sve kombinacije dok vrednost ne bude ~=50%
Npr:

p(slot) - odnos pobede/porazi:

(p1+p2+p3+p4+p5) / 5 = 35%
(p1+p3+p4+p5+p6) / 5 = 40%
(p1+p4+p5+p6+p7) / 5 = 32%
i tako za sve igrače dok vrednost ne bude 50% (ili približno - u tom slučaju uzeti vrednost koja je najpreciznija...tipa 47%-53%).

Verovatno postoji i bolje rešenje.
[ Mihajlo Cvetanović @ 19.06.2013. 11:55 ] @
Nemoj ručno da pišeš sve kombinacije, bezveze je tako. Umesto 10 promenljivih treba imaš niz od 10 elemenata, i da onda vrtiš kombinacije uzimajući podatke iz niza. Proguglaj ono što sam ti napisao u mom prvom postu.
[ ivan.a @ 19.06.2013. 12:05 ] @
Ne vrtim ih ručno. Napisao sam kako bi to izgledalo u petlji.

Sada ću da testiram.
[ ivan.a @ 20.06.2013. 15:54 ] @
Odlično radi...9ms za sve kombinacije. Još samo da se malo preradi (nizovi).

http://pastebin.com/7N71C3wR
i php varijanta:
http://pastebin.com/5LSkjbuw

Hvala na savetima.