Has anyone tried just generating random 100k-character brainfuck programs?

There's no way that is going to work, think of how many possible 100k-characte Brainfuck programs there are. Brainfuck does have the nice characteristic that each program is syntactically valid, but then you have the problem of running them, which is very resource-intensive (you would expect AI to be slow, so you need very large time-outs, which means you test very few programs every time-interval). Speaking of Brainfuck: http://www.vetta.org/2011/11/aiq/