The development and use of genetic programming (GP) software to synthesize true-3D artificial magnetic conductor (AMC) ground planes is presented, with the focus on achieving a lower frequency response (particularly in the high VHF to low UHF bands), low-profile, broadband designs without the use of absorbing or magnetic materials. Metallic 3D patterns are embedded in one or more substrate layers with a PEC bottom, and the patterning in the unit cell is allowed to extend into neighboring unit cells, thus achieving a lower frequency response with much smaller unit cell size and thickness. Four designs synthesized using the developed GP software are presented with achieved bandwidths ranging from 32.7% to 71.1% when using the reflection phase criterion. Further, it is shown that through the use of a parametric study, the center frequency (0 reflection phase) of one of the designs can be reduced from 381.3 MHz to 87.8 MHz, which is a 77% reduction. The edge of the square unit cell size for this miniaturized design is and the thickness is at 83.9 MHz.