You've already read Improving the Random Bot and you want to know what to do next.
Waste is unnecessary moves that don't improve your position and prevent you from maximizing your production each turn.
Some ways to reduce waste:
The ImprovedBot took care of some waste over RandomBot by adding a rule about attacking a cell with more strength than you, but it doesn't cover every situation.
If a cell is on the border, let's have it wait until it can attack successfully.
def get_move(square):
for direction, neighbor in enumerate(game_map.neighbors(square)):
if neighbor.owner != myID and neighbor.strength < square.strength:
return Move(square, direction)
if square.strength < square.production * 5:
return Move(square, STILL)
border = any(neighbor.owner != myID for neighbor in game_map.neighbors(square))
if not border:
return Move(square, random.choice((NORTH, WEST)))
else:
# wait until we are strong enough to attack
return Move(square, STILL)
You can see that PatientBot, by staying still, is able to grow faster and defeat ImprovedBot.
Right now both PatientBot and ImprovedBot move in a northwesterly direction. In most games this means that a lot of production and time is wasted moving from the southeast to the northwest.
Instead of moving randomly, let's move towards the nearest border.
def find_nearest_enemy_direction(square):
direction = NORTH
# don't get stuck in an infinite loop
max_distance = min(game_map.width, game_map.height) / 2
for d in (NORTH, EAST, SOUTH, WEST):
distance = 0
current = square
while current.owner == myID and distance < max_distance:
distance += 1
current = game_map.get_target(current, d)
if distance < max_distance:
direction = d
max_distance = distance
return direction
def get_move(square):
for direction, neighbor in enumerate(game_map.neighbors(square)):
if neighbor.owner != myID and neighbor.strength < square.strength:
return Move(square, direction)
if square.strength < square.production * 5:
return Move(square, STILL)
border = any(neighbor.owner != myID for neighbor in game_map.neighbors(square))
if not border:
return Move(square, find_nearest_enemy_direction(square))
else:
# wait until we are strong enough to attack
return Move(square, STILL)
AmbiturnerBot has higher production and territory just by moving in all directions.
Optimizing your growth rate is a great way to improve your standing in the rankings. Early, mid, and late game growth are crucial to defeating strong bots.
Early game growth is all about effectively using your resources to capture nearby valuable areas of the map. But what does valuable mean? The visualizer does a good job helping you identify metrics that may be valuable, namely territory, production, and strength.
The AmbiturnerBot optimizes for territory, usually capturing the lowest cost enemy cell it can. This is good because territory is how you win games but raw territory doesn't necessarily help much in the early game. Instead you probably want to optimize for production. Good early game production will fuel your bot through the rest of the game.
def get_move(square):
target, direction = max(
(
(neighbor, direction)
for direction, neighbor in enumerate(game_map.neighbors(square))
if neighbor.owner != myID
),
default=(None, None),
key=lambda t: t[0].production,
)
if target is not None and target.strength < square.strength:
return Move(square, direction)
elif square.strength < square.production * 5:
return Move(square, STILL)
border = any(neighbor.owner != myID for neighbor in game_map.neighbors(square))
if not border:
return Move(square, find_nearest_enemy_direction(square))
else:
# wait until we are strong enough to attack
return Move(square, STILL)
But wait! ProductionBot lost! I thought you said production was good!?
Production is good, but you can't focus on just production. AmbiturnerBot is winning because it uses a better heuristic.
How can we improve ProductionBot to start winning?
def heuristic(square):
return square.production / square.strength if square.strength else square.production
def get_move(square):
target, direction = max(
(
(neighbor, direction)
for direction, neighbor in enumerate(game_map.neighbors(square))
if neighbor.owner != myID
),
default=(None, None),
key=lambda t: heuristic(t[0]),
)
if target is not None and target.strength < square.strength:
return Move(square, direction)
elif square.strength < square.production * 5:
return Move(square, STILL)
border = any(neighbor.owner != myID for neighbor in game_map.neighbors(square))
if not border:
return Move(square, find_nearest_enemy_direction(square))
else:
# wait until we are strong enough to attack
return Move(square, STILL)
Combat is a huge part of Halite, and being bad at it can ruin an otherwise good bot.
One of the crucial things to know about combat is overkill
each piece decreases the strength of every adjacent or coinciding opposing piece by its own strength
Let's update our heuristic to take overkill into account.
def heuristic(square):
if square.owner == 0 and square.strength > 0:
return square.production / square.strength
else:
# return total potential damage caused by overkill when attacking this square
return sum(
neighbor.strength
for neighbor in game_map.neighbors(square)
if neighbor.owner not in (0, myID)
)
You'll notice that both bots behave almost identically until they start to fight, then OverkillBot takes DiscerningBot apart!
Here is the full source code for OverkillBot
import hlt
from hlt import EAST, NORTH, SOUTH, STILL, WEST, Move, Square
myID, game_map = hlt.get_init()
hlt.send_init("OverkillBot")
def find_nearest_enemy_direction(square):
direction = NORTH
# don't get stuck in an infinite loop
max_distance = min(game_map.width, game_map.height) / 2
for d in (NORTH, EAST, SOUTH, WEST):
distance = 0
current = square
while current.owner == myID and distance < max_distance:
distance += 1
current = game_map.get_target(current, d)
if distance < max_distance:
direction = d
max_distance = distance
return direction
def heuristic(square):
if square.owner == 0 and square.strength > 0:
return square.production / square.strength
else:
# return total potential damage caused by overkill when attacking this square
return sum(
neighbor.strength
for neighbor in game_map.neighbors(square)
if neighbor.owner not in (0, myID)
)
def get_move(square):
target, direction = max(
(
(neighbor, direction)
for direction, neighbor in enumerate(game_map.neighbors(square))
if neighbor.owner != myID
),
default=(None, None),
key=lambda t: heuristic(t[0]),
)
if target is not None and target.strength < square.strength:
return Move(square, direction)
elif square.strength < square.production * 5:
return Move(square, STILL)
border = any(neighbor.owner != myID for neighbor in game_map.neighbors(square))
if not border:
return Move(square, find_nearest_enemy_direction(square))
else:
# wait until we are strong enough to attack
return Move(square, STILL)
while True:
game_map.get_frame()
moves = [get_move(square) for square in game_map if square.owner == myID]
hlt.send_frame(moves)
This is a pretty good start for our bot. More things to think about are:
Our bot spends a lot of time with cells at the border that are just waiting until they have enough strength to attack an enemy. What if we combined some of them together to attack sooner?
Right now we move every cell to its nearest border, but what if the nearest border isn't particularly valuable? We should find ways to direct those resources towards valuable parts of the map.
Ensure that strength is not lost to the 255 cap. OverkillBot loses a lot of strength (especially when routing pieces) to combining pieces whose strengths sum to over 255. Avoiding this could make a big difference.
One additional detail about the 255 cap - the cap applies before combat occurs so if 2 200 strength cells attack one 220 strength cell in the same turn, the resulting cell will have 35 strength, not 180 strength.
Look for inefficiencies in your playstyle. Look for ways to improve your heuristic. Take past and future moves into account.
Check out halint to process your replays and get feedback about ways to improve.
May the best bot win!