Ett schackparti kräver att spelarna tänker flera drag framåt, en förmåga som datorprogram har bemästrat genom åren. Redan 1996 slog en superdator från IBM den dåvarande världsmästaren i schack, Garry Kasparov. Senare, 2017, vann ett program för artificiell intelligens (AI) som utvecklats av Google DeepMind, kallat AlphaZero, över de bästa datoriserade schackmotorerna på den tiden efter att ha tränat sig själv att spela spelet på några timmar.
På senare tid har vissa matematiker aktivt börjat undersöka om AI-program också kan hjälpa till att lösa några av världens svåraste matematiska problem. Men medan ett genomsnittligt schackparti varar i 30-40 drag, kräver dessa matematiska problem på forskningsnivå lösningar som tar en miljon eller fler steg, eller drag.
I ett dokument som visas på arXiv preprint-servern beskriver ett team som leds av Caltechs Sergei Gukov, John D. MacArthur Professor of Theoretical Physics and Mathematics, att utveckla en ny typ av maskininlärningsalgoritm som kan lösa matematiska problem som kräver extremt långa sekvenser av steg. Teamet använde sin nya algoritm för att lösa familjer av problem relaterade till ett övergripande decennier gammalt matematiskt problem som kallas Andrews-Curtis förmodan. I grund och botten kan algoritmen tänka längre framåt än till och med avancerade program som AlphaZero.
”Vårt program syftar till att hitta långa sekvenser av steg som är sällsynta och svåra att hitta”, säger studiens första författare Ali Shehper, en postdoktor vid Rutgers University som snart kommer att gå med i Caltech som forskare. ”Det är som att försöka hitta vägen genom en labyrint som är lika stor som jorden. Det är väldigt långa vägar som man måste testa sig fram på, och det finns bara en väg som fungerar.”
Att använda AI för att lösa matematiska problem har blivit alltmer populärt. Google DeepMinds AlphaProof presterade på samma nivå som en silvermedaljör i den internationella matematikolympiaden 2024, en matematiktävling på gymnasienivå. Och OpenAI:s o3-program resonerade sig nyligen fram genom benchmarkproblem inom matematik, vetenskap och datorprogrammering.
De Caltech-ledda matematikerna fokuserar inte på rutinproblem utan snarare på de tuffaste inom sitt område. I den nya studien använde de AI för att lösa två problemfamiljer inom Andrews-Curtis förmodan, ett gruppteoretiskt problem som först föreslogs för 60 år sedan.
Även om de inte löste själva huvudformodningen, motbevisade de problemfamiljer, så kallade potentiella motexempel, som hade varit öppna i ungefär 25 år; de gjorde också betydande framsteg med en annan familj av motexempel som har varit öppen i 44 år. Motexempel är i princip matematiska fall som skulle kunna motbevisa en ursprunglig förmodan. Om motexemplen i sig är motbevisade kan den ursprungliga gissningen fortfarande vara sann.
”Att utesluta några av motexemplen ger oss förtroende för giltigheten i den ursprungliga gissningen och hjälper oss att bygga upp vår intuition om huvudproblemet. Det ger oss nya sätt att tänka på det”, säger Shehper.
Gukov säger att det är som att ”ta sig från A till B” via invecklade rutter som kräver tusentals, miljontals eller till och med miljarder steg. Han jämför problemen med att lösa en otroligt komplex Rubiks kub.
”Kan du ta den här förvrängda, komplicerade Rubiks kub och få tillbaka den till sitt ursprungliga tillstånd? Du måste testa dessa mycket långa sekvenser av drag, och du kommer inte att veta om du är på rätt väg förrän i slutet”, säger Gukov, som också är chef för Caltechs nya Richard N. Merkin Center for Pure and Applied Mathematics.
Den maximala ökningen av längden på en presentation i förhållande till dess ursprungliga längd längs AC-trivialiseringsvägen. Ökningen är plottad som en funktion av den ursprungliga längden på presentationen till vänster och som en funktion av n till höger. Kredit: arXiv (2024). DOI: 10.48550/arxiv.2408.15332
Teamets AI-program lärde sig att komma med långa sekvenser av drag – som forskarna kallade ”superdrag” – som är oväntade, eller vad forskarna kallar outliers. Detta står i kontrast till hur AI-program som ChatGPT fungerar.
”Om du ber ChatGPT att skriva ett brev kommer det att komma fram till något typiskt. Det är osannolikt att det kommer att komma med något unikt och mycket originellt. Det är en bra papegoja”, säger Gukov. ”Vårt program är bra på att komma på avvikelser.”
För att träna sitt AI-program använde forskarna en maskininlärningsmodell som kallas förstärkningsinlärning. Först visade teamet AI:n enkla problem att lösa och gav den sedan successivt svårare och svårare problem.
”Den provar olika drag och blir belönad för att den löser problemen”, förklarar Shehper. ”Vi uppmuntrar programmet att göra mer av samma sak samtidigt som det behåller en viss nyfikenhet. Till slut utvecklar det nya strategier som är bättre än vad människor kan göra. Det är det magiska med förstärkningsinlärning.”
För närvarande är AI-program vanligtvis inte särskilt bra på att förutsäga avlägsna, sällsynta händelser som får dramatiska konsekvenser, t.ex. krascher på finansmarknaden. Teamets nya algoritm kan inte heller göra sådana förutsägelser, men den kan innehålla fröet till vad som skulle krävas för att göra intelligenta förutsägelser av den här typen. ”I grund och botten vet vårt program hur man lär sig att lära sig”, säger Gukov. ”Det tänker utanför boxen.”
Teamets nya algoritm har redan fått stort genomslag i matematikvärlden.
”Vi har gjort en hel del förbättringar inom ett område av matematiken som var flera decennier gammalt”, säger Gukov. ”Utvecklingen hade gått relativt långsamt, men nu är det full fart framåt.”
Faktum är att tre nya matematiker har anslutit sig till teamet – Lucas Fagan och Zhenghan Wang från UC Santa Barbara och Yang Qiu från Nankai University i Tianjin, Kina – och gruppen har publicerat ytterligare ett preprint-dokument som rapporterar att man löser ännu fler familjer av potentiella kontrafaktiska modeller som tillhör Andrews-Curtis förmodan.
I stället för att skala upp AI-modellerna har teamets strategi varit att hitta nya smarta knep och strategier som inte kräver stora mängder datorkraft.
”Vi försöker visa goda resultat på småskaliga datorer, som är lättillgängliga för ett litet akademiskt samarbete, så att alla våra kollegor runt om i världen enkelt kan reproducera dessa resultat”, säger forskarna.
För mer information: Ali Shehper et al, What makes math problems hard for reinforcement learning: a case study, arXiv (2024). DOI: 10.48550/arxiv.2408.15332
