Home

Welcome to the algobattle wiki!

Use the side bar to navigate through topics such as how to create your own problem files and on the functionality of the implemented battle wrappers.

A lot of this project is still undocumented. If you are interested in a topic, whether specific or broad, that is not yet documented, please let us know.

Please note that version 4.0.0 is currently in development which will restructure and simplify the code quite significantly, in the hope to make it even easier for students and yourself to use the framework. Along with it, we will overhaul and extend the documentation significantly. If you are eager to try it out already, you can check out the 4.0.0 Release Candidate. Note that the minimum python version required to run algobattle 4.0.0 is 3.11. The core concept remains the same.

What is the core concept of this project?

You are looking at code that was developed for use in an academic context, primarily in higher education. This framework is supposed to let you hold a lab course without having to do the heavy lifting of implementing the core logic of it. This means that you can focus on the kinds of problems that you want your students to solve.

The basic idea is quite simple. Complexity theory tells us that (we assume that) some problems have a bad worst-case runtime complexity, be it of a high polynomial order in the size of the input or even of non-polynomial complexity. In practice, these theoretically hard problems are often solved anyway, and much quicker than one might assume. The students are thus tasked with finding out what the hard core of a problem is. This task is to be solved from two points of view. The first one is to design an instance of a fixed size that is deemed hard to solve. The other point of view is to design a solver that is capable of solving hard instances quickly. Every groups solver is then pitched against each other groups generator.

Points are awarded in a battle between two teams in regards to how much better they are able to solve a problem than another team. This encourages optimizing both the generator and the solver.

As the organizer of the lab course, your part in preparing such a battle is in designing such a problem. This means specifying the problem itself, how it is supposed to be encoded and how a solution for an instance can be verified (we recommend also writing tests). We have published some of the problems that we have used in our own lab course. You can find them in the algobattle-problems repository. Feel free to inspect, play around and use them for your own teaching.

You then pose such a problem to your students. The students can use whatever programming language, libraries or other tools they want, as long as they can build a docker container around them. This means that you do not have to worry about installing anything on your host machine other than docker and python in order to run this lab course.

Since the framework only expects a problem to implement a parser and a verifier that reports back whether an instance or solution is valid, the range of problems goes far beyond basic text-based problem instances. As long as you have the expertise to formulate a parser and verifier (and specify the encoding and decoding) for it, nothing is stopping you from using data streams as input and output for generators and solvers, e.g. for solving problems on multimedia input.

Follow the side bar to dive deeper into specific topics, such as designing a concrete problem. If you need any help, feel free to contact us.