Partially-Observable Connect-4

Question

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 

• Barbarian772: 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.
• user1502040: @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.
• soktinpk: 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.
• mypetlion: @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.
• SIGSTACKFAULT: Zero-indexing from the bottom, are the taped-over rows (0,2,4,6) or (1,3,5)? Some ASCII art would be helpful.

Answer 1

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.

• Wheat Wizard: 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.
• Syfer Polski: I don't have enough reputation to comment on the main post. How do I withdraw an edit?
• Wheat Wizard: 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.
• Syfer Polski: 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!

Answer 2

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

Answer 3

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
What is your move?(0-6) 3
[[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
What is your move?(0-6) 2
[[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
What is your move?(0-6) 4
[[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
What is your move?(0-6) 1
[[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
What is your move?(0-6) 2
[[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
What is your move?(0-6) 3
[[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
What is your move?(0-6) 4
[[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
What is your move?(0-6) 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, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 9 Player: 2 Missing points: 1
What is your move?(0-6) 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, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 11 Player: 2 Missing points: 1
What is your move?(0-6) 4
[[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
What is your move?(0-6) 4
[[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
What is your move?(0-6) 3
[[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
What is your move?(0-6) 5
[[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
What is your move?(0-6) 
What is your move?(0-6) 6
[[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
What is your move?(0-6) 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
What is your move?(0-6) 3
[[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
What is your move?(0-6) 6
[[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
What is your move?(0-6) 5
[[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
What is your move?(0-6) 5
[[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, 2, 2],
 [0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0]] Turn: 29 Winner: 2
Round 1 of 1

Name Draws Losses Wins Score

manual_bot: 0 0 2 1.000 
zsani_bot_2: 0 2 0 -1.000