Player modeling in TORCS exploiting SVMs and GPUs parallelism

Part 1: Project profile

Project name

Player modeling in TORCS exploiting SVMs and GPUs parallelism

Project short description

This project is aimed at building a TORCS' driving agent, using SVMs (Support Vector Machines) as the main Machine Learning algorithm. This agent (also called Bot) must be able to drive versus other agents, with comparable or better performances. To fulfill this achievement, and to be able to train SVMs in feasible time, this work will initially focuses on using the CUDA architecture to rewrite and optimize a well-known SVM Toolkit, LibSVM.

Dates

Start date: ~2008/03/01

End date: ~2009/03/01

Website(s)

http://cig.dei.polimi.it

People involved

Project head(s)

P. L. Lanzi - User:PierLucaLanzi

D. Loiacono - User:DanieleLoiacono

Other Politecnico di Milano people

None.

Students currently working on the project

Fabrizio Bonfanti - User:FabrizioBonfanti

Students who worked on the project in the past

None.

External personnel

None.

Laboratory work and risk analysis

This is meant to be a software project, and all required hardware is used remotely, so no laboratory work is expected. No risks are associated to this project, hopefully.

Part 2: Project description

Currently, my CUDA implementation is being developed, and has already survived lots of problems. Read on for a small briefing of the most important milestones.

The really first implementation

This implementation was the first funcional one, it supported c-SVM and was tested against a good package of datasets.

Pros:

• Same results (nu, rho, sv, bsv, prediction %) compared to LibSVM

Cons:

• The Q matrix (#data x #data) was completely calculated before the real training
  • Memory cost
  • Speed cost
  • Could handle problems with less than ~7000 vectors
• Slower than LibSVM on nearly all the training datasets

The second implementation

Since results weren't as good as I expected, I decided to take another direction, effectively trashing the old work and starting fron scratch.

Pros:

• New algorithm, focalised on c-SVM without any LibSVM's optimization
• Nearly same results (nu, rho, sv, bsv, prediction %) compared to LibSVM
• Lines of Q are now calculated on demand
  • Freed a lot of memory
• Can solve problems of nearly any cardinality (limited by the GPU memory, however the biggest correctly solved was ~60000 vectors)
• Reached 3x speedup on a pair of dataset, still slower than 1x on the vast majority
• Tested on more datasets

Cons:

• Necessity of some kind of Q-caching, not easy to do on this implementation
• Time depends heavily on the number of iterations, since rows are calculated on demand
• Why the speedup is so variable was still not clear

The third implementation

My assignment changed, and the implementation of epsilon-SVR was required too. Looking at the math behind the two earlier implementations, I saw that there really weren't a lot of conceptual differences, so I decided to return back on the first implementation, adding the features that were working on the second one. Speedup is very variable, but it seems that this implementation works better with big problems. I suspect that the major point of speedup is about calculate the lines of Q, so problems with higher cardinality gain effectively a lot on this phase.

Pros:

• epsilon-SVR ossibility added to the c-SVC implementation
• Same results (nu, rho, sv, bsv, prediction %) compared to LibSVM
• Lines of Q are now calculated on demand
  • Freed a lot of memory
• Lines of Q are now cached
  • Speed gain
• Can solve problems of nearly any cardinality (limited by the GPU memory, however the biggest correctly solved was ~60000 vectors)
• Reached 4x speedup on a pair of dataset, still slower than 1x on the smaller problems
• Tested on more and more datasets

Cons:

• Some point of the algorithm are nearly blocking
• Overlaps of data transfer and CUDA executions are not exploited
  • The algorithm itself is very serial
  • Caching needs to serialize the lookup phase (CPU) and the calculus (GPU, if required)
• Time depends heavily on the number of iterations, since rows are calculated on demand

Now

Now, I'm working again on the last implementation. I'm testing times/performances on a lot of datasets, and I'm also studying how the SVM's parameters can change the overall performance.

I'm also looking if parallelizing multiple SVMs is feasible. My guess is that it is possible, but looking at the nature of the algorithm, I think the performance gain wouldn't be so high.

Part 3: Useful links

TORCS - http://torcs.sourceforge.net/

LibSVM - http://www.csie.ntu.edu.tw/~cjlin/libsvm/

CUDA - http://www.nvidia.com/object/cuda_home.html