• MacTech Network:
  • Tech Support
  • |
  • MacForge.net
  • |
  • Apple News
  • |
  • Register Domains
  • |
  • SSL Certificates
  • |
  • iPod Deals
  • |
  • Mac Deals
  • |
  • Mac Book Shelf

MAC TECH

  • Home
  • Magazine
    • About MacTech in Print
    • Issue Table of Contents
    • Subscribe
    • Risk Free Sample
    • Back Issues
    • MacTech DVD
  • Archives
    • MacTech Print Archives
    • MacMod
    • MacTutor
    • FrameWorks
    • develop
  • Forums
  • News
    • MacTech News
    • MacTech Blog
    • MacTech Reviews and KoolTools
    • Whitepapers, Screencasts, Videos and Books
    • News Scanner
    • Rumors Scanner
    • Documentation Scanner
    • Submit News or PR
    • MacTech News List
  • Store
  • Apple Expo
    • by Category
    • by Company
    • by Product
  • Job Board
  • Editorial
    • Submit News or PR
    • Writer's Kit
    • Editorial Staff
    • Editorial Calendar
  • Advertising
    • Benefits of MacTech
    • Mechanicals and Submission
    • Dates and Deadlines
    • Submit Apple Expo Entry
  • User
    • Register for Ongoing Raffles
    • Register new user
    • Edit User Settings
    • Logout
  • Contact
    • Customer Service
    • Webmaster Feedback
    • Submit News or PR
    • Suggest an article
  • Connect Tools
    • MacTech Live Podcast
    • RSS Feeds
    • Twitter

November 1997 Programmer's Challenge

PENTE®

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm EDT, Saturday, 1 November 1997

Reaching once again into the closet where we store board games, I found the game of Pente®, The board physically resembles the board used in GO, but the game strategies are simpler.

Pente® is played by two players who alternate placing stones on a 19x19 grid. The objective is to win the game by getting five or more stones in a row or, alternatively, by capturing five or more pairs of your opponent's stones. Your Challenge is to write code that will play the game of Pente® and accumulate the most points (described below) in the minimum time.

The prototype for the code you should write is:

typedef struct Capture {

  Point stone1;

  Point stone2;

} Capture;

void InitPente(

  long boardHalfSize  /* e.g., 9 for a 19x19 board */

                      /* all coordinates between -boardHalfSizeand +boardHalfSize */

);

void Pente(

  Point opponentsMove,      /* your opponent moved here */

  Boolean playingFirst,     /* ignore opponentMove */

  Point *yourMove,          /* return your move here */

  Capture claimCaptures[],  /* return coordinates of captured pairs here */

  long *numCaptures,        /* return number of claimCaptures here */

  Boolean *claimVictory     /* return true if you claim victory with this move */

);

void TermPente(void); /* deallocate any dynamic storage */

Captures take place by bracketing two adjacent stones of your opponents. Given the position

---BWW---

... Black can capture the two White stones by playing ...

---BWW---

---BWWB--

... after which the two White stones are removed ...

---BWW---

---B B--

Captures can occur horizontally, vertically, or diagonally. Note that no capture occurs if White moves into the unoccupied square below:

---BW-B--

Multiple captures can occur on a single move.

The game ends when one side captures five pairs of the opponent's stones, or when one side places five stones in a straight line, either horizontally, vertically, or diagonally. When one side obtains an unblocked row of four stones, called a tessera, a win is imminent. Therefore, an unblocked row of three stones, called a tria, is a serious threat that should be blocked unless a stronger offensive move exists.

The first player's first move must be at the origin (0,0).

To neutralize the advantage that the first player has, the first player's second move is restricted to be three or more intersections away from the center of the board (i.e., the h or v coordinates of first player's second move must both be greater than or equal to 3 in absolute value).

At the start of the game, your InitPente routine (and that of your opponent) will be called with the half-width of the board in boardHalfSize (between 9 and 15, inclusive). The Pente routines will then be alternately called, providing the location of your opponentsMove (unless you are playingFirst). You should place a stone in an unoccupied location and return that location in yourMove. In addition, if your move captures any adjacent pairs of your opponent's stones, you should report the number of captures in numCaptures, and the locations of the captured pairs in claimCaptures. If your move results in victory, either by achieving 5 of your stones in a row, or a cumulative capture of 5 pairs of your opponent's stones, you should set claimVictory to true. At the end of the game, TermPente will be called, where you should deallocate any dynamically allocated storage.

Board coordinates are expressed as distance from the center square in ordered (v,h) pairs, so that the center intersection is at (0,0), and the corners of the standard board are at (-9,-9), (-9,9), etc.

At the end of the game, points will be awarded as follows:

  5 points for the player who achieved 5 stones in a row

  1 point for each capture

  1 point for each distinct sequence of 4 stones in a row remaining on the board

One point will be deducted for each second of execution time used during a player's turns, including the time taken by the InitPente and TermPente routines. Both the game winner and the game loser will accumulate points. It is possible to earn negative points. The Challenge winner will be the entry that accumulates the most points in a round-robin tournament of all entries, where each entry plays each other entry at least twice, half of the time playing first and half playing second.

Your code may allocate up to 10MB of dynamic storage, including both explicit calls to NewPtr/malloc and allocation of dynamic objects. This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

Pente® is published by Pente Games, Inc.

 
MacTech Only Search:
Community Search:

 
 
 

 
 
 
 
 
  • SPREAD THE WORD:
  • Slashdot
  • Digg
  • Del.icio.us
  • Reddit
  • Newsvine
  • Generate a short URL for this page:



MacTech Magazine. www.mactech.com
Toll Free 877-MACTECH, Outside US/Canada: 805-494-9797
MacTech is a registered trademark of Xplain Corporation. Xplain, "The journal of Apple technology", Apple Expo, Explain It, MacDev, MacDev-1, THINK Reference, NetProfessional, Apple Expo, MacTech Central, MacTech Domains, MacNews, MacForge, and the MacTutorMan are trademarks or service marks of Xplain Corporation. Sprocket is a registered trademark of eSprocket Corporation. Other trademarks and copyrights appearing in this printing or software remain the property of their respective holders.
All contents are Copyright 1984-2010 by Xplain Corporation. All rights reserved. Theme designed by Icreon.
 
Nov. 20: Take Control of Syncing Data in Sow Leopard' released
Nov. 19: Cocktail 4.5 (Leopard Edition) released
Nov. 19: macProVideo offers new Cubase tutorials
Nov. 18: S Stardom anounces Safe Capsule, a companion piece for Apple's
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live