fbpx

Matematyka w koszykówce: co łączy Chrisa Paula i Tima Duncana

23

Dziś wpis gościnny, taki w niecodziennym stylu. Spróbuję go odrobinę “zdekodować” ale nie chcę naruszać głównego przesłania. Miłej lektury:

Kto studiował, ten wie – nie wszystkie zajęcia są ciekawe, nie na każdy wykład się chodzi, a zaliczenia nie zawsze bywają przyjemne. W przypadku moim i grupy znajomych, podczas pracy nad wspólnym projektem, żadna z powyższych rzeczy nie okazała się prawdą. Dlaczego? Między innymi dzięki koszykówce. Wiecie jak to jest – nawet gdy robisz rzeczy mało ciekawe, to gdy odnajdziesz w nich pierwiastek czegoś, co jest interesujące, od razu pracujesz wydajniej. W naszym przypadku do rzeczy ciekawych dołożyliśmy koszykówkę, więc pewnie domyślacie się, jaki był owoc takich działań.

Wyszukiwanie społeczności nachodzących w sieciach społecznościowych

Projekt, nad którym pracowaliśmy, nosił tytuł „Wyszukiwanie społeczności nachodzących w sieciach społecznościowych”. Jak zdefiniować taką sieć? Odpalcie Facebooka – voilà, właśnie znaleźliście się w ogromnej sieci społecznościowej. Naszym zadaniem było wyszukiwanie wśród takiej sieci użytkowników, z którymi jesteście związani mocniej niż z innymi. Naszym celem było przebadanie różnych metod do tego służących. Po co jednak robić takie rzeczy? W skali biznesowej zastosowanie wyszukiwania społeczności bywa niezwykle szerokie. Wyobraźcie sobie, że trójka z waszych znajomych z cotygodniowej koszykówki zakupiło najnowszą książkę Admina, a nasz algorytm połączył całą waszą grupę amatorów basketu jako jedną społeczność. Wtedy Ci z was, którzy książki jeszcze nie kupili (a powinni), dostaną reklamę o tego typu okazji.

No dobrze, ale gdzie w tym wszystkim koszykówka? Czas przejść do sedna sprawy. Otóż nasi dobrzy znajomi z parkietów NBA też mogą stworzyć graf, który w swej strukturze jest rozbudowany równie mocno jak słynne trójkąty Phila Jacksona. Tutaj warto opisać, czym jest graf, lecz może dam wam chwilę, by samemu to przemyśleć i posłużę się malutkim fragmentem naszego projektu.

Czym jest graf

Tak, to jest graf – kropki i kreski, proste. Współcześni matematycy i informatycy wariują na widok takiej konstrukcji. Kropka (w terminologii wierzchołek) połączona jest z inną poprzez krawędź wtedy, gdy łączy je jakaś relacja. Liczba problemów badanych na grafach (znacznie, znacznie większych niż prezentowany przykład) dorównuje liczbie wszystkich kochanek punktów zdobytych przez Wilta Chamberlaina. W naszym przypadku w grafie poszukiwaliśmy nachodzących społeczności, a więc jak wspomniałem wcześniej – grup ściśle ze sobą związanych. Nachodzących, a więc takich, w których jeden koszykarz może zostać przypisany do więcej niż jednej grupy. Jedyną informacją, którą posiadaliśmy były „kropki i kreski” – żadnych dodatkowych wiadomości na temat wspólnych treningów co wtorek czy niedzielnego golfa.

Udało się wam wywnioskować na podstawie poprzedniego rysunku co „połączyło” koszykarzy NBA? Zależnością tą była wspólna gra w jednym klubie w przynajmniej jednym meczu. Udało nam się zdobyć dane na temat 4800 koszykarzy, którzy postawili stopę na parkietach NBA przez 70 lat jej istnienia. Zbiór krawędzi oparty na wspólnej grze w jednym klubie liczył ponad 146 tysięcy elementów. Skąd można zdobyć takie dane? Będąc wystarczająco wytrwałym można je przepisać z portalu basketball-reference.com. Posiadając środki informatyczne można „zaprząc” do tej pracy robota. Naprawdę, zarządzający tą stroną mają tam wszystko i jestem pewien, że na bazie tych danych powstają te przeróżne statystyki o liczbie trafionych layupów lewą ręką po uprzednim koźle prawą pomiędzy nogami.

Liczę, że przynajmniej jeden wytrwały czytelnik dotarł do tego momentu, gdyż nadszedł czas przedstawić wyniki naszej pracy. Spójrzcie na grafy, odnajdźcie na nich znane nazwiska i spróbujcie zgadnąć jaki zbiór koszykarzy przedstawia dany obrazek? Pod nazwiskiem umieszczamy numery społeczności, w których danego zawodnika umieścił prezentowany algorytm. Na koniec artykułu zdradzimy wam odpowiedzi, na razie macie czas, aby się zastanowić.

1/ Algorytm Girvan-Newman (z modyfikacją CONGA)

Metoda ta dla badanego problemu jest jak layup dla każdego adepta koszykówki – od tego zaczyna się większość prac w tej tematyce. Niestety jego działanie można porównać do tej kontry:

Algorytm działa bardzo długo, ponieważ liczy on w każdym kroku, jak dużo krawędzi trzeba przejść od jednego wierzchołka do wszystkich pozostałych. W przypadku Russella Westbrooka zapyta on zarówno jak daleko od niego jest James Harden jak i Devin Booker, z którym przecież nigdy nie zagrał w jednej drużynie. I tak co krok algorytmu… Przedstawiony graf jest bardzo mały, jednak już dla około 500 wierzchołków czas trwania obliczeń zbliża się do czasu, jaki Trae Young przetrzymuje gałę w ciągu meczu.

Zerknijmy na Russa raz jeszcze – w jego przypadku algorytm zwrócił aż 3 różne społeczności. W jednej umieścił RW#0 z paczką z Golden State, w drugiej widzimy zwrot w stronę ekipy Houston Rockets (czasy obecne) a w trzeciej wylądował on ze znajomymi z OKC. Jak widać, podobnie na boisku – wszystko kręci się wokół Russa. Porównując ten algorytm do koszykarza, wskazałbym zawodnika niezwykle inteligentnego, przewidującego każdy ruch przeciwnika, dobrze analizującego taktykę. Zawodnik ten ma jednak podstawowy problem – nie potrafi zareagować w odpowiednim czasie. Zna każdą zagrywkę swoją i przeciwnika, lecz jest za wolny, aby podołać tempu meczowemu. Dobry do treningu, jednak gdy przychodzą prawdziwe wyzwania, ląduje na ławce.

2/ Algorytm LPA

Duży graf, bo i czas działania w tym wypadku zdecydowanie krótszy. Chodzą plotki, iż w wyniku szybkości działania algorytmu Coby White poczuł wiatr na swej bujnej czuprynie w swym domu w Chicago. O ile wcześniej mówiliśmy o najwolniejszej kontrze świata, tak w tym wypadku możemy posłużyć się tym przykładem:

Skąd ta szybkość? Od poprzednika algorytm ten różni się podejściem – tam wychodziliśmy od ogółu, a więc wszystkich koszykarzy NBA, tutaj na początku każdy z nich stanowi oddzielną społeczność. Od jednostek przechodzimy do całości, szukając osób dominujących w danej grupie. Efekt czasowy jest piorunujący, jakość wyniku prezentujemy na rysunku powyżej. Kolory może ładne, spójrzmy jednak na wyniki bardziej szczegółowo.

Obrazek w skali mikro to zadanie w stylu „znajdź szczegóły”. W jednej społeczności, widzimy tutaj dwóch koszykarzy związanych z naszym rodzimym krajem. Zostawimy wam to jako kolejną zagadkę do kolekcji.

Wymienione wcześniej zalety to jednak nie wszystko – algorytm ten można uruchomić na kilku wątkach równolegle, a więc jeszcze bardziej poprawić czas działania. Koszykarska analogia – Steph Curry, a więc szybki cyngiel i duża skuteczność, nawet z największej odległości. Dodając operacje na wspomnianych wątkach dorzucacie na boisko jeszcze Della i Setha Curry i robicie zawody za trzy rodem z charytatywnego konkursu podczas All-Star Game – z taką pomocą Steph na pewno zdołałby zgarnąć więcej pieniędzy.

3/ Algorytm OCDCLE

Kolejny z algorytmów, dla którego praca zaczyna się od pojedynczych koszykarzy. Co prawda tutaj nie dobiegniemy już w 3 susach pod samą obręcz, aby zgarnąć wynik, jednak nasza kontra może okazać się równie zabójcza. Ta metoda została stworzona z myślą o zbiorowej koszykówce. Pozostałe, aby uzyskać efekt jednej osoby w kilku grupach musiały być przez nas modyfikowane. Tutaj autorzy od razu pomyśleli o koszykarskich obieżyświatach.

W tym wypadku możemy zerknąć w stronę Shaquille’a O’Neala. W swojej karierze zwiedził on dużo klubów, co ma też odzwierciedlenie w uzyskanym wyniku. Widzimy, iż z jednej strony został on umieszczony w grupie z Los Angeles Lakers, z którymi chyba utożsamiany jest najmocniej. Druga grupa to dalsze wojaże, a więc między innymi przygoda z Boston Celtics czy Miami Heat. Opisana metoda zaoferowała nam również miarę, która była w stanie w jakiś matematyczny sposób oceniać grafy. Stąd też analogia koszykarska tego algorytmu jako poukładanego playmakera, który jest w stanie regulować tempo gry, dostrzegać kolegów na pozycjach i kreować liderów w każdym meczu.

4/ Algorytm Louvain

Dokonując wyboru tej metody zachowaliśmy się trochę jak skaut poszukujący talentów w drugiej rundzie draftu. Nie mieliśmy za dużo informacji o zawodniku, ledwie kilka wzmianek, niektóre mówiące o tym, że prace nad jego rozwojem ciągle trwają. Zdecydowaliśmy się postawić na tę kartę, w końcu dużo nie traciliśmy, a zysk mógł być ogromny.

Algorytm działa zachłannie, czyli mówiąc w skrócie, co krok wybiera możliwość, która w danej chwili wydaje mu się najlepsza, nie patrząc na żadne dalekosiężne konsekwencje. Właśnie w ten sposób powstał graf prezentowany powyżej. Odszukajcie na nim Kawhi Leonarda (podpowiedź: blisko zbiorów o numerach 7 i 8). Widzimy, iż opracowana metoda dopasowała Kawhi do dwóch grup – pierwsza z nich wyraźnie koncentruje się wokół jego sezonów w barwach San Antonio Spurs, druga natomiast wskazuje na ostatni sezon mistrzowski w barwach Toronto Raptors. Koledzy z Clippers nie doczekali się jeszcze u nas wspólnego zdjęcia z Kawhi.

Trzymając się przytoczonego porównania możemy stwierdzić, że nasz pick został dobrze spożytkowany. Szukając koszykarskiej analogii wśród zawodników, wskażemy na młodego gracza, który już teraz wyróżnia się boiskową inteligencją, a także walorami szybkościowymi. Może nie był on czołowym prospektem w swoim roczniku, jednak ciągle się rozwija i warto patrzeć na dalsze losy jego kariery.

Podsumowując – praca nad tym projektem to była dla nas naprawdę dobra zabawa. Co prawda z czasem przekonaliśmy się, że nie musieliśmy wcale wybierać aż 4 algorytmów, bo z jednym tylko wyborem mielibyśmy równie dużo pracy. W naszym podejściu wybraliśmy jednak gracza czytającego grę (lecz powolnego), strzelca z niezwykle szybki i celnym rzutem, inteligentnego playmakera i zdolnego zawodnika z draftu. Dorzućmy im do piątki gracza pokroju Kawhi Leonarda i idziemy na mistrza, hehe.

Liczymy, że ktoś wytrwał do tego momentu, a gdyby zainteresował go opis problemu odsyłamy tutaj: https://github.com/Sliwson/community-detection. Tam również można znaleźć nasze profile, gdyby ktoś chciał porozmawiać dłużej o grafach bądź o koszykówce. ‘I love this game’ – bez wątpienia to hasło łączy tutaj nas wszystkich, a jak widać, pierwiastek koszykówki można umieścić również i w informatyce.

[Irek Stanicki]

Grafy, które zaprezentowaliśmy to:

  1. Uczestnicy All-Star Game z lat 2019-2020
  2. Wszyscy zawodnicy NBA w historii z bazy basketball-reference (wypatrzyliście Macieja Lampe i Qyntela Woodsa?)
  3. Top 50 strzelców NBA
  4. Uczestnicy All-Star Game z lat 2011-2020

Ostatnie Wpisy

23 comments

  1. Array ( )
    Odpowiedz

    Pomysł bardzo ciekawy . Co prawda ciężko coś wnioskować na podstawie tylko boiskowych animozji , bo dochodzą jeszcze te z “łodzi bananowej “. Jednak w rezultacie i tak wyraźnie widać kto z kim przez lata grał . Mega ciekawi mnie też , czy otrzymaliście wnioski / przypuszczenia kto z kim w przyszłości może razem grać albo kto dołączy gdzie .

    (9)
  2. Array ( )
    Odpowiedz

    O cholera. Toż to szok. I pomyśleć że kiedyś człowiek cieszył się jak znalazl klasyfikacje pierwszej 10 w najważniejszych statystykach ligi.

    (3)
  3. Array ( )
    Odpowiedz

    Fajne.

    Jeszcze fajniejsze byłoby gdybyście na tapetę wzięli mistrzowskie ekipy. Jaki gracz jest potrzebny statystycznie do wygrania miska.

    (0)
  4. Array ( )
    Odpowiedz

    Zabierałem się za czytanie ale…nieee. Sam jestem trenerem ale chyba w nba pracy nie znajdę hehe bo to jednak dla mnie za dużo.

    (6)
  5. Array ( )
    Odpowiedz

    ej serio wy juz nie macie czego wrzucac XD
    Ten artykul jest tak glupi, nudny i bez sensu, ze tylko morda admina jest chyba gorsza.
    Na bank nie dodasz bartuś bo sie boisz hejtu panie wielki pisarzu. W sumie kupie ksiazke po to zeby ja spalic XD

    (-14)
    • Array ( [0] => administrator )
      Zdjęcie profilowe admin

      zapraszam do zamówień! wątpię żebyś kupił książkę, tacy jak Ty wiele gadają, a niewiele robią, gdyby robili nie mieliby czasu na bezsensowny hejt

      (23)
  6. Array ( )
    Odpowiedz

    Bratek książka nareszcie dotarła za co dzięki ale obiecałeś do każdego preorder “niespodziankę” no niestety w mojej przesyłce nic nie było…

    (0)
    • Array ( [0] => administrator )
      Zdjęcie profilowe admin

      mieliśmy problemy z systemem, błędy nowicjusza, kiedy ogarnąłem przesyłki, które jeszcze były do wysłania, “niespodzianki” dawno się skończyły
      zamówiłem nową partię, więc jeśli mogę Ci zrekompensować poślizg, napisz na sklep 🙂 dzięki! póki co przyjemnej lektury

      (3)

Gwiazdy Basketu