FPT 2011 Design Competition -- Connect6


Congratulations to the Winners!

First Place: T. Watanabe, R. Moriwaki, Y. Yamaji, Y. Kamikubo, Y. Torigai, Y. Nihira, T. Yoza, Y. Ueno, Y. Aoyama, M. Watanabe, Shizuoka University, Japan

Runner Up: K. Sano, Tohoku University, Japan


Finalists Announced

Congratulations to the following finalist teams!  (Listed in no particular order):

K. Vipin, S. Fahmy, "A Threat Based Connect6 Implementation on FPGA"
Nanyang Technological University, Singapore

T. Ziermann, B. Schmidt, M. Muhlentaler, D. Ziener, J. Teich, "An FPGA Implementation of a Threat-based Strategy for Connect6"
University of Erlangen-Nuremberg, Germany

K. Sano, "HW and SW Co-Design of Connec6 Accelerator with Scalable Streaming Cores"
Tohoku University, Japan

T. Watanabe, R. Moriwaki, Y. Yamaji, Y. Kamikubo, Y. Torigai, Y. Nihira, T. Yoza, Y. Ueno, Y. Aoyama, M. Watanabe, "An FPGA Connect6 Solver with a Two-Stage Pipelined Evaluation"
Shizuoka University, Japan

News:

FINAL INSTRUCTIONS:

The best designs will go through a live competition at FPT 2011, where competing hardware will play against each other in a tournament.  Papers (reports) describing the best designs will also be selected for the FPT proceedings published by IEEE.    

Designs, therefore, have to qualify for the live final and publication.  This is done by submitting a report, detailing how your solution works, and how effective it is, as well as by submitting your design's source code.  The designs and reports will be evaluated by the design competition panel and the best will be selected for advancement to the final.

Your report should include:
  • An overview of your design and its FPGA implementation. 
  • An overview of your design's decision making strategy: how does your design decide what move to make? 
  • An overview of the testing strategy: how did you evaluate its effectiveness?
  • Your design's performance: clock speed and how many cycles it requires to make a move.
  • Also indicate the number of moves your design needs to win over the software opponent (provided on this page).
  • The name of the FPGA board on which the design was tested.  Please indicate the specific FPGA part and speed grade on the board.
Your must submit the report, as well as the source for your design, by e-mail to the competition organizers: janders AT eecg DOT toronto DOT edu and shouri AT ee DOT iitd DOT ac DOT in

Reports are due on October 3, 2011 at noon Eastern time (East Coast of US/Canada).    Reports should be a maximum of FOUR pages and must conform to FPT's IEEE format for standard papers (see: http://www.cse.iitd.ac.in/~icfpt11/final.html).

Please note that the turnaround will be fast to facilitate timely publication of the conference proceedings.  

Key dates:

Design poster paper submission (report) deadline: October 3, 2011 (noon Eastern time)
Paper acceptance notification: October 11, 2011
Finalist teams notification: October 11, 2011
Camera-ready design poster paper due: October 15, 2011
Winner announcement: At the conference, December 2011.


Introduction

We will again be hosting a design competition at IEEE FPT 2011 in New Delhi, India.

Following on the success of last year's riveting Reversi competition at FPT Beijing, this year, we will develop FPGA hardware implementations that can compete against each other at a game called Connect6.  Connect6 is a two-player game, invented in 2003.  The game is essentially a large-scale variant of tic-tac-toe where a player wins by getting six or more of their own pieces in a line.  The game's rules are simple, yet the solution space is large.  

As in 2010, we will have a grand final competition at the FPT 2011 conference where competing designs will play against one another with the exciting action and results displayed to the audience.

Rules of Connect6

A Wikipedia description of the game is available.
  • Connect6 is a two-player game that we will play on a 19x19 board.
  • Each player is referred to as light and dark, playing pieces coloured accordingly.
  • The first player to achieve a contiguous line (row, column or diagonal) of six or more of their own pieces wins the game.  
Playing the Game:
  • The dark and light players alternate in taking turns.
  • Dark always plays first and lays down ONE piece on any empty intersection of the board.
  • Light plays next and lays down TWO pieces on any empty intersections of the board.
  • Dark then plays again and lays down TWO pieces on any empty intersections of the board.
  • Light and dark continue to alternate, each playing two pieces on a turn on empty intersections of the board.
  • Note: it is only in dark's first turn that a single piece is played.  In all other turns two pieces are played by each player.
  • The game is a draw if the board is completely filled yet no player has won.
  • Your design must be capable of playing either the dark or light pieces.  
  • Your design must choose its moves using FPGA hardware and not an embedded processor.  An embedded processor may be used in your design, but only for interfacing.  That is, you may not  implement your design entirely as a software program that runs on an FPGA embedded processor.
Figure 1 gives an example board after the dark player's initial turn, and one turn by the light player.


Figure 1: Example Connect6 board after two turns.

Communicating with an Opponent

Data will be transmitted to/from your FPGA design through an RS-232 connection.  

Your design has to communicate through a connection to a host software program -- the "referee".  Your design will communicate the moves it wishes to make and will receive updates about the moves made by the opponent design (which may be a software program running on the host, or it may be another FPGA design).  

To place one piece on the board, four ASCII characters will be communicated, indicating the row and column as in Figure 1 above (each specified with two ASCII digits).  For example, in Figure 1 above, the dark piece is located at 0910.  

In general, turns consist of placing two pieces on the board and hence a total of eight ASCII characters will be communicated in a turn.  The exception to this is the first turn of the game, made by the dark player, which will consist of only a single piece being played (specified with four ASCII characters).

Play begins with the referee asking your design to make a move.  This is done by communicating one of two characters over the serial connection.  If a "D" is sent over the connection, then your design will be playing the dark pieces.  Your design should respond by sending four characters over the serial connection (corresponding to the initial piece placement).  If a "L" is sent by the referee, then your design will be playing the light pieces.  In the case of "L", an additional four characters will be sent over the serial connection by the referee: these correspond to the position of the dark player's initial played piece.

The referee will be monitoring move legality.  Any illegal move will disqualify the sending design.

Your design has one second to complete a move.  If you do not complete a move within this time your design will be disqualified.  Any move made will be communicated to the opponent at the end of this time period.  When  your design is playing against the software opponent, the software has as long as it wants to make a move, but your design can assume the software will communicate after at least one second (this knowledge may be useful if your design does computations while waiting for the opponent to move).  

The RS-232 connection should be set to 115200 bps, 8-bit data, no parity and 1 stop bit (115200 8N1).

A host program (software opponent) is available for download.  See the next section.

Host Program
  
The host program runs on a PC connected to the FPGA through the serial port.  This will allow you to test your FPGA implementation by having it play against a software opponent.  The decision making in the host program is not particularly sophisicated at the moment, however, it should be sufficient for you to test your FPGA hardware against.  The host program is available in 3 versions:

Linux (no GUI)  (game state is displayed in ASCII form within the terminal window)
Linux (GUI)  (game state is displayed in a Qt-based GUI)
Windows (GUI)  (game state is displayed in a Qt-based GUI)

Special thanks go to Kevin Nam, ECE Department, University of Toronto, for developing the host program.

Approved Boards
The following list gives approved systems.  Depending on the submissions received, designs using the "advanced" boards may be evaluated separately from designs using the "basic" or "older" boards.

Advanced boards:
  • Atlys Xilinx Spartan-6 FPGA Development Board
  • Altera DE2 Board (with Cyclone IV)
Basic boards:
  • Altera DE2 Board (with Cyclone II)
  • Xilinx Spartan 3E Starter Board or Development Board
Older boards that may also be used:
  • Virtex-II Pro Development System
  • XtremeDSP Starter Platform - Spartan-3A DSP 1800A Edition

Competition Format
  • The best designs will be selected to go through a live competition at FPT 2011.  Competing hardware will play against each other in a round-robin tournament.
  • The submissions will be due in October 2011.  The submission format and requirements are still being finalized, so stay tuned to this website for more information to be announced.
  • Short papers describing the top entries will appear in the published FPT 2011 proceedings.
Important Dates
  • Entries are due: October 1, 2011.
  • Final submission for finalists: October 15, 2011.
  • More information on submission format to be announced.
Questions?