Chess algorithm - Master and student
Creating a reliable online system for enrolling in classes is not an easy task-see Usos during the registration period. We had the opportunity to deal with this problem, and time has shown that the solution proposed by US passed the test.
Our clients include NGOs working for the public good. For the children’s University Foundation, which works with great success to arouse scientific passion among the youngest, we have implemented and implemented an interesting online application. It serves, among other things, to support the student recruitment process.
One of the important goals that we set ourselves at the beginning was to remove some extremely embarrassing bottleneck that existed in the previous solution.
Enrollment at the university was then held according to a simple rule: “who first, the better” (the admission was decided mainly-though not exclusively-by the order of applications). This, in turn, led to a very rapid increase in traffic when the registrations were launched, because the parents of interested candidates were motivated to apply as soon as possible. At that time, the load on the infrastructure increased up to 1,000 times.
It was necessary to fundamentally change this model. In the new scheme, the moment of enrollment would become completely irrelevant, and admission would be decided by the previously adopted rules of preference (for example, preferences for children continuing education) and a draw, which in the appropriate groups would equalize the chances of candidates to study at the University of children.
Such a system would not only be less frustrating, but simply fairer.
In the meantime, a problem has emerged which has proved to be an extraordinary challenge.
In the oldest group of students, in the direction called master and pupil, the participants of the classes no longer follow a uniform program, as in previous years, but choose specializations in which they are particularly interested. The pool of places on individual specializations is-of course-limited.
The parents of the candidates at the time of the application of their child had to decide what specializations for their child they prefer, and the proposed system – to make enrolments taking into account these preferences and all relevant conditions.
Only that the relevant conditions were numerous and unusual, which consequently made it impossible to apply the algorithms commonly used in such cases.
In fact, students in the master and student majors choose two specializations: one for the first semester and the other for the next. The specializations have to be different, otherwise they would go through the same program twice.
This condition eliminated the Gale-Shapley algorithm used for combining bi-directional preferences, also known as the “stable marriage algorithm”, because it does not allow “bigamy”, that is, assigning two choices to one participant.
Most of the known methods of covering the collection, that is, searching for such assignments (students for specialization), which guarantee the maximum number of records, also did not fit this problem, because these, in turn, do not allow taking into account a number of preferences and possible preferences.
Worse, it happens that parents do not make timely payments for accepted applications, which causes some places to slow down. Our algorithm had to work correctly also in subsequent cycles, where it was supposed to qualify people from the reserve list.
In addition, some specializations occur only in one semester, and the number of places may change during recruitment, as the university tries to respond to increased interest. Consequently, the number of complications the new algorithm had to withstand was overwhelming.
The salvation was the creative use of a method typical rather for the search algorithms for optimal movement in chess.
Such algorithms analyze the various gameplay options and select the move that guarantees the best state of the board after a series of consecutive moves.
Our chessboard was the tables accepted for each specialization.
Thus, we made assignments in different variants, performing “several moves forward”, and then evaluated the state of our “chessboard” in each case. Then we chose the movement (one) best negotiating. Then we repeated the whole operation until there were no more permitted “movements”.
We could evaluate the status of tables after each set of assignments according to freely configured criteria, which gave us the opportunity to choose the validity of the corresponding rules. The algorithm worked quickly and accurately. We could also change the “depth of analysis” (how many moves forward) and repeat the operation in subsequent payment cycles with all the rules.
The solution to the problem was so non-trivial that even testing it proved to be a demanding task. Creating conditions that would be challenging for this algorithm was no small puzzle.
Algorithm in combat
Our unconventional approach has been implemented and launched. It underwent baptism of fire under difficult conditions: in four cities, within several payment cycles and was subjected to a severe test in the form of numerous changes “in flight”, increasing the pool and applying manual corrections in case of erroneous applications. These tests turned out to be defensive.
In the end, our chess algorithm was successfully verified in the real recruitment process, and young master and student students in the 2016/2017 school year for the first time were assigned to their favorite specialties in a way that was comfortable for parents and safe for the IT infrastructure.
Konrad J. Nowak