Described herein is a conversation engine that can be used in a system such as a personal digital assistant or search engine that combines a dynamic knowledge graph built during execution of a request and one or more static knowledge graphs holding long term knowledge. The conversation engine comprises a state tracker that holds the dynamic knowledge graph representing the current state of the conversation, a policy engine that selects entities in the dynamic knowledge graph and executes actions provided by those entities to move the state of the conversation toward completion, and a knowledge graph search engine to search the static knowledge graph(s). The conversation is completed by building the dynamic knowledge graph over multiple rounds and chaining together operations that build toward completion of the conversation. Completion of the conversation results in completion of a request by a user.