Algorytm Szachowy- Mistrz i Uczeń

Stworzenie niezawodnego systemu online do zapisów na zajęcia nie jest prostym zadaniem - patrz: USOS w okresie rejestracji. My mieliśmy okazję się z zmierzyć z tym problemem, a czas pokazał, że zaproponowane przez nas rozwiązanie zdało egzamin.

Wśród naszych klientów są organizacje pozarządowe działające dla dobra publicznego. Dla Fundacji Uniwersytet Dzieci, która zajmuje się z wielkimi sukcesami rozbudzaniem naukowej pasji wśród najmłodszych, zrealizowaliśmy i wdrożyliśmy interesującą aplikację działającą online. Służy ona, między innymi, do obsługi procesu rekrutacji studentów.

Jednym z istotnych celów, które sobie na początku postawiliśmy, było usunięcie pewnego niezwykle kłopotliwego wąskiego gardła, które występowało w poprzednim rozwiązaniu.

Zapisy na uniwersytet odbywały się wówczas według prostej zasady: „kto pierwszy, ten lepszy” (o przyjęciu decydowała głównie – choć niewyłącznie – kolejność zgłoszeń). To z kolei powodowało, że w momencie uruchomienia zapisów, następował bardzo gwałtowny wzrost ruchu, bo rodzice zainteresowanych kandydatów zmotywowani byli, by dokonać zgłoszenia w najwcześniejszym możliwym terminie. Obciążenie infrastruktury wzrastało wówczas nawet tysiąckrotnie.

Konieczna była gruntowna zmiana tego modelu. W nowym schemacie, moment zapisu stawałby się zupełnie nieistotny, a o przyjęciu miałyby decydować przyjęte wcześniej zasady uprzywilejowania (np. preferencje dla dzieci kontynuujących naukę) oraz losowanie, które w odpowiednich grupach zrównywałoby szanse kandydatów na studiowanie na Uniwersytecie Dzieci.

System taki byłby nie tylko mniej frustrujący, ale zwyczajnie – sprawiedliwszy.

Tymczasem ujawnił się problem, który w tej realizacji okazał się nadzwyczajnym wyzwaniem.

W najstarszej grupie studentów, na kierunku nazywanym Mistrz i Uczeń, uczestnicy zajęć nie podążają już jednolitym programem, jak w poprzednich rocznikach, ale wybierają sobie specjalizacje, którymi są szczególnie zainteresowani. Pula miejsc na poszczególnych specjalizacjach jest – naturalnie – ograniczona.

Rodzice kandydatów w momencie zgłoszenia swojego dziecka decydować mieli, jakie specjalizacje dla swojego dziecka preferują, a projektowany system – dokonywać zapisów z uwzględnieniem tych preferencji i wszystkich stosownych warunków.

Tyle, że owe stosowne warunki były liczne i nietypowe, co w konsekwencji uniemożliwiło zastosowanie powszechnie używanych w takich przypadkach algorytmów.

Czar par

Studenci na kierunku Mistrz i Uczeń wybierają w istocie dwie specjalizacje: jedną na pierwszy semestr i drugą na kolejny. Specjalizacje muszą być różne, bo w przeciwnym razie przerabialiby ten sam program dwukrotnie.

Ten warunek wyeliminował algorytm Gale’a-Shapleya używany w przypadku łączenia dwukierunkowych preferencji, znany też jako „algorytm stabilnych małżeństw”, bo ten nie dopuszcza „bigamii” czyli przypisywania dwóch wyborów do jednego uczestnika.

Większość znanych metod pokrywania zbioru, czyli poszukiwania takich przypisań (studentów do specjalizacji), które gwarantują maksymalną liczbę zapisów także nie nadawało się do tego problemu, bo te z kolei nie pozwalają na uwzględnienie szeregu preferencji i ewentualnych uprzywilejowań.

Co gorsza, zdarza się, że rodzice nie dokonują terminowych wpłat za zaakceptowane zgłoszenia, co powoduje, że pewne miejsca się zwalniają. Nasz algorytm musiał poprawnie działać również w kolejnych cyklach, gdzie miał kwalifikować osoby z listy rezerwowej.

Na dodatek, niektóre specjalizacje występują wyłącznie w jednym semestrze, a ilość miejsc może się zmieniać w trakcie rekrutacji, bo uniwersytet stara się reagować na zwiększone zainteresowanie. W konsekwencji, liczba komplikacji, na które musiał być odporny nowy algorytm, była przygniatająca.

Poziom piona

Wybawieniem okazało się twórcze zastosowanie sposobu typowego raczej dla algorytmów poszukiwania optymalnego ruchu w szachach.

Algorytmy takie analizują rozmaite warianty rozgrywki i wybierają posunięcie, które gwarantuje najlepszy stan planszy po szeregu kolejnych ruchów.

Naszą szachownicą były tabele przyjętych na poszczególne specjalizacje.

Dokonywaliśmy zatem przypisań w różnych wariantach, wykonując „kilka posunięć w przód”, a następnie ocenialiśmy stan naszej „szachownicy” w każdym przypadku. Wtedy wybieraliśmy ruch (jeden) najlepiej rokujący. Potem powtarzaliśmy całą operację do momentu, kiedy nie było już żadnych dozwolonych „ruchów”.

Stan tabel po każdym szeregu przypisań mogliśmy oceniać według swobodnie konfigurowanych kryteriów, co dawało nam możliwość wyboru ważności odpowiednich zasad. Algorytm działał szybko i precyzyjnie. Mogliśmy również zmieniać „głębokość analizy” (ile ruchów w przód) i powtarzać operację w kolejnych cyklach płatności z zachowaniem wszystkich zasad.

Rozwiązanie problemu było na tyle nietrywialne, że również jego przetestowanie okazało się wymagającym zadaniem. Stworzenie warunków, które dla tego algorytmu byłyby wyzwaniem, stanowiło nie lada łamigłówkę.

Algorytm w boju

Nasze nieszablonowe podejście zostało zaimplementowane i uruchomione. Przeszło chrzest bojowy w niełatwych warunkach: w czterech miastach, w ramach kilku cykli płatności i poddane zostało ciężkiej próbie w postaci licznych zmian „w locie”, powiększania puli i nanoszenia ręcznych poprawek w przypadku omyłkowych zgłoszeń. Z tych testów wyszło obronną ręką.

Ostatecznie, nasz algorytm szachowy został skutecznie zweryfikowany w prawdziwym procesie rekrutacyjnym, a młodzi studenci kierunku Mistrz i Uczeń w roku szkolnym 2016/2017 po raz pierwszy zostali przypisani do swoich ulubionych specjalizacji w sposób, który był komfortowy dla rodziców i bezpieczny dla infrastruktury IT.

Konrad J. Nowak

Software Architect