CSC 1913 Fall 2025 Project 1 – Kōnane

Introduction to Algorithms, Data Structures, and Program Development

Deadline: Fri, Oct 10, 2025 5pm

Academic Integrity Warning

Unlike the computer lab exercises, this is not a collaborative assignment. See the Collaboration and Academic integrity document for information concerning Academic Dishonesty. Always feel free to ask the instructor or the TAs if you are unsure of something. They will be more than glad to answer any questions that you have. We want you to be successful and learn so give us the chance to help you. Please also make sure you are familiar with the Scholastic Conduct Policy outlined in the Syllabus.

Submission Instructions

You must submit a file called project_one.py to gradescope. This should be the only file you submit
Your name must appear at the top of the file in a docstring
Project 1 is due on Fri, Oct 10, 2025 5pm

Kōnane

Parts of this section are from several National Park Service resources. One of which is liked to in the “More Info” section.

Kōnane is a two-player strategy board game from Hawaii. Played on a rectangular board, it begins with black and white counters filling the board in an alternating pattern. Before contact with Europeans the game was played using small pieces of white coral and black lava rock. Using a large carved that doubled as a board and table. Pu’uhonua o Hōnaunau National Historical Park is where one of our instructors first encountered this game.

Set Up the Board

The Kōnane board is an 8 by 8 board. In the upper left hand corner is a black stone. Then alternate Black and White across the first row. Alternate stone colors going down columns as well.

8 by 8 board with alternating black and white stones

Then, one player removes two stones from the center of the board. Each player is randomly assigned a color, and the player who is assigned the color Black moves first.

Playing the Game

The First player moves a black stone over a white stone into an empty space (a jump). That player then takes the white stone and removes it from the board. The next player moves their white stone over a black stone to an empty space and removes the black stone.

Every move is made by jumping over one ore more a rival stones, providing that there is an empty space to move to.

While a stone can jump as many of the rival stones as the player wants (provided there is empty spaces to move into) the moves must always be in a straight line. A player will never move in two directions in one play. Additionally, a player may not jump diagonally.

During a single move a player will move a single stone only one direction left, right, up, or down.

Winning the Game

The more moves are made the fewer stones remain on the board. Players always alternate turns. When a player is unable to make any jump they have lost and the game is ended. The Game will never end in a tie, as the winner is always the last player to make a move.

More Info

Read more from the National Park Service

You can also play Kōnane online

Program Requirements

Board Representation

Throughout these functions the board will be represented by a list of lists. An empty spot will have a 0, a spot with a Black Stone will have a 1, and a spot with a White Stone will have a 2. You may assume that the will be a Rectangle.

The Black player will be represented by the int 1 and the white player by the int 2.

A move will be a Tuple of two Tuples, where each nested Tuple will have two integers a row and a column.

Tuple[Tuple[int, int], Tuple[int, int]]

The first Tuple will be the starting position of the stone, and the second Tuple will be the ending position of the Stone.

Tuple[Start, End]

Functions

generate_board(an_int)

This function should take a single integer. While all of the other functions you write must assume a rectangular board, you may assume that this specific function will always be used to generate Square Boards. Therefore the integer passed is both the height and width.

The function should return a list of lists, filled in such that the item at position (0,0) is a 1, and the remainder of the spots are filled in with alternating colors.

If the user uses a zero or negative value return an empty list.

>>> generate_board(6)
[[1, 2, 1, 2, 1, 2],
 [2, 1, 2, 1, 2, 1],
 [1, 2, 1, 2, 1, 2],
 [2, 1, 2, 1, 2, 1],
 [1, 2, 1, 2, 1, 2],
 [2, 1, 2, 1, 2, 1]]
>>> generate_board(8)
[[1, 2, 1, 2, 1, 2, 1, 2],
 [2, 1, 2, 1, 2, 1, 2, 1],
 [1, 2, 1, 2, 1, 2, 1, 2],
 [2, 1, 2, 1, 2, 1, 2, 1],
 [1, 2, 1, 2, 1, 2, 1, 2],
 [2, 1, 2, 1, 2, 1, 2, 1],
 [1, 2, 1, 2, 1, 2, 1, 2],
 [2, 1, 2, 1, 2, 1, 2, 1]]
>>> generate_board(11)
[[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1],
 [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2],
 [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1],
 [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2],
 [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1],
 [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2],
 [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1],
 [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2],
 [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1],
 [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2],
 [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1]]

get_board_as_string(board)

You must include a function that returns the current board state as a string. Each “cell” in the board should be represented in the following format

When no one has played in that square the cell should be empty. If that the spot has a white token it should be (the white token is Unicode u25CB)

A black token should be (the black token is Unicode u25CF)

Adjacent cells should share borders. For example:

A board should display all the cells with indicators for column and row indices (Zero based indexing).

If the indexes of the columns or rows are 10 or larger, the index should be printed modulo 10.

It is difficult to see, but for the board layout for the to string function, each row should start with have a number, followed by a space, followed by |. Which means that the “Lines” separating rows (of the form +-+-+-+-+-+ should start with two space characters.

The following is an example of a full 8 x 8 board

And here’s a 15 x 15 board:

prep_board_human(board)

This function should print the board as a string, then prompt the user to enter two row and column locations and remove the token at those two locations. The two locations must be of different colors, and if the same color is picked twice the user should be re-prompted. Additionally, both of the selected tokens must not be on the edge of the board.

You can see some examples of this function running

This function should return None. It should mutate the passed in board.

is_valid_move(board, move)

This function will accept two arguments, a board and a move. It will return True if the move is valid and False if the move is invalid.

While the description of this function is simple, the actual implementation requires a number of different checks you will have to identify.

Remember that a move is a Tuple of two Tuples. The first Tuple will be the starting position of the stone, and the second Tuple will be the ending position of the Stone.

get_valid_moves_for_stone(board, stone)

This function will take in a board, and a stone. This stone will actually be a tuple of length two with a row and column representing a stone location.

The function should return a list of all of the valid moves for a given stone position. If there are no valid moves or if the give stone location is empty return an empty list.

Remember that a move is a Tuple of two Tuples, where each nested Tuple will have two integers a row and a column. The first Tuple is the starting position of the stone, and the second Tuple is the ending position of the Stone.

get_valid_moves(board, player)

This function will accept a board and an integer representing a “Black” or “White” player. This function should return a list of all of the valid moves for that player given the current board state.

human_player(board, player)

This function will take in a board and an integer (1 or 2). This function will return an empty tuple if there is no valid moves. If there is a valid move it should print the board to the standard output. Then it should prompt the user to enter a valid move. It should continue to prompt the user until they enter a valid move. The function will return the valid move.

You can see some examples of this function running

random_player(board, player)

This function will accept a board and an integer (1 or 2). This function will return a random valid move for that player (starting position coordinates, and ending position coordinates). If there is no valid move the function should return an empty tuple.

ai_player(board, player)

This function will accept a board and an integer (1 or 2). This function will return a valid move for that player. This AI can choose a valid move using any method except for completely random selection (like random_player(board, player) and it cannot require any interaction with a human. If there is no valid move the function should return an empty tuple.

play_game(board)

This function will play an entire game of Kōnane between the two AI agents. It should play the game the given board.

The “First” player should be randomly selected between the white and black AI. If the white AI wins the function should return 1. If the black AI wins the function should return 2.

Documentation

Every function should have function docstrings, and you should have sensible in-line comments.

Style Checker

We will be using an automatic style checker in the auto-grader as well as checking for sensible variable names and function names. Use of the break keyword or of global variables will result in a loss of points

Constraints

You may use any built-in Python objects/methods (string, list, etc.)
You may use imported functions and class methods from random and math only
You may not use the break keyword
You may not use global variables (global constants are okay)
You may not work with anyone else
You may not use any form of generative AI
The work submitted must be your own