[algorytm]Podział graczy po ilości pkt Opcje

[ShadowD]

Hej, tworzę stronę gdzie każdy ma daną ilość punktów, wygranych, przegranych i wyjść z gry.

Stworzyłem jak na razie takie założenia, wygrany ma +5, przegrany -3, osoba która wyszła z gry podczas jej trwania -10, w grze zawsze występuje 5 osób, istnieją dwie drużyny każda po 5. Gracze wchodzą do gry i po uzbieraniu 10 gra automatycznie jest stratowana, a oni przydzielanie dowiedzionych drużyn tak by gra była jak najbardziej zrównoważona.

Nie koniecznie wiem jaki algorytm można by zastosować by teamy były jak najbardziej zrównoważone, można by przydzielać graczy w systemie 1-2-2-2-2-2-1, od największej ilości punktów do najmniejszej, lecz jeśli pierwszy gracz posiada 2000pkt, a reszta ~1200pkt to teamy nadal nie będą w najlepszej kondycji. Przydzielanie najlepszego do pierwszego teamu, a następnie reszty od najlepszego do najgorszego do drugiego aż do wyrównania różnicy też może nie zawsze dać dobry rezultat.

Trzeba pamiętać, że nawet najlepszy gracz z gromadą osób nie umiejących grać nie da sobie rady z samymi średnio zaawansowanymi. Gracze z małą ilością wygranych (procentowo) lub z małą ilością punktów powinni mieć jakieś inne/specjalne uprawniania do rozkładania ich po równo w drużynach. Co o tym myślicie?

Moim zdaniem najlepszym pomysłem na daną chwilę jest dodanie najlepszego do #1, reszty do #2 do czasu gdy ich pkt nie będzie większe nić #1, a jeśli go przewyższy znów do #2 na identycznych zasadach, gracze rozdawani od największej ilości punktów, jeśli w końcowym rozrachunku drożyny będą różniły się większą ilością pkt. niż 10% (liczba strzelona nieco w ciemno) gra może zostać automatycznie zamknięta, a gracze proszeni o wejście do nowej.

Moim pytaniem związanym z php, a w zasadzie z samym algorytmem było by jak coś takiego najlepiej zapisać pamiętając o ograniczeniach z strony php, kod będzie w przeszłości odpalany co kilkanaście sekund więc jego optymalność, a w zasadzie optymalność algorytmu musi być dosyć spora, macie jakiś pomysł na spisanie go lub opracowanie innego?

Mam nadzieje, że nie namieszałem za mocno.

[Spawnm]

Może daj tiery ?
gracze z przedziału 1-100 , 101-200 itd. potem po średniej i powinno być ok.

[ShadowD]

Głównym celem tego systemu ma być umożliwienie jak najszybszej rozgrywki z sprawdzoną grupą osób. Stosowanie wielu grup okraszonych danymi przedziałami wydłuży czas jaki każdy gracz będzie musiał czekać, system ma wystartować dopiero niebawem, pierwsi gracze mieli by dobrze ponieważ byli by w najliczniejszej grupie, ale jak ktoś tylko z niej wyjdzie nie będzie mieć zbytnio równych sobie. Poza tym gra z dwoma lepszymi graczami i resztą słabszych spowoduje może wiele wyrwanych włosów od ciągłych śmierci, ale też pomoże im nauczyć się grać. Zawsze lepiej mięć lepszych kompanów.

[toel]

Taki algorytm mi wpadł do głowy - na razie wydaje mi się logiczny, ale sam oceń.



Dzielisz losowo na 2 drużyny po 5.

Teraz sprawdzasz, w której jest większa suma punktów.

Sprawdzasz różnicę między drużynami.

Dodajesz ilosc punktów najsłabszego gracza ze słabszej drużyny do tej różnicy.

Dzielisz całość na 2 i w mocniejszej drużynie szukasz osoby punktowo najbardziej zbliżonej do tego wyniku.

Wymieniasz ją z najsłabszym graczem z drużyny "słabej".

I tak aż do momenty gdy ilość punktów w drużynach będzie równa (mało prawdopodobne) lub gdy teraz to drużyna słaba będzie mocna. Oznaczało by to, że nie ma już opcji podmian.


Wymyślone na szybko, teraz wydaje mi się ok, no i mam nadzieję, że w mairę sensownie to wytłumaczyłem

[everth]

A może tak:

1. Bierzemy środek rozkładu np. medianę
2. Na prawo od niej bierzemy gracza i dajemy go do drużyny A, na lewo dajemy do drużyny B
3. W drugim kroku odwracamy kolejność to znaczy gracz z prawa trafia do B a z lewa do A
4. Powtarzamy powyższą sekwencję aż uzyskamy 5 graczy
5. Dla kolejnych drużyn powtarzamy

Algorytm powinien tworzyć silne drużyny średnie a skrajnych graczy mieszać z sobą. Może się to wydawać na początku bez sensu ale teoretycznie osłabia to najsilniejszych a słabszym pozwala się wybić. Po wielu rozgrywkach rozkład powinien zagęszczać się wokół środkowej wartości. Pisane z głowy więc jakby ktoś zauważył durnotę to pisać

[Spawnm]

to może idąc dalej tropem tierów nie dawać ich sztywno tylko elastycznie
Czyli robisz jakiś wpis w bazie z info o danym meczu gdzie jest ratio silla wszyskich graczy , potem dostęp do meczu dajesz tylko tym których skill jest w miarę bliski temu z ratio.
To zapobiegnie wchodzeniu na mecze dla bardziej pro graczom początkującym a ci co wejdą będą sortowani tak aby po obu stronach było tyle samo skill points .
Dodatkowo aby nie było płaczu można dodać opcję sondy czy ponownie wymieszać teamy (w razie by w jednym był jeden pro i 4 lamki a w drugim teamie same średniaki itp. )

[lobopol]

Może głupie, ale:
1. drużyna pierwsza dostaje gracza z najwyższą ilością punktów
2. drużyna druga dostaje następnego w kolejności
porównanie która drużyna ma większą ilość punktów (oczywiście pierwsza:P)
3. drużyna druga dostaje 3 gracza w kolejności punktów
4. drużyna pierwsza dostaje 4 gracza w kolejności punktów
porównanie która drużyna ma większą ilość punktów
5. drużyna z mniejszą ilością punktów dostaje 5 gracza w kolejności punktów
6. drużyna z większą ilością punktów dostaje 6 gracza w kolejności punktów
itd. do końca


Bądź druga opcja
1. drużyna pierwsza dostaje gracza z najwyższą ilością punktów
2. drużyna druga dostaje następnego w kolejności
porównanie która drużyna ma większą ilość punktów (oczywiście pierwsza:P)
3. drużyna pierwsza dostaje 10 gracza w kolejności punktów
4. drużyna druga dostaje 9 gracza w kolejności punktów
porównanie która drużyna ma większą ilość punktów
5. drużyna z większą ilością punktów dostaje 8 gracza w kolejności punktów
6. drużyna z mniejszą ilością punktów dostaje 7 gracza w kolejności punktów
itd. do końca

No i 3 opcja
1. drużyna pierwsza dostaje gracza z najwyższą ilością punktów
2. drużyna druga dostaje następnego w kolejności
porównanie która drużyna ma większą > ilość punktów (oczywiście pierwsza:P)
3. drużyna pierwsza > dostaje 10 gracza w kolejności punktów
4. drużyna druga dostaje 3 gracza w kolejności punktów
porównanie która drużyna ma większą > ilość punktów
5. drużyna z większą > ilością punktów dostaje 9 gracza w kolejności punktów
6. drużyna z mniejszą ilością punktów dostaje 4 gracza w kolejności punktów
itd. do końca

edit. Jeszcze czwarta opcja:
1. drużyna pierwsza dostaje gracza z najwyższą ilością punktów
2. drużyna druga dostaje następnego w kolejności
porównanie która drużyna ma większą > ilość punktów (oczywiście pierwsza:P)
3. drużyna pierwsza > dostaje 10 gracza w kolejności punktów
4. drużyna druga dostaje 3 gracza w kolejności punktów
porównanie która drużyna ma większą > ilość punktów
5. drużyna z większą > ilością punktów dostaje 4 gracza w kolejności punktów
6. drużyna z mniejszą ilością punktów dostaje 9 gracza w kolejności punktów
itd. do końca

Najgorzej się te algorytmy niestety sprawdzą w sytuacji np. :
1 gracz 1000 punktów reszta po 100 itp.
Przydałoby się sprawdzić jak się ma średnia wszystkich punktów do punktów najlepszego (jeszcze przed dzieleniem)
w sytuacji 190 średnia, a 1000 najlepszy nie ma nawet jak równo podzielić. A co do różnic to 10% będziesz miał naprawdę rzadko różnicy (wiem, że w ciemno strzelałeś)

Ten post edytował lobopol 12.08.2010, 17:17:50

[Crozin]

1) Poziom zawodnika lepiej jest określać na podstawie jego wyników z ostatnich 5-10-100 meczy (w zależności od tego jak często w tej grze zawodnik będzie mógł grać), a nie jego całej przeszłości. Ktoś mógł przez długi czas słabo grać, a potem błyskawicznie się wybić - powinien grać z lepszymi.
2) Powinieneś umożliwić ręczne ustawienie drużyn, bo co jeżeli przykładowo grupa osób z Krakowa i druga z Warszawy będzie chciała sobie zrobić zawody? Powinni mieć możliwość ustalenia jak dokładnie chcą grać.
3) Jak już wspomniano powinna być możliwość ustalenia, że w tym meczu mogą grać tylko osoby na odpowiednio wysokim/niskim (ograniczenie od, do oraz od i do) poziomie.

Co do samego automatycznego ustawienia drużyn. Jeżeli podstawą rankingu mają być jakieś punkty to raczej nie masz zbyt dużych możliwości - obie drużny powinny mieć jak najbardziej wyrównaną sumę punktów. Jeżeli natomiast będziesz brał pod uwagę wyniki z kilku ostatnich spotkań, wyciągniesz z nich dużo danych statystycznych n/t danego zawodnika nie tylko punkty, ale i na przykładzie piłki nożnej: ile miał sytuacji do oddania gola, ile było na bramkę ile akcji wyprowadził, ogólnie: jak w danym meczu grał, dodatkowo w jakiej lidze odbył się mecz i jak wypadł na tle swojej drużyny* - wtedy możesz przyporządkować mu jakiś tam wynik punktowy - potem sytuacja wygląda podobnie: dzielisz zawodników tak by ich punkty były jak najbardziej wyrównane.

* Chodzi o to, że twoja drużyna mogła przegrać 3:7, ale to ty zdobyłeś 3 punkty, ty wyprowadziłeś 6 akcji, ty zrobiłeś coś tam, a reszta drużyny kaleczyła - wtedy powinieneś mimo przegranej zostać oceniony wysoko.

[ShadowD]

OKi, coś próbuję za waszych propozycji wybrać. Nie liczę na ogromy użytkowników na wstępie więc przerzucanie graczy pomiędzy teamami nie może mieć miejsca.

Aktualnie poszukuje algorytmu na najbliższą liczbę danej w zbiorze, mam na przykład array(12,14,3452, 2365,344), i liczbę 400 oczekuję dostania 344. Jest może jakiś gotowy algorytm bądź posiada nazwę owego, lub coś po czym mógł bym wyśledzić go w googlach.

[toel]

[PHP] pobierz, plaintext 
 
function getClosest($array,$number)
{
	$diff=null;
	$closest=null;
 
	sort($array);
 
	foreach($array as $item=>$value)
	{
		$temp_diff=$number-$value;
 
		if($temp_diff<0)
		{
			$temp_diff=$temp_diff*(-1);
		}
 
		if($diff===null || $diff>$temp_diff)
		{
			$diff=$temp_diff;
			$closest=$value;
		}
		elseif($diff<$temp_diff)
		{
			return $closest;
		}
	}
 
	return $closest;
 
}
 
[PHP] pobierz, plaintext 

takie coś może być ?

Ten post edytował toel 13.08.2010, 14:16:24

[ShadowD]

W czystej postaci nie zadziała na moje potrzeby, ale po przestudiowaniu postaram się go przystosować.

Tymczasowe posiadane dane które posiadam są - http://www.dota-league.pl/

[everth]

Może ci się przyda, dla mnie działał dosyć szybko:

[PHP] pobierz, plaintext 
function getLeft($number,$array) {
   $length = count($array);
   if ($length==1) {
      if ($array[0]>=$number) return false;
      return $array[0];
   }
   asort($array);
 
   $divide = ceil($length/2);
   $array = array_chunk($array,$divide);
 
   $left = max($array[0]);
   $right = min($array[1]);
 
   if($left>$number && $right>$number) return getLeft($number,$array[0]);
   if ($left<$number && $right<$number) return getLeft($number,$array[1]);
   return getLeft($number,$array[0]);
}
[PHP] pobierz, plaintext 

[thek]

Ścisły podział punktowy uważam za nieco nieprecyzyjny z racji różnego skilla graczy. Widziałem to nieraz i wykorzystywałem w grach przeglądarkowych. Jako łapiący szybko algorytmy, bylem w stanie w kilka dni rozkminić algorytmy rozgrywki, kasowałem stare konto i nowe prowadziłem nowe bardzo optymalnie, przez co w takich w miarę świeżych potrafiłem w mniej niż tydzień wystrzelić, przy kilku tysiącach kont, do top50. Bez stosowania botów. Dobre planowanie wystarczało. Jeśli takimi algorytmami dzieliłem z hardcorami to dopiero były jazdy. Kiedyś jeden w 2 dni od założenia konta wskoczył na pierwsze miejsce na serwerze. Taki gracz potrafi nawet z niskopoziomową postacią pociągnąć drużynę, praktycznie na straty spisaną, do zwycięstwa. Kilku w drużynie i rozkładają po kątach nawet ludzi grających znacznie dłużej Wprowadź przyznawanie punktów zależne od konkretnych akcji. Coś co można określić jako doświadczenie bitewne. Ilość zdobytych punktów, pokonanych wrogów, asysty miały by wpływ na sumaryczną punktację drużyny i potem ilość punktów określonego gracza decydowała o jego części "łupu" za wygraną. Dzięki temu pozbyłbyś się w pewien sposób także "taksówek". Aczkolwiek i mechanizmy takie także omijałem w kilku grach pozwalając na swoich kontach nabijać słabym graczom niebotyczne ilości punktów w ekspresowym tempie (błędy tego typu zgłaszałem i w ciągu góra kilku dni wychodziły poprawki) by przebili się do top100 Admini z reguły mieli ze mną masę utrapienia bo podawałem na podstawie analiz gotowe wzory służące określonym celom. Excel to jednak świetne narzędzie do wyłapywania zależności

Nie polegaj na samym miejscu, pozycji. Osoba dobra szybko na wysokie wskoczy, ale nie liczyłbym na to. Wiele zależy od algorytmu. Premiuj słabych wśród silnych (niech mają szansę podjąć rękawicę przed gnębiącymi ich), bo wielokrotnie się zdarzają playerkillerzy, który robią sobie z nowych farmy punktowe. Drobne, ale stałe źródło dochodu. Osłabiaj silnych w walce ze słabszymi, by im się ten proceder nie opłacał. Może to być system karmy jakiś, który za ataki na słabych mocno osłabia ich walory bitewne. Mają gracze walczyć z równymi sobie. Albo premiuj walki z równymi sobie w miarę poziomem. No chyba, że chcesz szkolić kamikaze i dasz bonusy za ataki na silnych Ja znałem taki system i były jaja z tego powodu. Gracz silny ugadywał się ze słabymi i wystawiał się do walki bez obrony oraz bez oręża, przez co słabi ich lali i zbijali niesamowite ilości punktów.

Sam przydział jeśli się uprzesz rozwiązuj z podziałem medianą. Weź najsilniejszego do drużyny A a 2 i 3 do drużyny B. Jeśli suma punktów drużyny przeciwnej będzie mniejsza niż tej, do której aktualnie dodajesz gracza - dodaj kolejną. Jeśli przekroczy - przejdź do drużyny przeciwnej i dodaj postać następną w kolejce. Całość rób tak długo aż skończą się gracze lub któraś z drużyn osiągnie limit postaci na drużynę. W tym ostatnim wypadku reszta pozostałe postacie w puli trafiają do drużyny przeciwnej niż ta, do której aktualnie dodajesz. Zrobiłbym jednak zabezpieczenie, bo może się okazać, że jest jedna bardzo silna postać i wiele płotek. Wtedy bardzo trudno będzie tym plotkom wygrać w starciu z silnym bez dodatkowych algorytmów wzmacniających słabe oraz osłabiających silne postacie. Może jakiś limit który w momencie różnicy punktowej obu drużyn większej niż X% usuwa najsilniejszą i robi losowanie ich pośród tej pomniejszonej puli + następna w kolejce. W ten sposób silny czeka na równiejszy skład drużyn, ale nie blokuje to meczy. Odbywają się one po prostu w innych składach. Pula może mieć więc niekoniecznie równą ilość graczy. Jeśli robisz mecze 5x5 to może być i 34 graczy w kolejce, którzy zostaną rozłożeni najpewniej na 2-3 starcia (zależnie od siły graczy).

Zauważ jeszcze jedną rzecz, która jest silnym hamulcem, a z jakim spotkałem się nieraz. Najsilniejsi gracze na serwerze nie mają z kim walczyć. Choć są motorem serwera, to szybko algorytmy zaczynają ich blokować i przez to cały serwer zwalnia. Musisz premiować ostre bicie w przód, czołówka musi mieć jakieś nagrody za ciągnięcie serwera inaczej opór algorytmów przeciwdziałających "znęcaniu nad słabymi" zatrzyma ich całkowicie w miejscu.

Co z tego o czym mówię wynika? Nie ma algorytmów idealnych Gracze to bandy sk..li które wykorzystają każdą lukę algorytmu by pocisnąć siebie lub znajomych. Ja w jednej zrobiłem krucjatę przeciwko player killerom produkując na uboczu armie podsyłane topowym gildiom do porachunków, a gdy ktoś nieopatrznie zaatakował "słabiaka" by go ogolić potrafił natknąć się na armię, która roznosiła jego wojska w drobny mak Zresztą jeśli zrobisz system gildii czy klanów to dopiero wtedy zobaczysz co to są porządne wojny serwerowe, gdzie potrafią się lać bandy po kilkadziesiąt postaci ze swoimi wojskami. Sam pamiętam absurdy w stylu takim, że siła wojsk biorących udział w starciach przekraczała wszelkie możliwe zakresy liczb dostępne dla bazy i przekręcała przez to liczniki. Ale tam wojska były liczone czasem w miliardach jednostek po każdej stronie konfliktu. Już sama ilość potrafiła przekroczyć typowy zakres int, a co dopiero jeszcze na nich przeprowadzać operacje arytmetyczne konieczne do obliczenia siły oraz wyniku starć.

[ShadowD]

Sporo tego napisałeś i na pewno masz rację, ale nie koniecznie wszystko o czym piszesz powinno się znaleźć w tym temacie - to moja wina nie określiłem o jaką grę chodzi i większość z Was potraktowała to jako grę gdzie mam wpływ na skile czy wynkiki meczu.

Pewnie mało osób wie, że W3 posiada ciekawy dodatek o nazwie DotA, powstaje masę lig gdzie można się zarejestrować i grać. Tutaj gracze wychodzący są mocno karani, a i Teamy są dosyć wyrównane. Wpadłem na pomysł stworzenia czegoś w typie dota-league.com, tylko mam ciekawy pomysł na ulepszenie tego typu gry. Mianowicie tutaj gracze hostują gry, a w moim zamyśle gra jest hostowana automatycznie na specjalnym serwerze, dzięki temu gracze nie narzekają na lagi, a i eliminuje to problem braku hostów, czy ich małych kłamstw jak np. nie są z kolegą w teamie. Dla nie uświadomionych, batelnet musi mięć odblokowany port by móc hostować i mimo to że wydaje się być abstrakcyjnie dla mnie osobiście nie posiadanie własnego IP to nie wszyscy mają taką możliwość, więc średnio co 4 gracz może zakładać grę. Posiadam program do hostowania i startowania gier więc teraz piszę algorytm który umożliwi mi tworzenie wyrównanych teanów.

Niestety nie mam wpływu na cenę, ani żadne inne aspekty gry, gra za każdym startem rozpoczyna się od nowa, więc takie wybicie się w kosmos za pomocą błędnego algorytmu nie jest tak do końca tutaj możliwe. To co osiąkniemy w jednej rozgrywce przepada, jedynie nabity skil zostaje. :-)

@everth - sprawdziłem Twój algorytm i niestety okazuje się błędny w niektórych przypadkach, a tu jeden z nich - http://www.dota-league.pl/index.php?i=5. Zamiana najgorszego gracza z jakimkolwiek jest nie opłacalna, ale zamiana najmocniejszych już tak. Ehhh, sporo nad tym siedziałem i trochę żałuję, że okazał się mieć wady. get[i], opisuje ilość podmian jaka ma być wykonana - mój system zatrzymywania operacji gdy teamy są już najbardziej wyrównane jak się da również zawodzi w tym przypadku więc zostaje ręczne podanie ilości przeniesień.

@thek - myślisz, że Twój sposób na podział graczy jest najlepszym z możliwych?
- W kolejności od najmocniejszego do najsłabszego
- P1 do #1
- P2 do #2
- P3 do #2
- P4 do #1 jeśli #2 ma więcej pkt niż #1 inaczej do #2
- p5-P10 tak jak i P4
- jeśli sloty w jakimś teamie się skończą reszta z automatu do drugiego

Edit:



Udowodnienie błędu algorytmu omawianego kilka sekund wcześniej. Wymiana 4 plajerów znacząco poprawi równowagę... (chyba, że coś źle obliczałem - ręcznie) ;/

Ten post edytował ShadowD 14.08.2010, 00:59:51

[thek]

Nie sądzę, że najlepszym, ale myślę, że jednym z prostszych do implementacji przy zachowaniu w miarę poprawnych wyników. Co do graczy P5-P10 to oczywiście przyporządkowanie do określonej drużyny jest zależne od sumy punktów graczy dotychczas się w nich znajdujących. Tak więc dodawanie gracza następuje zawsze do drużyny z mniejszą liczba punktów. W sytuacji gdy najpierw sortujemy graczy w kolejności malejącej liczby punktów przyporządkowanie pierwszych 3 graczy jak zauważyłeś zapewne jest z automatu zawsze takie samo. Dopiero reszta jest dynamiczna i zgodna z tym co napisałeś jako algorytm. Musisz tylko jedno przewidzieć. To o czym dodałem jako o dodatkowym warunku, który w razie różnicy między drużynami większej niż X% wyrzuca z listy najsilniejszego i tworzy nową listę 10 graczy spośród których próbuje utworzyć drużyny.

Algorytm jest o tyle prosty, że ogranicza się do posortowania i sumowania tak naprawdę oraz IFów sprawdzających sumy i długość drużyn. Obliczenia są bardzo proste i ich wykonanie to będą ułamki sekundy, a jak wspomniałeś liczy się dla Ciebie także optymalizacja. Ten algorytm jest na tyle banalny, że jakakolwiek optymalizacja byłaby wręcz ciężka do przeprowadzenia już. W zasadzie dobrze się zastanowiwszy możesz w prosty sposób, mając posortowaną tablicę, od razu zrobić nie jeden, ale kilka składów.

[ShadowD]

Tutaj można zauważyć błąd jaki występuje, sprawdzałem to kilka razy i raczej błędu nie ma z miej strony. Zamiana P4 (#1) z P5 (#2) która była by w brew algorytmowi znacznie poprawia rozkład pkt... ;/

[thek]

Wymieniłeś nie 4 ale 2. Balans się zwiększył, ale musiałeś analizować kto z kim może zamienić. Możesz zawsze po zakończeniu spróbować zamienić graczy na ostatnich 2 pozycjach w obu drużynach (tam jest najwyższa szansa na trafienie optymalne) na różne kombinacje i przeliczyć punkty (#1-4 <->#2-4, #1-5 <-> #2-5, #1-4 <-> #2-5, #1-5 <-> #2-4), ale to dodatkowe koszty obliczeniowe i musisz się zastanowić czy warto czy nie.


Im więcej zaczniesz grzebać w drużynach tym gorzej. Jeśli przyjmiesz, że możesz tylko jedna zmianę zrobić, to liczba kombinacji sprawdzanych będzie równa Liczba_pól do kwadratu. 2 ostatnie dają 4 wypisane przeze mnie kombinacje, 3 ostatnie - 9, wszystkie - 25 możliwości. Jeśli zechcesz zmieniać 2 i więcej par, to liczba kombinacji wzrośnie wykładniczo. To będzie dalekie od optymalności. Oko na owe 4, góra 9 jeszcze jakoś można będzie przymknąć. Więcej już wprowadzi za duże zamieszanie.

[everth]

Być może ten algorytm powinien (chyba) przybliżyć zbalansowany rozkład:

1. Ustalamy zadowalającą nas w przybliżeniu różnicę pkt. A i B (np. 10%)
2. Sortujemy graczy i przyporządkowujemy ich po kolei do drużyn
3. Liczymy sumę punktów całości
4. Oraz poszczególnych drużyn
5. Liczymy jaki procent całości punktów stanowi różnica punktów drużyn A i B oraz wartość tej różnicy
6. Sprawdzamy z warunkiem 1
7. Jeśli różnica jest dodatnia to będziemy odejmowali z A (w przeciwnym wypadku na odwrót);
8. Znajdujemy w tabeli A (jeśli różnica była dodatnia) najbliższą wartość równą modułowi różnicy;
9. W tabeli B znajdujemy najmniejszą wartość;
10. Zamieniamy je ze sobą
11. Powtarzamy od kroku 4

Algorytm prymitywny i zachłanny - wynik ręcznych zabaw w Excelu. Warto byłoby też ustalić jakiś iteracyjny próg odcięcia żeby nie liczył sobie w nieskończoność (bo np. 10% jest w takiej konfiguracji niemożliwe do osiągnięcia).

PS: Nie chciało mi się już analizować wcześniejszych propozycji więc jak kogoś zdublowałem to proszę wybaczyć.

[thek]

Everth... Algorytm w postaci jaką podałem i jaką policzył autor tematu w pierwszym przejściu, bez jakichkolwiek wymian, pokazał, że różnica punktów w porównaniu do ilości punktów słabszej drużyny to 6%. Gdyby patrzeć na różnicę w porównaniu do całości to spada ona do 3% Jak więc widać, limit 10% bez optymalizacji został osiągnięty. Prościutka matma bez rekurencji czy ogromu iteracji. Sumowanie i parę IFów. Jeśli autor dorzuci wymiany zasugerowane przeze mnie i sprawdzi różnice tych wymian oraz zostawi te kombinację z najmniejszą to będzie zadanie niewiele bardziej obciążające. W zasadzie nastapi tylko wymiana na kilku polach i sumowanie, bo ponowny przydział graczy do drużyn nie jest konieczny. Całość się ograniczy do:
1) Weź policzony układ bazowy
2) Zapisz różnicę drużyn
3) Wymień graczy według kombinacji
4) Wróć do 2 robiąc wszystkie kombinacje wymian
5) Wybierz najmniejszą różnicę. To Twoja kombinacja graczy najlepsza.
6) Koniec

[everth]

@thek - masz jak zwykle rację Śpiący byłem i jak zaznaczyłem nie chciało mi się analizować wpisów z wątku.

Rzeczywiście pierwszy algorytm w zasadzie daje bardzo zbilansowane układy. Poza jednym 'ale' - przy graczach 'odstających' tworzy według mnie mało sensowne układy w których jedna drużyna może grupować równych poziomem a druga - jednego gracza odstającego + same miernoty (dla bilansu). W zasadzie taki gracz będzie musiał ciągle użerać się z miernotami co w końcu doprowadzi przez niego do rzucenia gry (w sumie to też może być metoda bilansowania ). Dlatego też tutaj musi zostać zastosowane jakieś dzielenie graczy na koszyki.

PS: W pierwszym algorytmie chyba wystarczy kontrolować ostatniego gracza przydzielanego - bo to on w zasadzie ustala ostateczny bilans (czyli wybieramy gracza zbliżonego do aktualnej różnicy punktów). Nie wiem jak to wpłynie na dalszy układ w tabeli.