# The Game

You will be playing an (almost) standard game of Connect-4. Unfortunately, it is a correspondence game and someone has placed black tape on every second row starting from the bottom, so that you cannot see any of your opponent's moves within these rows.

Any moves within already-full columns will count as passing your turn, and if a game runs for longer than 6 * 7 turns it will be adjudicated as a draw.

# Challenge Specification

Your program should be implemented as a Python 3 function. The first argument is a 'view' of the board, representing the known board state as a 2D list of rows from bottom to top where 1 is a move by the first player, 2 a move by the second player, and 0 an empty position or a hidden move by your opponent.

The second argument is a turn number indexed from 0, and its parity tells you which player you are.

The final argument is an arbitrary state, initialized to None at the beginning of each game, which you can use to preserve state between turns.

You should return a 2-tuple of the column index you wish to play, and the new state to be returned to you next turn.

# Scoring

A win counts as +1, a draw as 0, and a loss as -1. Your goal is to achieve the highest average score in a round-robin tournament. I will try to run as many matches as required to identify a clear winner.

# Rules

Any competitor should have at most one competing bot at any one time, but it is OK to update your entry if you make improvements. Please try to limit your bot to ~1 second of thinking time per turn.

# Testing

Here is the source code for the controller, together with a few non-competing example bots for reference:

import itertools
import random

def get_strides(board, i, j):
yield ((i, k) for k in range(j + 1, 7))
yield ((i, k) for k in range(j - 1, -1, -1))
yield ((k, j) for k in range(i + 1, 6))
yield ((k, j) for k in range(i - 1, -1, -1))
directions = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
def diag(di, dj):
i1 = i
j1 = j
while True:
i1 += di
if i1 < 0 or i1 >= 6:
break
j1 += dj
if j1 < 0 or j1 >= 7:
break
yield (i1, j1)
for d in directions:
yield diag(*d)

DRAWN = 0
LOST = 1
WON = 2
UNDECIDED = 3

def get_outcome(board, i, j):
if all(board[-1]):
return DRAWN
player = board[i][j]
strides = get_strides(board, i, j)
for _ in range(4):
s0 = next(strides)
s1 = next(strides)
n = 1
for s in (s0, s1):
for i1, j1 in s:
if board[i1][j1] == player:
n += 1
if n >= 4:
return WON
else:
break
return UNDECIDED

def apply_move(board, player, move):
for i, row in enumerate(board):
if board[i][move] == 0:
board[i][move] = player
outcome = get_outcome(board, i, move)
return outcome
if all(board[-1]):
return DRAWN
return UNDECIDED

def get_view(board, player):
view = [list(row) for row in board]
for i, row in enumerate(view):
if i % 2:
continue
for j, x in enumerate(row):
if x == 3 - player:
row[j] = 0
return view

def run_game(player1, player2):
players = {1 : player1, 2 : player2}
board = [[0] * 7 for _ in range(6)]
states = {1 : None, 2 : None}
for turn in range(6 * 7):
p = (turn % 2) + 1
player = players[p]
view = get_view(board, p)
move, state = player(view, turn, states[p])
outcome = apply_move(board, p, move)
if outcome == DRAWN:
return DRAWN
elif outcome == WON:
return p
else:
states[p] = state
return DRAWN

def get_score(counts):
return (counts[WON] - counts[LOST]) / float(sum(counts))

def run_tournament(players, rounds=10000):
counts = [[0] * 3 for _ in players]
for r in range(rounds):
for i, player1 in enumerate(players):
for j, player2 in enumerate(players):
if i == j:
continue
outcome = run_game(player1, player2)
if outcome == DRAWN:
for k in i, j:
counts[k][DRAWN] += 1
else:
if outcome == 1:
w, l = i, j
else:
w, l = j, i
counts[w][WON] += 1
counts[l][LOST] += 1
ranks = sorted(range(len(players)), key = lambda i: get_score(counts[i]), reverse=True)
print("Round %d of %d\n" % (r + 1, rounds))
rows = [("Name", "Draws", "Losses", "Wins", "Score")]
for i in ranks:
name = players[i].__name__
score = get_score(counts[i])
rows.append([name + ":"] + [str(n) for n in counts[i]] + ["%6.3f" % score])
lengths = [max(len(s) for s in col) + 1 for col in zip(*rows)]
for i, row in enumerate(rows):
padding = ((n - len(s)) * ' ' for s, n in zip(row, lengths))
print(''.join(s + p for s, p in zip(row, padding)))
if i == 0:
print()
print()

def random_player(view, turn, state):
return random.randrange(0, 7), state

def constant_player(view, turn, state):
return 0, state

def better_random_player(view, turn, state):
while True:
j = random.randrange(0, 7)
if view[-1][j] == 0:
return j, state

def better_constant_player(view, turn, state):
for j in range(7):
if view[-1][j] == 0:
return j, state

players = [random_player, constant_player, better_random_player, better_constant_player]

run_tournament(players)


Happy KoTHing!

# Provisional Results

Name                    Draws Losses Wins  Score

zsani_bot:              40    5377   94583  0.892
better_constant_player: 0     28665  71335  0.427
constant_player:        3     53961  46036 -0.079
normalBot:              38    64903  35059 -0.298
better_random_player:   192   71447  28361 -0.431
random_player:          199   75411  24390 -0.510

• Could you explain why you check view[-1][j] == 0? I am not entirely sure I see where you filled them and my python knowledge seems to be a bit rusty. – Barbarian772 Sep 10 '18 at 11:57
• @Barbarian772 I'm checking if there is still space in that column. Note that there are 6 rows so the top row is fully-observed. – user1502040 Sep 10 '18 at 12:03
• You shouldn’t count placing in already full columns as a pass. Many connect 4 games end with only one column not filled and if one player will lose by playing in that column, this will make the game tie when it is otherwise a forced win for one player. – soktinpk Sep 10 '18 at 16:35
• @soktinpk Doesn't that just add another layer of strategy? Connect-4 is a solved game after all, so the turn skipping factor could be enough of a rule change that contributors can't just use the standard algorithms. – mypetlion Sep 10 '18 at 17:56
• Zero-indexing from the bottom, are the taped-over rows (0,2,4,6) or (1,3,5)? Some ASCII art would be helpful. – SIGSTACKFAULT Sep 21 '18 at 18:02

This bot takes all sure wins, and falls back to block the rivals, second guess them vertically and horizontally or make random moves.

import pprint, math, collections, copy
def zsani_bot_2(view, turn, state):
if state == None: #first own turn - always for for middle
state = (1, 2) if turn == 0 else (2, 1) #(my_symbol, your symbol)
#print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]))
return 3, state

#locate obvious points
for i in range (1, 6):              #skip first row
for j in range(len(view[i])):   #TODO: Optimise with zip. Go for clarity now
if view[i][j] != 0 and view[i-1][j] == 0:
view[i-1][j] = state[1]
enemy_points = math.floor(turn/2)
++enemy_points if state[0] == 2 else enemy_points
known_points = sum([i.count(state[1]) for i in view])
missing_points = enemy_points - known_points

#get sure wins in any direction
for j in range(0, 7): #every column
for i in range(4, -1, -1):
if view[i][j] !=0:
break #find highest known filled point
if (not missing_points or i+1 in {1, 3, 5}):
view1 = copy.deepcopy(view)
attempt = apply_move(view1, state[0], j)
if attempt == WON:
# print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' winner move')
return j, state

#block sure enemy wins in any direction
for j in range(0, 7):
for i in range(4, -1, -1):
if view[i][j] !=0:
break #find highest known filled point
if (not missing_points or (i+1 in {1, 3, 5})):
view1 = copy.deepcopy(view)
attempt = apply_move(view1, state[1], j)
if attempt == WON:
#  print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' saving move')
return j, state

#block walls
for i in range(0, 3): #impossible to get 4 in a row when the column is full
for j in range(0, 6):
if view[i][j] != 0 and view[i][j] == view[i+1][j] and view[i+2][j] == view[i+3][j] == 0:
#   print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' column move')
return j, state

#block platforms if posessing perfect information on row below and drop point
for i in range(0, 5):
for j in range(0, 3):
stats = collections.Counter([view[i][j], view[i][j+1], view[i][j+2], view[i][j+3]])
if stats[0] == 2 and (stats[state[0]] == 2 or stats[state[0]] == 2):
for k in range(0, 3):
if view[i][j+k] == 0:
break
if (i == 0 or view[i-1][j+k] != 0) and (not missing_points or i in {1, 3, 5}):
#print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' platform move')
return j+k, state
else:
for l in range (k, 3):
if view[i][j+l] == 0:
break
if (i == 0 or view[i-1][j+l] != 0) and (not missing_points or i in {1, 3, 5}):
#       print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' platform move')
return j+l, state

#fallback -> random
while True:
j = random.randrange(0, 7)
if view[-1][j] == 0:
#print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' random move')
return j, state


Thank you for fixing run_game!

Changelog:

• v2 adds horizontal blocking - if, in a row of 4, there are two empty spots and two spots filled by the same player, it will attempt to fill one of them to have three in a row/block the opponents row, which will hopefully be capitalized upon in the following turns.
• Welcome to the site. I voted to reject the edit to change to code, it would be best left as a comment, that way the OP can decide what to do with the code. – Wheat Wizard Oct 8 '18 at 16:20
• I don't have enough reputation to comment on the main post. How do I withdraw an edit? – Syfer Polski Oct 8 '18 at 16:30
• No need to withdraw the edit (I don't think you can anyway). In the future commenting will be sufficient but since you have said it in your answer it is likely that the OP will see. Plus I think that the OP will see that you suggested and edit even if it has been rejected. – Wheat Wizard Oct 8 '18 at 16:44
• The reason I'd like to withdraw the edit is because I missed one line in the changes, without which the edited code will completely fail to run. I've included it in the edit suggestion in my post. Thank you for your help! – Syfer Polski Oct 8 '18 at 16:48

normalBot plays upon the assumption that spots in the middle are more valuable than spots on the ends. Thus, it uses a normal distribution centered in the middle to determine its choices.

def normalBot(view, turn, state):
randomNumber = round(np.random.normal(3, 1.25))
fullColumns = []
for i in range(7):
if view[-1][i] != 0:
fullColumns.append(i)
while (randomNumber > 6) or (randomNumber < 0) or (randomNumber in fullColumns):
randomNumber = round(np.random.normal(3, 1.25))
return randomNumber, state


This is obviously non-competing, but nonetheless very useful for debugging... and surprisingly fun, if you know your bot well enough to cheat :D so I'm posting in the hopes of inspiring more submissions:

import math, pprint
def manual_bot(view, turn, state):
if state == None:
state = (1, 2) if turn == 0 else (2, 1) #(my_symbol, your symbol)

#locate obvious points
for row in range (1, 6):
for j in range(len(view[row])):
if view[row][j] != 0 and view[row-1][j] == 0:
view[row-1][j] = state[1]

#if you're second, the opponent has one more point than half the turns
enemy_points = math.ceil(turn/2)
known_points = sum([row.count(state[1]) for row in view])
missing_points = enemy_points - known_points

print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' Missing points: ' + str(missing_points))
while True:
try:
move = int(input("What is your move?(0-6) "))
except ValueError:
continue
if move in {0, 1, 2, 3, 4, 5, 6}:
return move, state


The grid is upside down(the bottom row is highest). To get the winner announcements, you need to patch the game controller, adding a print statement before returning the win:

elif outcome == WON:
print(pprint.pformat(board) + ' Turn: ' + str(turn) +' Winner: '+ str(p))
return p


[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 0 Player: 1 Missing points: 0
[[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 2 Player: 1 Missing points: 0
[[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 4 Player: 1 Missing points: 1
[[0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 6 Player: 1 Missing points: 2
[[2, 1, 1, 1, 1, 2, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 6 Winner: 1
[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 1 Player: 2 Missing points: 1
[[0, 0, 2, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 3 Player: 2 Missing points: 2
[[0, 0, 2, 1, 0, 0, 0],
[0, 0, 1, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 5 Player: 2 Missing points: 1
[[0, 0, 2, 1, 2, 0, 0],
[0, 0, 1, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 7 Player: 2 Missing points: 2
[[0, 2, 2, 1, 2, 0, 0],
[0, 0, 1, 2, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]] Turn: 9 Player: 2 Missing points: 1
[[0, 2, 2, 1, 2, 0, 0],
[0, 0, 1, 2, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 11 Player: 2 Missing points: 1
[[0, 2, 2, 1, 2, 0, 0],
[0, 0, 1, 2, 2, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 13 Player: 2 Missing points: 2
[[0, 2, 2, 1, 2, 0, 0],
[0, 1, 1, 2, 2, 0, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 2, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 15 Player: 2 Missing points: 1
[[0, 2, 2, 1, 2, 0, 0],
[0, 1, 1, 2, 2, 0, 0],
[0, 0, 1, 2, 1, 0, 0],
[0, 0, 1, 0, 2, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 17 Player: 2 Missing points: 2
[[0, 2, 2, 1, 2, 1, 1],
[0, 1, 1, 2, 2, 2, 1],
[0, 0, 1, 2, 1, 0, 0],
[0, 0, 1, 0, 2, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 19 Player: 2 Missing points: 0
[[0, 2, 2, 1, 2, 1, 1],
[0, 1, 1, 2, 2, 2, 1],
[0, 0, 1, 2, 1, 0, 2],
[0, 0, 1, 0, 2, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 21 Player: 2 Missing points: 1
[[0, 2, 2, 1, 2, 1, 1],
[0, 1, 1, 2, 2, 2, 1],
[0, 2, 1, 2, 1, 0, 2],
[0, 1, 1, 0, 2, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 23 Player: 2 Missing points: 1
[[0, 2, 2, 1, 2, 1, 1],
[0, 1, 1, 2, 2, 2, 1],
[0, 2, 1, 2, 1, 0, 2],
[0, 1, 1, 2, 2, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]] Turn: 25 Player: 2 Missing points: 2
[[0, 2, 2, 1, 2, 1, 1],
[0, 1, 1, 2, 2, 2, 1],
[0, 2, 1, 2, 1, 0, 2],
[0, 1, 1, 2, 2, 0, 2],
[0, 0, 2, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0]] Turn: 27 Player: 2 Missing points: 1
[[1, 2, 2, 1, 2, 1, 1],
[1, 1, 1, 2, 2, 2, 1],
[0, 2, 1, 2, 1, 2, 2],
[0, 1, 1, 2, 2, 0, 2],
[0, 0, 2, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0]] Turn: 29 Player: 2 Missing points: 0