Combinatorial Optimization & Constraint Programming

Declarative Visualization Framework for Comet

2007

This piece of software provides a specification language for visualizing the behavior of metaheuristics implemented in Comet. One of the layers of our visualization architecture provides a declarative graphics toolkit which is made possible thanks to the incremental variables and invariants of Comet. The model-based high-level specification language is translated into widgets of the declarative graphics toolkit. The user just specifies what where and how information has to be displayed and the system takes care of updating the display whenever a variable of the model is changed by a move performed by the metaheuristic. More info can be found in our CP2007 paper. Download it (soon) together with the Comet compiler and runtime.

PyGecode and pyExplorer

2006

This is a preliminary version of a Python wrapper around Gecode. The wrapper is based on ctypes and a C wrapper around the C++ API of Gecode. The package also includes a python based scriptable tree search explorer. This explorer can also be used on top of pure C++ Gecode programs (your own Space specialization). The wrapper was started together with the members of logilab during a PyPy-Oz workshop I organized in Louvain-la-Neuve in 2004. Download it here. Please do not ask questions about this on the Gecode mailing list; the Gecode team has nothing to do with this completely unsupported piece of software.

CP(Graph) implementation over Gecode 1.3

2005-2006

This is the code with which we experimented a common API and several implementations/reformulations of a graph interval domain variable for constraint programming. The code also contains an implementation of the path and shorter path constraints (see my thesis for more details).

This code is a little outdated and is not maintained anymore. The Gecode API has been extended with support for variables deltas (through deamons ŕ la AC5 and AC2001), which now allows to break the main bottleneck in our implementation. Another piece of code of interest if you would like to pursue this work is the graph data structure with support for dynamic update of some properties implemented by Xavier Lorca and available under a BSD licence.

It might however still be useful for solving constrained path finding problems (shortest simple path with mandatory nodes and pairs of mutually exclusive nodes). Note that the results we published in CP05 on that problem were obtained with an more naive filtering algorithm implemented in Oz. As of CP2007, that CP(Graph) Gecode code still runs with state of the art timings on the constrained shortest path instances we obtained from metabolic network analyses.

Stéphane Zampelli uses some parts of this code in his (sub)graph isomorphism algorithm which outperforms all previous algorithms for this problem on various classes of instances.

Download it here.

Teaching Artifical Intelligence

This section lists some of the software I implemented to support the course INGI2261 at UCLouvain during the period I TA'ed it (2003-2006). The IA part is based on AIMA.

Tikal, a multi-user networked board game

2005

This game was implemented as a framework for an AI programming contest for the UCL course Ingi2261 in 2004. Check the game rules and the README. It is a game server with a GUI display. The display also allows to play and host a game at the same time. Finally, a remote graphical client also exists. The students had to implement a game playing agent. The agent which won the competition was authored by Cédric Cornez & François Zoetardt, it is based on alpha-beta search on a subset of the possible actions with a nice heuristic. This agent is included with the game. The main program is about 3000 lines of Python code and should run with Python 2.3 and higher. The Twisted python package is used for its XMLRPC/Tk reactor. Download

Rush Hour, a single user puzzle

2004

The application is launched via RushGUI.py. It allows to edit puzzles, solve them by hand or using various search algorithms. Replays are also supported. This is done in less than a thousand lines of Python code. Students were expected to come up with an interresting heuristic evaluation function for A*. You need python-imaging and python-imaging-tk. We also borrowed some files from the AIMA library. Last time I checked, it worked with python2.5. Download

Python Course

2003-2006

I wrote a Python course with Yves Deville. The idea is to interactively introduce the students to the main concepts of the language, with some exercices (most importantly on higher order programming) then move on to exciting mini-projects such as a GUI calculator (Tkinter), an online calculator (with an intro to HTTP, HTML and CGI), a web scraper (urllib and optionally HTMLParser), and database integration (mysqllib with a warning about SQL injection). I gave this 2 day course at TechnoFutur 3 six times in 2004 and 2005, the feedback was excellent except the students wished the course could continue over a couple more days to explore more mini-projects. The course material was also available to the students of Ingi2261 ( AI 101 course at UCL ) since the assignments and programming contests were done in Python. I had the opportunity to lecture an extended version of this course over 5 days in French at IFI in Hanoi.

The slides are available in PDF. The main part (Python language) is mainly based on the python tutorial. It is in english. The remaining sections are in french as they were originally made for the IFI.

The snake game

2003

This is an experiment on the value of step-wise evolution of a short program in order to introduce new software concepts (e.g. classes) and demonstrate their strengths and pitfalls. The code starts with a flat script to implement a playable snake game, the game is then upgraded to two players on a single keyboard thanks to classes. The next step would have been to make the game playable on internet, add several lives per player etc... Code is GPL, comments and function names are in French (If you continue this please send me a copy).

1. Snake1.py
   A 150 line flat script implementation of a single player snake game. This illustrates basic Tkinter concepts: the Canvas and Label widgets, the mainloop and the after method. Note the use of a list of pending moves which provides excellent playability despite the low refresh rate.
2. Snake2.py
   This version illustrates how a class can be used for grouping the code reponsible for the management of the snake: change its direction, make it walk one step.
3. Snake3.py
   Now that the snake is a separate entity in the program, we can place several snakes on the playing board. This version shows how one can modify the main loop to take up to two snakes into account (including their collision). Player 1 plays with the arrow keys, player 2 plays with qsdz (azerty keyboard).
4. Snake4.py
   Players have their own class, with their preferences. Not much functionality is added (apart from setting the score of the player terminating the game to 0).