search

dgets / nightMiner

Halite III Bot - rewriting Halite III bot from scratch with better project structure plans
6 stars 1 forks source link

Ships are making 'pawn' formations #33

Open dgets opened 5 years ago

dgets commented 5 years ago

Much like in a game of chess when there are head-to-head pawns blocking each other, the ships are occasionally finding ways to keep each other from doing anything when they want to get into the same spot. I'm assuming this is because of profitable halite determination telling them both to head for the same space, but there are potentially other sources for this collision issue. Log analysis will be necessary.

Also, as the game continues, the 'pawn blockade' has a greater and greater chance of adding more ships to it with each additional ship that gets stuck in that pattern. So this is kind of a significant problem, at least for some percentage of games played.

dgets commented 5 years ago

In the following log snippets, a pawn formation develops between ship IDs 2 and 11 after turn 103:

INFO:root:=============== TURN 102 ================ DEBUG:root: - me.get_ships() dump: [Ship(id=2, Position(17, 16), cargo=997 hali te), Ship(id=6, Position(23, 17), cargo=919 halite), Ship(id=4, Position(23, 13) , cargo=919 halite), Ship(id=11, Position(21, 16), cargo=154 halite), Ship(id=10 , Position(23, 20), cargo=54 halite), Ship(id=0, Position(19, 14), cargo=1000 ha lite), Ship(id=9, Position(17, 18), cargo=978 halite)] DEBUG:root: Making sure turn (101 <= 368) INFO:root: - processing ship.id: 2 INFO:root: - ship.id: 2 in transit to drop INFO:root: - ship.id: 2 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 6 INFO:root: - ship.id: 6 in transit to drop INFO:root: - ship.id: 6 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 4 INFO:root: - ship.id: 4 in transit to drop INFO:root: - ship.id: 4 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 11 DEBUG:root: - ship.id 11 in primary mining conditional INFO:root: - ship.id: 11 scooting to Position(18, 16) INFO:root: - processing ship.id: 10 DEBUG:root: - ship.id 10 in primary mining conditional INFO:root: - ship.id: 10 scooting to Position(23, 21) INFO:root: - processing ship.id: 0 DEBUG:root: - ship.id 0 in primary mining conditional INFO:root: - ship.id: 0 in transit to drop INFO:root: - ship.id: 0 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 9 DEBUG:root: - ship.id 9 in primary mining conditional INFO:root: - ship.id: 9 mining at Position(17, 18) DEBUG:root:Killing from history for reassignment: [] DEBUG:root:Killing from history due to ship 8-x: [] INFO:root: - updating frame INFO:root:=============== TURN 103 ================ DEBUG:root: - me.get_ships() dump: [Ship(id=0, Position(20, 14), cargo=999 halite), Ship(id=11, Position(20, 16), cargo=121 halite), Ship(id=10, Position(23, 21), cargo=40 halite), Ship(id=4, Position(23, 14), cargo=896 halite), Ship(id=2, Position(18, 16), cargo=997 halite), Ship(id=6, Position(23, 16), cargo=0 halite), Ship(id=9, Position(17, 18), cargo=983 halite)] DEBUG:root: Making sure turn (102 <= 368) INFO:root: - processing ship.id: 0 INFO:root: - ship.id: 0 in transit to drop INFO:root: - ship.id: 0 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 11 DEBUG:root: - ship.id 11 in primary mining conditional INFO:root: - ship.id: 11 scooting to Position(18, 16) INFO:root: - processing ship.id: 10 DEBUG:root: - ship.id 10 in primary mining conditional DEBUG:root: - ship.id: 10 WTF ship history dump: ship ID: 10, location: Position(23, 16), destination: Position(23, 21), turnstamp set: 92, secondary_mission: Missions.in_transit, primary_mission: Missions.mining; full ship dump: Ship(id=10, Position(23, 21), cargo=40 halite) DEBUG:root: - generate_profitable_offset() returning: (1, 0) from: analytics.HaliteAnalysis.find_best_dir() INFO:root: - processing ship.id: 4 INFO:root: - ship.id: 4 in transit to drop INFO:root: - ship.id: 4 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 2 INFO:root: - ship.id: 2 in transit to drop INFO:root: - ship.id: 2 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 6 INFO:root: - ship.id: 6 DROPPED the BONE DEBUG:root: - fell into except; setting new ship id: 6 to mining DEBUG:root: -* generate_profitable_offset() returning: (0, 1) from: analytics.HaliteAnalysis.find_best_dir() DEBUG:root: - tmp_destination_dir contents: (0, 1) INFO:root: - processing ship.id: 9 DEBUG:root: - ship.id 9 in primary mining conditional INFO:root: - ship.id: 9 mining at Position(17, 18) DEBUG:root:Killing from history for reassignment: [] DEBUG:root:Killing from history due to ship 8-x: [] INFO:root: - updating frame INFO:root:=============== TURN 104 ================ DEBUG:root: - me.get_ships() dump: [Ship(id=11, Position(19, 16), cargo=108 halite), Ship(id=0, Position(21, 14), cargo=956 halite), Ship(id=10, Position(24, 21), cargo=40 halite), Ship(id=2, Position(18, 16), cargo=997 halite), Ship(id=9, Position(17, 18), cargo=987 halite)] DEBUG:root: Making sure turn (103 <= 370) INFO:root: - processing ship.id: 11 DEBUG:root: - ship.id 11 in primary mining conditional INFO:root: - ship.id: 11 scooting to Position(18, 16) INFO:root: - processing ship.id: 0 INFO:root: - ship.id: 0 in transit to drop INFO:root: - ship.id: 0 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 10 DEBUG:root: - ship.id 10 in primary mining conditional INFO:root: - ship.id: 10 mining* at Position(24, 21) INFO:root: - processing ship.id: 2 INFO:root: - ship.id: 2 in transit to drop INFO:root: - ship.id: 2 returning to shipyard at Position(23, 16) INFO:root: - processing ship.id: 9 DEBUG:root: - ship.id 9 in primary mining conditional INFO:root: - ship.id: 9 mining at Position(17, 18) DEBUG:root: - spawning ship DEBUG:root:Killing from history for reassignment: [] DEBUG:root:Killing from history due to ship 8-x: [] INFO:root: - updating frame

As can be seen, at the time of the pawn formation, ship id 11 is scooting, while id 2 is in transit to drop. So there needs to be verification that each of the applicable routines is setting the current_assignments properly (in case we need to go about determination based on the turnstamp), and some navigation changes that take into account a ship existing in the direction that we want to move in.

This may not correct all cases, but it's a start and it'll yield a percentage boost.

dgets commented 5 years ago

Managed to clear up the pawn formations in those two methods with commit 1e48809. Forgot to create a separate bugfix branch; further fixing of this issue will be taking place in bugfix/avoid-pawn-formations. There are still pawn formations occurring in the blockade routines, it appears, but I think I just cut out the vast majority of them preventing my own halite stockpiling, if not all of 'em.

dgets commented 5 years ago

So maybe I was wrong about that?

dgets commented 5 years ago

Back to this issue in general; there are still places in the code where the destination hop is not properly considered; make sure that all seek_n_nav movement routines are properly considering their destinations as per our potential solution for the collisions that I've just witnessed.

dgets commented 5 years ago

Well, I did a first and ended up modifying some of the code in _hlt/gamemap. naive_navigate() hasn't been living up to my expectations, so now that I've got a good addition to it, I've thrown it into there. When there's going to be a collision it should now go into a random, unoccupied map cell, instead of just holding and waiting for conditions to change.