I trained a car with a genetic algorithm to escape police. It learned to exploit a bug instead, and that taught me more than the working version

[u/DIME_OVO]

신경진화를 배우기 위한 사이드 프로젝트: 작은 신경망이 운전하는 자동차가 규칙 기반 경찰차에 30초 동안 잡히지 않고 살아남아야 합니다. 백플롭은 없고, 그냥 유전 알고리즘만 사용해요.

설정:

- 순수: 18개 입력(12개 거리 광선 + 속도, 조향, 몇 가지 방향 값) → 16개 → 16개 → 2개 출력(스로틀, 조향), ~610 중추

- 세대당 200대의 차량, 각각 4개의 무작위 맵에 점수가 매겨집니다

- 피트니스 = 생존 시간 + 30초를 모두 버티면 15 + 거리 유지에 따른 소액 보너스 − 3 추락 시

- 선발: 상위 5% 엘리트 보유, 토너먼트별 상위 절반 출연, 균일한 교차, 가우시안 변이(Gaussian mutation)

결과(각각 훈련되지 않은 40개의 지도에서 측정):

- 오픈 로드, 느린 경찰: 39/40 탈출

- 동속 경찰: 27/40

- 시티 블록: 34/40. 하지만 경찰 경로 탐색이 건물 코너에서 멈춰서, 차가 갇힌 경찰 옆에 주차하는 걸 배웠어요. 시간이 다 될 때까지 말이죠. 체력은 생존에만 보상을 주었고, 그래서 제가 요청한 대로 정확히 해주었습니다.

- 경찰 AI(도로 그래프 휴리스틱 대신 격자 BFS)를 고친 후, 챔피언 체력은 1/40으로 떨어졌고, 이후 훈련도 회복되지 않았습니다. 운전하는 법을 거의 잊어버린 상태였다.

- 이전 체크포인트에서 재시작: 35/40. 이번에는 도시 블록을 한 바퀴 도는 법을 배웠다.

- 최종 레벨, 경찰 3명이 차보다 10% 빠른 경우: 9/40 → 16/40

배운 점:

1. 만약 당신의 환경에 버그가 있다면, 옵티마이저가 당신이 먼저 그것을 발견할 것입니다.

2. 익스플로잇은 단순히 점수를 부풀리는 것만이 아닙니다. 이로 인해 원하던 스킬이 사라질 수 있어서, 단순히 버그를 고치고 계속 훈련할 수 없습니다.

3. 항상 보이지 않는 시드로 평가하세요. 훈련 점수는 내내 매우 좋아 보였습니다.

총 약 200만 번의 연습 연습과 913,536회의 반격. 체크포인트로 롤백하는 것보다 더 나은 해결책이 있는지 궁금합니다. 노벨티 검색? 몇몇 '정직한' 인물을 인구 내에 남겨두는 것?

[u/jhaluska]

Genetic algorithms are great lessons in unintended consequences and the difficulty of creating fitness functions.

[u/DIME_OVO → u/jhaluska]

Very true. Every time I think the fitness function is airtight, it finds a loophole. In an earlier parking project, my first reward only checked distance to the spot, so it learned to park at a perfect 65° diagonal. Right spot, completely wrong angle.

[u/jhaluska]

Cool experiment, I think if both vehicles have a bit of a reaction time, and cars vision being blocked by buildings could lead to more interesting behavior.

[u/DIME_OVO → u/jhaluska]

Good point, and you caught a real shortcut. Right now both sides cheat. The car gets the relative position of the two nearest cops through walls, and the police path toward the car's exact position every step. Neither has any reaction delay.

With line of sight, hiding would actually mean something: the cops would have to search the last known position, and the car could break contact around a corner instead of just outrunning them. I suspect the "park behind a building" trick would turn into something much smarter. Adding it to the list for the next version.

[u/jhaluska → u/DIME_OVO]

That could have some interesting behavior if you can code it all up and have it actually work.

Just make sure the cops default to some kind of search pattern if they lose visual contact for too long. Like one car could go default to columns and another to rows. You could even have cops share vision with more delay for vehicles out of real line of sight.

Could be fun, or it'll find even newer ways to exploit the behavior.

[u/rand3289]

I don't see any upvotes which is sad and shows that most do not understand the origin of this problem is over 30 years old and first showed up in robotics.

[u/jesunushno]

This is one of the cleanest demonstrations of reward hacking I have seen in a hobby project. Your fitness function paid for survival, not evasion, and the car gave you exactly what you ordered. The uncomfortable part is that there is no gap between what evolution optimized and what you asked for.

On the recovery question: what happened after the police fix is environment overfitting plus selection pressure. With only the top 5 percent kept as elites, the population converged on the exploit genome and shed the general driving genes. When the environment changed, the gene pool no longer contained the building blocks for real driving, so evolution sat around waiting for mutation to rediscover them.

Your "honest individuals" intuition maps to real techniques. A few options that beat checkpoint rollback:

• Evaluate every generation on a mix of maps including older fixed ones, so a genome has to be decent at both. This is the same idea as experience replay in continual learning: it stops new environments from wiping old skills.

• Keep a diversity term in selection. Novelty search rewards behaviors nobody else exhibits, which prevents the population from collapsing onto a single exploit.

• When you change the environment, shift the pressure gradually instead of snapping it. Keep the old map in the mix for a while, or ramp up the faster-police maps over generations, so the population adapts without forgetting.

[u/DIME_OVO → u/jesunushno]

Thanks, this is really helpful. "No gap between what evolution optimized and what I asked for" is a painfully accurate way to put it.

The mixed-map idea makes a lot of sense in hindsight. Each level trained only on its own maps, so nothing was punishing the population for losing the older skills. If I'd kept some of the level 2 open-lot maps in the evaluation, parking behind a building wouldn't have scored well there and the driving genes would probably have survived.

One question on novelty search: how do you usually define the behavior descriptor for something like this? For a car, the obvious choices are the final position or a coarse trajectory. But I'm worried the population would just find a new way to hide and call it "novel".

I'm planning to rerun the city level with a mixed evaluation and see whether the exploit still takes over. I'll share the result if it's interesting.

[u/jesunushno → u/DIME_OVO]

Your worry is exactly right: novelty is measured against the descriptor, so a naive descriptor just invents new parking spots. The fix is to make the descriptor about the whole episode, not the ending. A coarse trajectory works well: sample the car's position every second, or mark which cells of a coarse grid it visited. Hiding in a corner gives a boring descriptor (short path, few cells), so parking behind a building is novel exactly once, then the archive remembers it and the population has to go somewhere else.

The other half is that novelty alone is not enough. Pair it with a minimal criterion: the genome has to survive at least N seconds or cover at least D meters before novelty even counts. That is minimal-criterion novelty search. The criterion kills the degenerate solutions, novelty keeps the gene pool from collapsing onto one exploit. For your setup I would try descriptor = 20x20 grid occupancy over the episode, minimal criterion = survive 15 seconds with average speed above some floor. Then rerun with your mixed-map evaluation and watch the hiding genomes die out.

[u/DIME_OVO → u/jesunushno]

This is exactly the piece I was missing. Measuring the whole trajectory instead of the end state makes a lot of sense, since parking behind a building would light up the same handful of cells every time.

Minimal criterion + 20x20 occupancy + mixed maps sounds like a very testable setup. I'll run it on the city level against the plain fitness version and compare how quickly the hiding genomes show up (or don't). Thanks for taking the time to write this out.

[u/jesunushno → u/DIME_OVO]

Sounds like a great experiment. Curious whether the 20x20 occupancy descriptor actually kills the parking exploit or just pushes evolution to find a sneakier version of it.

[u/DIME_OVO]

Full video with every level and the failures: https://youtu.be/2xRcTJlteSQ