PSet 3 Tournament

From 6.034 Wiki

Current revision

There are 51 entries in the tournament; these consist of everyone who indicated that they would like to compete, and who provided a ps3.scm that can be loaded in a reasonable amount of time. They were given a seed order according to how they performed against rspeer (the TA)'s code in a 0.01-second lightning round. The highest-seeded competitors got byes in the first round.

Each contest is a series of six games. Each player plays white three times and black there times, on boards of size 5, 6, and 7. If there is a 3-3 tie, the contest is run again at double the time limit to determine a winner.

The tournament isn't run in as controlled conditions as the problem set grading, so here's how the rounds were run:

• Round 1: 0.1 seconds per move, on whatever processor time we got on linux.mit.edu
• Round 2: 0.2 seconds per move, on a 4GHz cluster computer
• Round 3: 0.4 seconds per move, on whatever processor time we got on linux.mit.edu
• Round 4: 0.4 seconds per move, on a rather fast multicore machine
• Round 5: 0.8 seconds per move, same multicore machine
• Rounds 6 and 7: 1.6 seconds per move, same multicore machine

Final standings

Here, we present the winners and the techniques they used.

All three finalists' solutions have something in common: they all assigned pieces a value based on the number of ranks they have moved forward. Simply adding up their ranks would not value one move over another, because every move increases the rank of some pawn, but (for example) squaring the rank makes the player favor moving pieces that are already far down the board (or, conversely, prevent their opponent from moving pieces far down the board).

By adding up the squared values for your own pieces, and subtracting the squared values for your opponent pieces, you get a surprisingly powerful "sum-of-squares heuristic". Using 2ⁿ instead of n² gives a "sum-of-exponentials" heuristic that places even more weight on pieces that are far down the board.

First place: Maciej Pacula (mpacula)

Maciej's evaluation function started with the simple heuristic of the number of possible moves, but made possible capturing moves worth 10 times more. He added this value to .85 of the sum-of-squares heuristic. With the evaluation function's focus on capturing, the result was an aggressive player that clawed its way to the top for an undefeated victory.

Second place: Yuran Lu (yuranlu)

Illustrating the fact that an evaluation function can do well by being dead simple, Yuran's evaluation function used the sum-of-exponentials heuristic and nothing more. Yuran's player lost only to Maciej's (twice).

Third place: Andreas Weibel (anweibel)

Andreas' evaluation function was also simple, using just the sum-of-squares heuristic. It performed nearly the same as Yuran's sum-of-exponentials. It was a close match when they competed head-to-head: they tied on the size-5 and size-6 boards, but Yuran's sum-of-exponentials saw the winning move one step ahead in both size-7 games.

(This writeup previously said that Yuran used sum-of-squares as well. Sorry about the error.)

Rounds 5-7

Round 5...                 Round 6...    Round 7
            TOP BRACKET

anweibel  ]
mattlong  ]--------------- anweibel ]
                                    ]--- mpacula  ]
yuranlu   ]--------------- mpacula  ]             ]
mpacula   ]                                       ]
                                                  ]
                                                  ]--- mpacula
martynaj  ]                                       ]
yuranlu   ]-- yuranlu  ]                          ]
                       ]-- yuranlu  ]             ]
agorlin   ]-- agorlin  ]            ]--- yuranlu  ]
mattlong  ]                anweibel ]

            BOTTOM BRACKET

Top bracket (rounds 1-4)

Seed  Round 1...   Round 2...    Round 3...    Round 4...

 [1] ccpost   ]
[64] BYE      ]--- ccpost   ]
                            ]--- agorlin  ]
[32] byoshimo ]--- agorlin  ]             ]
[33] agorlin  ]                           ]
                                          ]--- martynaj ]
[16] ng1213   ]                           ]             ]
[49] espeed   ]--- ng1213   ]             ]             ]
                            ]--- martynaj ]             ]
[17] martynaj ]--- martynaj ]                           ]
[48] jslocum  ]                                         ]
                                                        ]--- anweibel
 [8] anweibel ]                                         ]
[57] BYE      ]--- anweibel ]                           ]
                            ]--- anweibel ]             ]
[25] alerer   ]--- alerer   ]             ]             ]
[40] rothberg ]                           ]             ]
                                          ]--- anweibel ]
 [9] peairs   ]                           ]
[56] BYE      ]--- peairs   ]             ]
                            ]--- nbieber  ]
[24] cnorahs  ]--- nbieber  ]
[41] nbieber  ]

 [4] alexch   ]
[61] BYE      ]--- alexch   ]
                            ]--- igork    ]
[29] igork    ]--- igork    ]             ]
[36] abrahamr ]                           ]
                                          ]--- r_chiang ]
[13] r_chiang ]                           ]             ]
[52] BYE      ]--- r_chiang ]             ]             ]
                            ]--- r_chiang ]             ]
[20] asilata  ]--- k_rowe   ]                           ]
[45] k_rowe   ]                                         ]
                                                        ]--- mattlong
 [5] tkang    ]                                         ]
[60] BYE      ]--- tkang    ]                           ]
                            ]--- ithink   ]             ]
[28] ithink   ]--- ithink   ]             ]             ]
[37] cpercib  ]                           ]             ]
                                          ]--- mattlong ]
[12] cmcheng  ]                           ]
[53] BYE      ]--- cmcheng  ]             ]
                            ]--- mattlong ]
[21] mattlong ]--- mattlong ]
[44] dwhitlow ]

 [2] yuranlu  ]
[63] BYE      ]--- yuranlu  ]
                            ]--- yuranlu  ]
[31] hsk      ]--- hsk      ]             ]
[34] munir    ]                           ]
                                          ]--- yuranlu  ]
[15] owenlin  ]                           ]             ]
[50] austein  ]--- owenlin  ]             ]             ]
                            ]--- owenlin  ]             ]
[18] markstev ]--- markstev ]                           ]
[47] lilywang ]                                         ]
                                                        ]--- yuranlu
 [7] ede      ]                                         ]
[58] BYE      ]--- ede      ]                           ]
                            ]--- thananat ]             ]
[26] whoburg  ]--- thananat ]             ]             ]
[39] thananat ]                           ]             ]
                                          ]--- thananat ]
[10] jeremyis ]                           ]
[55] BYE      ]--- jeremyis ]             ]
                            ]--- jmstein  ]
[23] jmtstein ]--- jmstein  ]
[42] jtchang  ]

 [3] jtrigg   ]
[62] BYE      ]--- jtrigg   ]
                            ]--- jtrigg   ]
[30] huynht   ]--- huynht   ]             ]
[35] grk      ]                           ]
                                          ]--- jtrigg   ]
[14] raza     ]                           ]             ]
[51] amrik    ]--- amrik    ]             ]             ]
                            ]--- aspicer  ]             ]
[19] aspicer  ]--- aspicer  ]                           ]
[46] jambo    ]                                         ]
                                                        ]--- mpacula
 [6] mpacula  ]                                         ]
[59] BYE      ]--- mpacula  ]                           ]
                            ]--- mpacula  ]             ]
[27] rnk      ]--- rnk      ]             ]             ]
[38] zero     ]                           ]             ]
                                          ]--- mpacula  ]
[11] gdurrett ]                           ]
[54] BYE      ]--- gdurrett ]             ]
                            ]--- gdurrett ]
[22] luuk     ]--- luuk     ]
[43] geofft   ]

Bottom bracket (rounds 1-4)

Since this is a double-elimination tournament, you end up in this bracket whenever you lose a round. The bottom bracket plays two games for every one that the top bracket plays.

Round 1...   Round 2...                Round 3...                Round 4...

BYE      ]-- byoshimo ]
byoshimo ]   ccpost   ]-- ccpost   ]
                                   ]-- ng1213   ]
espeed   ]-- jslocum  ]-- ng1213   ]            ]-- gdurrett ]
jslocum  ]   ng1213   ]                gdurrett ]            ]
                                                             ]
BYE      ]-- rothberg ]                                      ]-- gdurrett ]
rothberg ]   alerer   ]-- alerer   ]                         ]            ]-- martynaj ]
                                   ]-- alerer   ]            ]   martynaj ]            ]
BYE      ]-- cnorahs  ]-- cnorahs  ]            ]-- aspicer  ]                         ]
cnorahs  ]   peairs   ]                aspicer  ]                                      ]
                                                                                       ]
BYE      ]-- abrahamr ]                                                                ]
abrahamr ]   alexch   ]-- alexch   ]                                                   ]-- martynaj
                                   ]-- alexch   ]                                      ]
BYE      ]-- asilata  ]-- asilata  ]            ]-- jmstein  ]                         ]
asilata  ]   k_rowe   ]                jmstein  ]            ]                         ]
                                                             ]                         ]
BYE      ]-- cpercib  ]                                      ]-- owenlin  ]            ]
cpercib  ]   tkang    ]-- cpercib  ]                         ]            ]-- owenlin  ]
                                   ]-- cpercib  ]            ]   r_chiang ]
BYE      ]-- dwhitlow ]-- cmcheng  ]            ]-- owenlin  ]
dwhitlow ]   cmcheng  ]                owenlin  ]

BYE      ]-- munir    ]
munir    ]   hsk      ]-- hsk      ]
                                   ]-- markstev ]
austein  ]-- lilywang ]-- markstev ]            ]-- ithink   ]
lilywang ]   markstev ]                ithink   ]            ]
                                                             ]
BYE      ]-- whoburg  ]                                      ]-- ithink   ]
whoburg  ]   ede      ]-- whoburg  ]                         ]            ]-- ithink   ]
                                   ]-- jtchang  ]            ]   thananat ]            ]
BYE      ]-- jtchang  ]-- jtchang  ]            ]-- igork    ]                         ]
jtchang  ]   jeremyis ]                igork    ]                                      ]
                                                                                       ]
BYE      ]-- grk      ]                                                                ]
grk      ]   huynht   ]-- grk      ]                                                   ]-- agorlin
                                   ]-- grk      ]                                      ]
raza     ]-- raza     ]-- raza     ]            ]-- grk      ]                         ]
jambo    ]   amrik    ]                nbieber  ]            ]                         ]
                                                             ]                         ]
BYE      ]-- zero     ]                                      ]-- agorlin  ]            ]
zero     ]   rnk      ]-- rnk      ]                         ]            ]-- agorlin  ]
                                   ]-- rnk      ]            ]   jtrigg   ]   
BYE      ]-- geofft   ]-- geofft   ]            ]-- agorlin  ]
geofft   ]   luuk     ]                agorlin  ]

Detailed results

Click on the name of any match to see the output of the match. The last line of the file indicates the overall winner.

Top bracket, round 1

• ccpost vs. BYE: ccpost
• byoshimo vs. agorlin: agorlin
• ng1213 vs. espeed: ng1213
• martynaj vs. jslocum: martynaj
• anweibel vs. BYE: anweibel
• alerer vs. rothberg: alerer
• peairs vs. BYE: peairs
• cnorahs vs. nbieber: nbieber
• alexch vs. BYE: alexch
• igork vs. abrahamr: igork
• r_chiang vs. BYE: r_chiang
• asilata vs. k_rowe: k_rowe
• tkang vs. BYE: tkang
• ithink vs. cpercib: ithink
• cmcheng vs. BYE: cmcheng
• mattlong vs. dwhitlow: mattlong
• yuranlu vs. BYE: yuranlu
• hsk vs. munir: hsk
• owenlin vs. austein: owenlin
• markstev vs. lilywang: markstev
• ede vs. BYE: ede
• whoburg vs. thananat: thananat
• jeremyis vs. BYE: jeremyis
• jmstein vs. jtchang: jmstein
• jtrigg vs. BYE: jtrigg
• huynht vs. grk: huynht
• raza vs. amrik: amrik
• aspicer vs. jambo: aspicer
• mpacula vs. BYE: mpacula
• rnk vs. zero: rnk
• gdurrett vs. BYE: gdurrett
• luuk vs. geofft: luuk

Bottom bracket, round 1

• BYE vs. byoshimo: byoshimo
• espeed vs. jslocum: jslocum
• BYE vs. rothberg: rothberg
• BYE vs. cnorahs: cnorahs
• BYE vs. abrahamr: abrahamr
• BYE vs. asilata: asilata
• BYE vs. cpercib: cpercib
• BYE vs. dwhitlow: dwhitlow
• BYE vs. munir: munir
• austein vs. lilywang: lilywang
• BYE vs. whoburg: whoburg
• BYE vs. jtchang: jtchang
• BYE vs. grk: grk
• raza vs. jambo: raza
• BYE vs. zero: zero
• BYE vs. geofft: geofft

Top bracket, round 2

• ccpost vs. agorlin: agorlin
• ng1213 vs. martynaj: martynaj
• anweibel vs. alerer: anweibel
• peairs vs. nbieber: nbieber
• alexch vs. igork: igork
• r_chiang vs. k_rowe: r_chiang
• tkang vs. ithink: ithink
• cmcheng vs. mattlong: mattlong
• yuranlu vs. hsk: yuranlu
• owenlin vs. markstev: owenlin
• ede vs. thananat: thananat
• jeremyis vs. jmstein: jmstein
• jtrigg vs. huynht: jtrigg
• amrik vs. aspicer: aspicer
• mpacula vs. rnk: mpacula
• gdurrett vs. luuk: gdurrett

Bottom bracket, round 2a

• byoshimo vs. ccpost: ccpost
• jslocum vs. ng1213: ng1213
• rothberg vs. alerer: alerer
• cnorahs vs. peairs: cnorahs
• abrahamr vs. alexch: alexch
• asilata vs. k_rowe: asilata
• cpercib vs. tkang: cpercib
• dwhitlow vs. cmcheng: cmcheng
• munir vs. hsk: hsk
• lilywang vs. markstev: markstev
• whoburg vs. ede: whoburg
• jtchang vs. jeremyis: jtchang
• grk vs. huynht: grk
• raza vs. amrik: raza
• zero vs. rnk: rnk
• geofft vs. luuk: geofft

Bottom bracket, round 2b

• ccpost vs. ng1213: ng1213
• alerer vs. cnorahs: alerer
• alexch vs. asilata: alexch
• cpercib vs. cmcheng: cpercib
• hsk vs. markstev: markstev
• whoburg vs. jtchang: jtchang
• grk vs. raza: grk
• rnk vs. geofft: rnk

Top bracket, round 3

• agorlin vs. martynaj: martynaj
• anweibel vs. nbieber: anweibel
• igork vs. r_chiang: r_chiang
• ithink vs. mattlong: mattlong
• yuranlu vs. owenlin: yuranlu
• thananat vs. jmstein: thananat
• jtrigg vs. aspicer: jtrigg
• mpacula vs. gdurrett: mpacula

Bottom bracket, round 3a

• ng1213 vs. gdurrett: gdurrett
• alerer vs. aspicer: aspicer
• alexch vs. jmstein: jmstein
• cpercib vs. owenlin: owenlin
• markstev vs. ithink: ithink
• jtchang vs. igork: igork
• grk vs. nbieber: grk
• rnk vs. agorlin: agorlin

Bottom bracket, round 3b

• gdurrett vs. aspicer: gdurrett
• jmstein vs. owenlin: owenlin
• ithink vs. igork: ithink
• grk vs. agorlin: agorlin

Top bracket, round 4

• martynaj vs. anweibel: anweibel
• r_chiang vs. mattlong: mattlong
• yuranlu vs. thananat: yuranlu
• jtrigg vs. mpacula: mpacula

Bottom bracket, round 4a

• gdurrett vs. martynaj: martynaj
• owenlin vs. r_chiang: owenlin
• ithink vs. thananat: ithink
• agorlin vs. jtrigg: agorlin

Bottom bracket, round 4b

• martynaj vs. owenlin: martynaj
• ithink vs. agorlin: agorlin

Top bracket, round 5

• anweibel vs. mattlong: anweibel
• yuranlu vs. mpacula: mpacula

Bottom bracket, round 5a

• martynaj vs. yuranlu: yuranlu
• agorlin vs. mattlong: agorlin

Bottom bracket, round 5b

• yuranlu vs. agorlin: yuranlu

Round 6

• anweibel vs. mpacula: mpacula
• yuranlu vs. anweibel: yuranlu

Final

• mpacula vs. yuranlu: mpacula