Lukious/Rewrite

Lukious Sub-pages:

Lukious - Version History - RRGC - Rewrite - Archived Talk 20090521

---

I'm re-deriving Lukious from post-rewrite Dookious. Simonton demanded I post some TC results by today, so here are the latest. I'll clean this up later.

Targeting Challenge 2K7/Results (500 rounds):

Name	Gun	CC	RMX	SHA	WS	WOE	Surf	DM	FT	GG	RMC	WLO	No Surf	Total	Comment
Lukious 1.19.10	DC/GF	68.03	74.49	64.95	69.13	69.21	69.16	87.11	77.76	82.63	77.79	81.97	81.45	75.31	3 seasons
Lukious 1.19.13	DC/GF	72.94	76.93	69.59	76.67	72.84	73.79	87.99	79.71	84.85	78.04	80.63	82.24	78.02	3 seasons
Lukious 1.19.15	DC/GF	69.82	76.40	71.37	75.43	69.87	72.58	87.66	78.94	83.03	76.44	79.56	81.13	76.85	3 seasons
Lukious 1.19.16	DC/GF	71.21	76.80	70.67	76.96	71.50	73.43	88.06	78.39	83.55	77.13	81.40	81.71	77.57	3 seasons
Lukious 1.19.20	DC/GF	70.95	78.45	72.45	77.76	71.60	74.23	86.83	78.06	85.96	77.66	79.59	81.62	77.93	3 seasons
Lukious 1.19.24	DC/GF							87.79	77.84	84.14	77.65	81.27	81.74		3 seasons
Lukious 1.19.32	DC/GF							88.25	78.40	84.78	77.47	80.30	81.84		8 seasons

Targeting Challenge 2K7/Fast Learning Results:

Name	Gun	CC	RMX	SHA	WS	WOE	Surf	DM	FT	GG	RMC	WLO	No Surf	Total	Commentsteady
Lukious 1.19.10	DC/GF	67.87	75.65	61.07	71.89	68.87	69.07	87.47	78.77	80.88	78.29	81.64	81.41	75.24	40 seasons
Lukious 1.19.13	DC/GF	70.65	77.40	64.45	76.03	71.93	72.09	86.77	80.14	81.91	78.17	81.73	81.74	76.92	40 seasons
Lukious 1.19.20	DC/GF	69.49	76.99	68.53	75.58	70.63	72.24	86.63	78.52	82.71	77.86	79.41	81.03	76.63	40 seasons
Lukious 1.19.24	DC/GF	68.39	76.93	67.22	74.21	69.14	71.18	86.23	76.21	82.17	75.34	79.92	79.25	75.58	50 seasons

Targeting Challenge 2K6/Results (500 rounds):

Name

Gun

BFly

CC

Chk

Cig

Cya

DM

FM

Grb

RMB

Tig

Total

Comment

Lukious 1.19.10

DC/GF

99.76

67.58

94.57

87.73

77.83

93.31

89.75

87.44

90.99

83.54

87.25

4 seasons

Version Notes:

• 1.19.10: 22,000 scans, cluster size 50.
• 1.19.13: 40,000 scans, cluster size 50. Switched the abs-ticks-from-firetime to use a "Triweight" instead of "Triangle" distribution. (Basically, more heavily weighting scans closer to fire time. See Kernel Density Estimators.) Misc tweaks to distance function.
• 1.19.15: Entropy-based dynamic weighting on Dynamic Clustering attributes. Keeps a singly segmented Visit Count Stats style buffer for each attribute, solely for calculating entropy. Each attribute has 3 segments, evenly distributed across the domain. Attribute with max information gain is weighted 5, with others scaled linearly such that 0 info gain would be weighted 1. All 13 attributes enabled: lateral velocity, advancing velocity, distance, wall distance, wall distance reverse, accel, distance last 8 ticks, distance last 15 ticks, distance last 25 ticks, time since velocity change, time since zero velocity, time since max velocity, abs ticks from aiming time (2 offset from fire time).
• 1.19.16: Uses "good" segments instead of evenly distributed ones; not all attributes are split into the same number of segments. Max weight is 7 instead of 5.
• 1.19.20: Added two more attributes: turn rate and distance last 60 ticks. Misc tweaks to existing attributes. Dynamic weights now exactly (still linearly) proportional to the information gain - attribute with 0 info gain would be weighted 0. Back to the Triangle distribution for the fire time element of KernelDensity (i.e., increasing weights of non-firing waves) and one small tweak to the KernelDensity method.
• 1.19.24: Dropped 5 attributes: distance last 15 ticks, distance last 25 ticks, time since velocity changed, time since max velocity, and turn rate. Forgot I'd left this in there - using Cosinus distribution instead of Gaussian for the KernelDensity. (Not sure this matters much at all...) Dimension weights used by the gun are a running total of weights that are calculated once per shot, trying to take mutual information into account.
  • For each attribute, find 50 closest scans among last 1,000, using only that attribute in the distance formula; calculate the entropy of the GuessFactors returned (sliced into a VisitCountStats bin); and find the info gain (from maximum entropy); this info gain is the initial weight for that attribute in this calculation.
  • Then, for each combination of two attributes, again find 50 closest scans among last 1,000, using only these two attributes in the distancing function; find the entropy and info gain (infoGainCombo) of the resulting GuessFactors; multiply both attributes' weights by ((infoGain1 + infoGain2) / infoGainCombo). E.g., if infoGain1 == infoGain2 == infoGainCombo, then nothing is gained from using both attributes vs using either one (i.e., they are measuring the same thing), so their weights are cut in half. I have no idea if this should scale linearly like this, but this value is almost always between .5 and 1, so I think this is at least somewhat sound.
  • Loop through the (temporary) weights on each element, find the max, and then divide them all by the max, for normalization. This is so that one calculation matters as much as the next one.
  • Add this temporary weight to the actual weight for each element.
• 1.19.32: Turned off all weighting, to serve as a baseline comparison for 1.19.33. Custom scaling for many attributes - e.g., third root of AdvancingVelocity, the portions from 0-1 and 7-8 count double in lateral velocity, and decelerating values for accel are halved. Returned to Gaussian distribution in kernel density. Adjusted the GuessFactor bandwidth in the KernelDensity calculation to try and account for an issue David made me aware of. Returned to Gaussian distribution for kernel density.

---

Some info on the above:

• Based on Dookious, so inherits the nicely polished wave handling and Virtual Guns systems and all other non-stats stuff.
• I've been toying with a "Main Gun" and an "AntiSurfer Gun", but I am dropping the latter for now, for a couple of reasons: first, non-surfers are far more important to focus on at first with a gun; second, a DC gun tends to do OK against surfers anyway (note that Shadow only has one gun).
• 1.19.10 is just Main Gun, with 22,000 scans and a cluster size of 50.
• KernelDensity (among closest scans) has two elements:
  • First dimension is the difference in Guess Factors, Gaussian distribution with a bandwidth of half a bot width (much like Chalk and old Lukious).
  • Second dimension is what I call "absolute ticks to fire time", which is min(time since bullet fired, time until gun cooled), with (1 - (absTicks / 9)) (I guess this is called a "Triangle" distribution).
• Scan distance formula is Euclidean (square root(sum of squares)) distance with lateral velocity, advancing velocity, distance, wall distance (forward and reverse), distance last eight ticks, time since velocity change (divided by bullet time), and abs ticks to fire time. Right now, all with intuitive (static) weights. (No, I don't actually do the square root on all of them, only the closest ones once I find them. :P)

A couple key speed improvements I've learned along the way:

• Don't have any sin's or cos's in your distance formula. =) Kinda obvious, but it's easy to forget what's behind that "getLateralVelocity()" method call.
• I was inspired by a Wave Surfing related tip from Krabb and found another excellent improvement: pass the current "max distance" to your scan distancing method as you're iterating through your scans, calculate your highest weighted factors first in the distancing method, check if you've already passed the max distance a few times throughout and just cut off if you have. I was able to increase from ~25,000 to ~40,000 scans with a first pass at this trick.
• Keeping the list of closest scans sorted when generating them is really good (learned from Corbos' Chalk, he may have learned from ABC's DCBot). It's still O(n = cluster size) to update your maximum distance among your closest scans, but it averages to probably (n/2) or less if you keep it sorted, I think. Note: upon reviewing things, this doesn't matter as much as I thought!