veyepar: Solving an NP-Hard Problem for Fun and Profit

Author(s):	Raymond Chandler III
Location	Cartoon 2
Date	jul Sun 29	Days Raw Files
Start	16:15	First Raw Start	16:00
Duration	0:30:0	Offset	0:14:24
End	16:45	Last Raw End	16:47
Chapters	00:00 0:15:26
Total cuts_time	28 min.

https://pyohio.org/2018/schedule/presentation/24/
raw-playlist raw-mp4-playlist encoded-files-playlist host archive tweet mp4 svg png

assets release.pdf Solving_an_NPHard_Problem_for_Fun_and_Profit.json
logs
Admin: episode episode list cut list raw files day marks day marks day image_files

State:

Locked:

clear this to unlock

Locked by:

user/process that locked.

Start:

initially scheduled time from master, adjusted to match reality

Duration:

length in hh:mm:ss

Name:

Video Title (shows in video search results)

Emails:

email(s) of the presenter(s)

Released:

has someone authorised pubication

Normalise:

Channelcopy:

m=mono, 01=copy left to right, 10=right to left, 00=ignore.

Thumbnail:

filename.png

Description:

markdown

Last year I was given a task by the publishers of the CATAN board game. They wanted a tournament management tool that could help them organize, run, seat, and rank players in their world championships and several local qualifying events around the world. Most of the application was straightforward but they also had a very specific seating problem, and after doing some investigation I learned that their specific requirements made the task an NP-hard problem. The problem is this:

Given some number of players. Generate a number of tables where each table has 4 or 3 seats. Then from round to round seat players in such a way so that A) no player plays in the same seating position they previously sat in, and B) no player plays against someone they played against previously. Players should be seated as fairly as possible from round to round, and where there is a perfect solution the algorithm should arrive at it, and when there isn't it should arrive at the "fairest" solution possible. It should be able to handle any arbitrarily large number of players, and should run in seconds.

In this talk, I'm going to talk a bit more about this specific problem and how I solved it using Python. I will walk you through my different attempts and thought processes while attempting to develop a good solution. You will walk away with a process and framework to solve your own difficult problems and develop a scientific mindset that can help lead you to new discoveries.

Finally, I will present how the algorithm works, and make suggestions to how it can be applied to solve other similar types of problems. I proudly present to you: The Gamer's Algorithm.

P.S. The algorithm will be used for the first time in the wild at the CATAN World Championships at Origin Games Fair and the U.S. National Championships at Gencon in 2018.

Comment:

production notes