8
2
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
user1502040
Posted 2018-09-10T11:24:22.347
Reputation: 2 196
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 – 2018-09-10T11:57:43.777
@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 – 2018-09-10T12:03:28.623
1You 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 – 2018-09-10T16:35:09.443
@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 – 2018-09-10T17:56:25.063
@soktinpk Point taken. However, I suspect that many fewer games will make it to that point given the hidden information. – user1502040 – 2018-09-11T12:29:17.040
Are there limitations to the "state" variable? For example, can it store information about the progress of the game in a list, or can it only be boolean? – Solvation – 2018-09-11T21:08:18.417
@Solvation, it can be any data you wish to preserve between turns. – user1502040 – 2018-09-11T21:20:40.303
I might not understand something, but shouldn't the get_view function iterate across the row to hide values? Right now, 'if row[i] == 3 - player:' only evaluates the index of the row instead of the column. – Solvation – 2018-09-12T21:39:54.447
@Solvation Wow, what a stupid bug. I should have been more careful when refactoring. Thanks. – user1502040 – 2018-09-13T07:27:55.987
1Zero-indexing from the bottom, are the taped-over rows (0,2,4,6) or (1,3,5)? Some ASCII art would be helpful. – SIGSTACKFAULT – 2018-09-21T18:02:43.363
@Blacksilver (0,2,4,6). – user1502040 – 2018-09-22T18:18:07.677