ACM Collegiate Programming Contest (Hong Kong)

June 20, 2009 The Hong Kong University of Science and Technology (HKUST)

Introduction Regulations RegistrationProgramImportant DatesVenueAchievementPast ContestsCommittee Links

Participants Result Photo/Video Gallery Big 2 Competition

Co-Organizer

ACM-HK	HKUST

Sponsorship

ACM-HK	OGCIO	HKUST	HKU	Cyberport
CityU	HP

Introduction

Every year, the Association for Computing Machinery (ACM) sponsors regional and international collegiate programming contests . They divide the world up into 16 regions. Each region has a regional contest, with the top two or three teams in each region going on to the international contest.

Since 1991, the ACM Hong Kong Chapter has been organizing a local contest in Hong Kong, following the ACM contests in terms of aims, format, and style. This year, the Programming Contest is confirmed to be held on June 20 (Sat), 2009 at Hong Kong University of Science and Technology(UST). Fifty teams have been invited from the ten tertiary institutes in Hong Kong and Macau: The Chinese University of Hong Kong, The City University of Hong Kong, The Lingnan University, The Hong Kong Polytechnic University, The Hong Kong University of Science and Technology, The University of Hong Kong, The Hong Kong Baptist University, The Open University of Hong Kong, The University of Macau, and Macau University of Science and Technology. Each department of a participating institution can nominate up to five teams to take part in the contest. Teams will then be selected by the CPC organizing committee according to the priorities indicated by the individual department, making sure that the participating teams will be evenly distributed among the departments, with no single institution sending more than five teams.

Last year, the Collegiate Programming Contest was held on July 5, 2008 at the City University of Hong Kong, and a team from the The University of Hong Kong won the contest.

For more contest information (problem set), you can download contest '94 , contest '95 , contest '98 , contest '00 , contest '01 , contest '02 or the contest '03 .

In conjunction with the programming contest on 20/June, the computer-based Big 2 competition will also be held concurrently in Hong Kong University of Science and Technology(HKUST)..

Regulations

The format of the contest pits teams of three programmers competing against the clock. The software used for development is scheduled to be based on Microsoft Windows XP with Visual Studio.NET 2003 and Java 1.5.007 with Netbean 5.0. Each team is given six programming problems. They then try to write programs to solve as many of these problems as possible in the allotted time (scheduled to be four hours). The team that correctly solves the most problems wins. If multiple teams solve the same number of problems, the team that solved them fastest wins. Expertise in quick-and-dirty hacking is usually more valuable than rigid software engineering techniques in such an environment. Experience with debugging stupid mistakes is also a plus.

Registration

Please note that this year we introduce some changes to the local contest:

• Each university can send a maximum of FIVE regular teams and a maximum of THREE observing teams.
• Registration fee will be charged for each team:

Regular team: $2000 and Observing team: $500

Please complete the forms and mail to the following address by May 20 2009:

Ngo Chong-Wah
ACM-HK Collegiate Programming Contest 2009
Department of Computer Science
City University of Hong Kong
83 Tat Chee Avenue, Kowloon, Hong Kong
Email: cwngo@cs.cityu.edu.hk
Phone: 2784-4390
Fax: 2788-8614

Date and Venue

June 20, 2009

Room 4578-4580, Computer Barn C, ( via Lift 27-28)
Hong Kong University of Science and Technolgy
How to get there

Program

10:45-11:15:	Registration
11:15-12:00	Preparation and testing of machines
12:00-13:40	Lunch time
13:40-13:50	Competition Preparation
13:50-14:00	Openning speech by Professor Mounir HAMDI
14:00-18:00	Competition
18:30-21:30	Banquet and Award Ceremony

Important dates

Deadline for Registration:	May 20, 2009
Contest Date:	June 20, 2009

Participants

Competition Teams:

Name	Team	Coach	Organization
Chen Qifeng	HKUST1	Dr. KE Yi	Hong Kong University of Science and Technology
Li Yuliang
Yan Zhepeng
Wu You	HKUST2
Xu Yisheng
Liu Haixiang
Wai Wing Hei	HKUST3
Wong Ho Wa
Hung Chiu Lung
Chu Li Yu	HKUST4
Lam Chi Kit
Yeung Yuen Chuen
Cheng Michael	SIGHT (HKBU1)	Dr. Chu Xiaowen	Hong Kong Baptist University
Du Rui
Gao Shen
Zhao Kaiyong	SHARP (HKBU2)
Tang Chao
Yang Xiaofei
Ren Chushi	BRIGHT (HKBU-observing)
Chu Ting Fung
Li Chun Lung
Pang Hau Yan	IISZ000 (CityU1)	Dr. Duncan Wong	City University of Hong Kong
Wong Chi Fung
Lo Kwok Chung, Kengood
Chan Ka Shing	CITYU-CS2 (CityU2)
Chiu Lik Hang, Eric
Yin Linzhi, Alex
Fung Alan	BAT (OpenU1)	Dr. Andrew Kwok-Fai Lui	The Open University of Hong Kong
Wong Sau Yee
Suen Ching Wai
Yeung Wing Hong	KES (OpenU-observing)
Tsang Ka Ming
Yee Choi Wa Starry KES	(OpenU-observing)
Wu Hung Fai	CCUBE (OpenU-observing)
Chan Wing Kam
Fung King Ho
Liu Zhengyang	DIE HARD (PolyU1)	Dr. Dan Wang	The Hong Kong Polytechnic University
Liu Zhiyue
Yang Fan
Wang Tianzheng	Eagle (PolyU2)
Liu Zhengzhong
Chu Tun Yin
Wong Ke Fang	Black Hawk (PolyU3)
Tong Man Kin
Chan Sin Lun
Kwok Tsz Chiu	E++ (CUHK1)	Dr. Wong Tsz Yeung	The Chinese University of Hong Kong
Leung Kai Man
Lee Chin Ho
Yam Yu Kai
Cheung Ho Yee	++Zz (CUHK2)
Hung Chun Ho
Li Cheuk Ting
Mak Ka Ying
Lin Jian	super XX (CUHK-observing)
Peng Hao
Ding Qian
Hui Yan Ting	Far (HKU1)	Dr. Reynold Cheng	The University of Hong Kong
Ng Kwong Hei
Yip Lik Yau
Chen Yining	Lucky (HKU2)
Sun Liwen
Tong Chiu Man
Chan Sze Hang	Hi Hi (HKU3)
Lai Yiu Ming
Wong Lai Yin
Wong Chak Lim	thunder (HKU-observing)
Wong Chi Yuen
Lin Charles Matthew
Ngai Ka Kit	lightning (HKU-observing)
Divine Fung
Au Yeung Yat (Samuel)
Chan Pak Hay	HKOI1-observing	Dr. Ma Hoi Hung	Hong Kong Association for Computer Education
Law Wai Hon
Hon Man Hin Jeffrey
Tsang Chun Chi	HKOI2-observing
Lam Ka Wing
Wong Man Lok
So Pak Yeung	HKOI3-observing
Sham Yik Hin
Ng Yin Ki

Achievement

The achievement of the Hong Kong teams in the ACM-ICPC (ACM International Collegiate Programming Contest) world contest
　

Past Contests

　

Committee

Honorary Chair :	HAMDI Mounir
Chair:	Chen Lei
Local Arrangement:	Ke Yi
Judges:	Joe Yuen (Chief), Ho Wai-Shing(Chief), Hu Haibo, Ngo Chong Wah
Big-2 Competition:	Ho Wai-Shing
Web Chair:	Joe Yuen
Web / System Support:	Ke Yi
Sponsorship and Finance:	Howard Leung, Joe Yau
Registration:	Ngo Chong Wah

Related Websites

Result

Winner	Team	Member	Solved	Time
Champion	CUHK1- Chinese University of Hong Kong	Kwok Tsz Chiu Leung Kai Man Lee Chin Ho Yam Yu Kai	7	661
1st Runner-up	HKUST1- Hong Kong University of Science and Technology	Chen Qifeng Li Yuliang Yan Zhepeng	7	920
2nd Runner-up	CUHK2 - Chinese University of Hong Kong	Cheung Ho Yee Hung Chun Ho Li Cheuk Ting Mak Ka Ying	6	626

Big 2 Competition Winner: Mr. Bruce Kwong-Bun Tong (CityU)

Awards	Prizes
Champion Team	OGCIO travel award equivalent to $26000 to financially support the winning team to participate in one of the ACM Asia Regional Programming Contest 2009. Cash prize: $4,000 Additional cash prize: $500 per solved question
1st Runner Up	Cash prize: $3,000 Additional cash prize: $500 per solved question
2nd Runner Up	Cash prize: $2,000 Additional cash prize: $500 per solved question
Big-2 Competition	Cash prize: $1,000

Photo/Video Gallery

• Photo
• Video

Big-2 Competition

A computer Big 2 competition will be held during the Annual ACM Hong Kong Chapter Collegiate Programming Competition. While teams compete in the programming contest, at another location of the content site a competition will be held for Big 2 playing programs, which are to be written and submitted before the contest day.

In this competition, the programs play a number of Big 2 games. The organizer's "mediator program" acts as the dealer and the communication proxy to all the Big 2 playing programs. Each participating program matches up with all other programs, and the one which gets the highest score wins. This document describes the rules of Big 2 and the protocol understood by the mediator. It also describes the competition arrangements for reducing the luck factor in Big 2 games.

How to play the game?

"Big 2" is a popular poker game in East Asia and South East Asia, especially in Hong Kong, Macau, Singapore, Malaysia and Taiwan [1]. It is usually played with 2 to 4 players. In this competition, only 4-player Big 2 games are played and hence we assumed every game has 4 players in the following discussions. At the beginning of a Big 2 game, every player gets 13 cards. Then, the players can play (i.e., discard) some of their cards in their hands according to the rules. The objective of the game is to become the first player who played all his/her cards.

Rules

Different variation of rules are available for the games at different locations. For the competition, we need a set of common rules for all the programs. We describe the common rules here, mainly following the conventions in Hong Kong.

Cards:

The game uses a standard 52-card deck as in poker, with thirteen cards in each of the four suits. Each card has a suit and a rank . Spades (?) suit is the highest, followed by hearts (?), clubs (?) and then diamonds (?). As the name of the game indicates, twos have the highest rank, and the rest of the deck have normal ranks as in poker -- aces above kings, kings above queens, and so on. Threes have the lowest rank.

Game Play:

A Big 2 game is played in tricks . A player starts a trick by playing any valid combination (more will be discussed in the next section). Then, the next player (the one who sits on the right hand side of the current player) can choose to play a combination that has the same size and a higher ranking than the last play or choose to pass . If three consecutive players pass, the trick ends and the player who made the last play can start a new trick. The game ends if any player played all his/her cards.

At the beginning of each game, the entire deck is dealt to the players so that each player has 13 cards. Then, if this is the first game of a sequence of games, the player who has ?3 starts the first trick by playing a combination which contains ?3. In subsequent games, the player who has won the last game starts the first trick and there are no restrictions on his/her first play.

Combination:

Cards may be played as singles or in groups of two, three, or five cards which resemble poker hands. Here is a list of all valid combinations and their rankings. Note that when a player makes a play within a trick, that play must be of the same size as the previous play and must have a higher ranking.

• Size-1 combination ( single ): Any single card from the deck. The cards are ordered by their ranks with suits being the tie-breaker. (E.g., ?A beats ?A, and ?A beats ?K.)
• Size-2 combination ( pair ): Any two cards of the same rank. The ranking of a pair is determined by the ranking of the card within the pair with the highest single-card ranking. (E.g., The pair ?K?K beats the pair ?K?K because ?K beats ?K.)
• Size-3 combination ( three-of-a-kind ): Any three cards of the same rank. The ranking of a three-of-a-kind is determined by the cards' rank. (E.g., 7-7-7 beats 3-3-3 regardless their suits.)
• Size-5 combinations: There are five different types of 5-card combinations. The rankings, from low to high, are as follows. (i.e., any flush beats any straight, and any full house beats any flush, etc.)
  • Straight : Any 5 cards in a sequence of ranks (but not all of them are in the same suit). Note that J-Q-K-A-2, Q-K-A-2-3 and K-A-2-3-4 are not straights but A-2-3-4-5 and 2-3-4-5-6 are. The ranking of a straight is determined by the ranks of the cards in the straight. If two straights have cards in the same ranks, the suit of the highest ranked card is used as tie-breaker. (E.g., 2-3-4-5-6 beats 10-J-Q-K-A because 2 beats A. A-2-3-4-5 beats 2-3-4-5-6 because after the tie at 2, A beats 6. ?A-?2-3-4-5 beats ?A-?2-3-4-5 because all ranks are tied and ?2 beats ?2.)
  • Flush : Any 5 cards of the same suit (but not in a sequence of ranks). Its ranking is determined by the ranks of the cards in the flush. If two flushes have cards in the same ranks, suit is used as tie-breaker. (E.g., ?3-4-7-9-2 beats ?9-J-Q-K-A because 2 beats A. ?3-4-7-K-2 beats ?9-T-J-Q-2 because after the tie at 2, K beats Q. ?3-4-7-K-2 beats ?3-4-7-K-2 because ? beats ? while all ranks are equal in two flushes.)
  • Full House : A composition of a three-of-a-kind and a pair. Its ranking is determined by the ranking of the three-of-a-kind.
  • Four-of-a-kind and One Card : A composition of four cards of the same rank plus any fifth card. Its ranking is determined by the rank of the card in the four-of-a-kind.
  • Straight Flush : A composition of straight and flush. i.e., the five cards are in a sequence of ranks and in the same suit. The ranking follows the rules as in straights.

  Note that the ranking of a 5-card combination is determined by its type using the intra-type ranking as tie breaker. i.e., 3-3-3-3-4 beats 2-2-2-A-A because Four-of-a-kind has a higher-ranking type than Full house.

Scoring:

After that a game ends, if a player has less than 10 cards in hand, he/she gets -1 point per card. If a player has 10 to 12 cards in hand, he/she gets -2 points per card. If a player has not played any card, he/she gets -3 points per card instead. The winner of a game gets points equal to the total of points deducted from other player. E.g., if a game ends when the players have 3, 10 and 13 cards in hand (the winner must have 0 cards in hand), the players get -3, -20 and -39 points respectively and the winner gets +62 points.

After a series of games, the player with the highest point total wins.

The Competition

The participants of the computer Big 2 competition have to write a computer program which can act as a player in a 4-player Big 2 game. The programs play the Big 2 games by communicating with a mediator program through a specific protocol. The competition uses a league format to determine the winning program.

The League

In the league, each program has to play a match of Big 2 games against every other program. Within a match, a number of Big 2 games are played and the program which gets the highest point total wins the match. The winner of the match gets 2 match points and the loser gets 0 match points. If the match ends in a draw, each program gets 1 match point. The program which gets the most match points wins the competition. If there is a tie in match points by different programs, only the matches involving those programs are used to determined the winner. If the winner still cannot be decided, the program which gets the highest point total in all Big 2 games it played wins the competition.

The Match

A match is a competition between two computer Big 2 playing programs. Two sequences (tables) of 4-player Big 2 games are played in a match with instances of those two programs as players. i.e., in a table of Big 2 games, each program has two instances running and plays in two positions in the table. The positions are randomly assigned at the beginning of the match.

In normal Big 2 games, the score a player gets does not only depend on his/her playing skills. The quality of his/her opening hand is also very important. In order to reduce the effect of randomness in our match, two tables of Big 2 games are played using exactly the same set of hands. The playing position of the Big 2 playing programs are swapped in these two tables. E.g., if program 1's instances play positions A and B in the first table, program 1's instances play positions C and D in the second table. In this case, if a program gets a good hand in one table, its opponent will get exactly the same good hand in the other table. Therefore, every program plays through exactly the same set of hands and the effect of hand quality is reduced.

The score of a Big 2 playing program is the total score of all four positions it played in two tables. The program with a higher score wins the match. If the programs finish with the same score, the match ends in a draw.

Play Computer Big 2 Games

In a table of Big 2 games, the computer Big 2 playing programs play a number of 4-player Big 2 games. The Big 2 programs communicate with each other through a mediator program following a specific protocol. For simplicity, a Big 2 playing program is simply referred as a player and the mediator program as the mediator below.

When a table of Big 2 games begins, the mediator starts up each player as a child process. The child processes will subsequently communicate with the mediator by reading from their standard input stream and writing to their standard output stream. Since these streams are in reality connected to pipes created by the mediator, output must be flushed after each message is written by C++ I/O manipulator flush or C function fflush .

The mediator starts the table by forking a new process for each of the four players. Then, the mediator sends a line containing a single integer to each player, indicating the total number of Big 2 games will be played within this table before the scores are counted.

At the beginning of each Big 2 game, the mediator sends a line containing that player's opening hand to each player. The opening hand contains exactly 13 cards. Each card is denoted by two characters and the cards are separated by any number of whitespace. The first character denotes the suit ( S = ?, H = ?, C = ?, and D = ?) and the second character denotes the rank (2 = 2 and 10 = T ) of the card. The cards are sorted in ascending order of ranking. Then, the mediator starts the game by getting the play from the player who should make the first play. In the first game of the table, the mediator gets the play from the player who has D3 . This play must contain D3 . In subsequent games, the mediator gets the play from the player who has won the previous game.

A play from a player is a line of text that contains a set of cards sorted in ascending order of ranking, or a special move "PASS", which is denoted by the string PASS . After getting the play, the mediator writes a line containing the player's ID (an integer) and the play to the input streams of all other players and gets the play from the next player. Each player numbers itself as 0, its next player as 1, its opposite player as 2 and its previous player as 3. The players follow an anti-clockwise order.

Each player has to keep track of the game state itself as no part of the protocol contains such information. For example, after getting a play from player 3, a player should decide its play and output that play to its standard output. As another example, a player should detect whether another player has won a game after a play so that it knows when to receive the initial hand for the next game from the mediator.

Each player has 5 minutes to decide all its plays in a table of Big 2 games. The player can use more time making certain plays and less making others. After a player has used up 5 minutes, each of its plays thereafter must be decided within two seconds. The mediator maintains 4 clocks, one for each player, initialized to zero at the beginning of the table. At any time, only one clock runs, the one of the player who is computing the next play.

As soon as a player decides the next play by sending a message to the mediator, its clock stops. The mediator then sends the message to all other players, starts the clock of the next player and waits for that player's play. Any player which does not have its clock running are suspended by the mediator so that the player cannot perform any computation during the thinking time of other players.

The players and the mediator run in a multiprogrammed environment. The time used by a player is measured by the time used by its process. Therefore, players must not fork any other processes.

The configuration of computers on which the Big 2 playing programs will run will be announced soon.

A player can communicate only with the mediator through its standard input stream and standard output stream. It will be disqualified if it communicates with other parties by any other means.

If a player submits an illegal play to the mediator or cannot decide a play within the time limit, that player loses the match and loses any subsequent tie-breakers involving that match. A player can assume that any play sent from the mediator is always legal.

The Interface Package

The packages for mediator and sample program are available for downloading: big2judge and big2player . (Note: the program can only run on Linux due to the use of Linux specific virtual file system on time counting.)

To play a game between two players, execute the command

big2judge ../player/player1 ../player/player2 ../player/player3 ../player/player4 in the directory big2judge . The methods in which the players are invoked and the protocol with which the mediator communicates with the players will not change in future versions of the mediator. Only better display, loggin, error checking, etc. will be added to it, and these will be made publicly available when they are ready.

Contact Information

Big 2 Competition Chair: HO Wai Shing, Department of Computer Science, The University of Hong Kong. < wsho@cs.hku.hk >

For registration information, bug reports, questions, and suggestions, please contact < wsho@cs.hku.hk >

Reference

[1] Big 2, Wikipedia. Retrieved on May 2, 2008, http://en.wikipedia.org/wiki/Big_Two .